CN110831105A

CN110831105A - Method for selecting nodes with fewer neighbors in Ad Hoc route to reduce communication interference

Info

Publication number: CN110831105A
Application number: CN201911343039.2A
Authority: CN
Inventors: 王超; 付光远; 魏振华; 杨世荣; 赵士裕; 王修东
Original assignee: Rocket Force University of Engineering of PLA
Current assignee: Rocket Force University of Engineering of PLA
Priority date: 2019-12-24
Filing date: 2019-12-24
Publication date: 2020-02-21

Abstract

The invention belongs to the technical field of networks, and discloses a method for reducing communication interference by selecting nodes with fewer neighbors in an Ad Hoc route, which is characterized by comprising the following steps: comprises the following steps: a first step of using location-based routing in a MANETs network; secondly, introducing a conservative neighborhood range; and thirdly, using the nodes with fewer neighbors as next hop nodes. The invention provides a new method, namely GBR-CNR-LN, to improve the performance of GBR method, and simulation experiments show that the proposed method significantly improves the packet transfer performance and ensures higher network stability. The method has the advantages of remarkably improving the performance of packet transmission, ensuring higher network stability and improving the communication reliability.

Description

Method for selecting nodes with fewer neighbors in Ad Hoc route to reduce communication interference

Technical Field

The invention relates to the technical field of networks, in particular to a method for reducing communication interference by selecting nodes with fewer neighbors in an Ad Hoc route.

Background

Ad Hoc is a MulTI-hop, centerless, Ad-Hoc wireless Network, also known as a MulTI-hop Network (MulTI-hop Network), infrastructure-free Network (infrastructure-free Network) or Self-organizing Network (Self-organizing Network), formed by a group of autonomous wireless nodes or terminals cooperating with each other, a Network that is independent of fixed infrastructure and that employs distributed management, is a Self-creating, Self-organizing and Self-managing Network, has no fixed infrastructure throughout the Network, each node is mobile, and can dynamically maintain contact with other nodes in any way. In the network, due to the limitation of the wireless coverage value range of the terminal, two user terminals which cannot directly communicate can forward packets by means of other nodes. Each node is also a router that performs the functions of discovering and maintaining routes to other nodes.

In order to effectively perform communication in Mobile Ad Hoc Networks (MANETs), it is very important to handle interference when constructing a multi-hop route. By establishing interference-aware routing, the effects of interference in the overall wireless communication can potentially be reduced, thereby improving network performance. Mobile devices represented by nodes in MANETs are used for broadcasting in a limited shared medium, and the use of both routing and scheduling mechanisms in wireless transmissions can reduce redundancy and communication interference. Mobile devices in MANETs can typically move in any direction, and therefore the shared media between mobile devices may change often. In MANETs, all nodes that are to exchange messages (packets) must transmit their packets simultaneously if there is no interference affecting their communications. In other words, to improve network efficiency for MANETs, routing and scheduling protocols must account for parallel transmissions on multiple links. Interference in MANETs is a result of concurrent transmissions in the neighborhood (asynchronous), and is also associated with collisions (producing corrupted data) by nodes that are outside range of each other transmitting simultaneously (synchronously) to a common receiver. However, in MANETs, the route from the source to the destination in a particular path may not be the best choice when considering interference. That is, to minimize communication interference, the selected path may not be the shortest path or the number of hops in the routing path may be increased.

Document a greedy-based stable multi-path routing protocol in mobile Ad Hoc Networks [ J ]. Ad Hoc Networks, 2011: 662-674. greedy-based Backup Routing Protocol (GBR), Greedy Perimeter Stateless Routing (GPSR) is used to construct a primary path such that each node treats the node closest to the destination within its transmission range as the next hop. To maintain the stability of the local link, the GBR constructs the backup path locally. But due to the greedy approach of GPSR, a node may move out of transmission range before the next HELLO beacon broadcast, resulting in no longer receiving a transmission.

Disclosure of Invention

The purpose of the invention is: the method overcomes the defects in the prior art, and provides a method for selecting nodes with fewer neighbors in the Ad Hoc route to reduce communication interference, so that the stability of connection can be maintained, and the communication reliability is improved.

The technical scheme of the invention is as follows: a method for selecting nodes with fewer neighbors in Ad Hoc routing to reduce communication interference comprises the following steps:

a first step of using location-based routing in a MANETs network;

the routing in MANETs depends on many factors, including the network topology, the type of information available in the routing process, and the specific underlying network characteristics, which can serve as a heuristic factor to efficiently find paths with less communication interference. To define how connections between communication nodes are established in MANETs, a network model of MANETs is first defined and how routes are determined in the model is discussed. MANETs can be modeled using graph G = (V, E), where V represents a set of nodes/vertices and E represents a set of links/edges. Each edge represents a link between two nodes currently in transmission range, for this work, assuming all nodes are identical, n (vi) represents the set of neighbors of node vi, the path used as the first choice when transmitting from source to destination is called the primary path. Each node in MANETs has a unique identifier whose geographical location is known. In the real world, it is assumed that the global positioning system and/or location services are used to track the location of nodes in MANETs; suppose nodes are arranged in two-dimensional euclidean space such that G is a geometric graph; it is assumed that all nodes regularly broadcast their location to their neighbors using HELLO messages (also referred to as beacon messages).

There are two main types of routing in Ad Hoc networks, namely topology-based routing and location-based routing. Topology-based routing protocols use link information available in the network to determine routes between nodes. Location-based routing uses the location of a node to determine a route. In location-based routing, each network node is informed of its location, the locations of its neighbors, and the location of the destination. Location-based routing scales well even with highly dynamic networks, since no explicit routes need to be maintained. This is a major advantage of mobile Ad Hoc networks, since in mobile Ad Hoc networks the topology may change often. Location-based routing often uses one or both of geometry-based routing, greedy routing and surface-based routing. In the invention, hybrid routing can be used, the advantages of greedy routing and surface routing are fully combined, and when the greedy-based routing cannot find a node closer to a destination, the surface-based routing is beneficial to obtaining a standby node.

Preferably, a Greedy-based Backup routing protocol (GBR) is used.

Secondly, introducing a conservative transmission range;

since nodes move constantly at different speeds and directions, a node that is within transmission range of another neighboring node at one time may be out of range at another time. In Greedy-based backup Routing Protocol (GBR), Greedy Perimeter Stateless Routing (GPSR) is used to construct a primary path such that each node treats the node closest to the destination within its transmission range as the next hop. To maintain the stability of the local link, the GBR constructs the backup path locally, and because of the greedy approach of GPSR, the node may move out of transmission range before the next HELLO beacon broadcast, resulting in no longer receiving a transmission.

In response to the above problems, the present invention introduces a Conservative Neighbor Range (CNR) to improve GBR, which takes into account the possibility that nodes may be out of range during an interval and then avoids including them in the path, thereby significantly reducing packet loss and improving reliability of communication. Fig. 1 shows the construction and use of the model, with node u being the sender and node D being the destination. If node v does not exceed node u's transmission range during the HELLO broadcast interval, node u will select node v closest to the destination as its next hop node. In fig. 1, CNR is defined by a conservative neighborhood transmission range Rc, which depends on the speed of the node, the interval between HELLO message broadcasts, and the actual transmission range value. Rc ═ R- (vmax.t), where R is the actual transmission range, vmax is the maximum node speed, and t is the time interval between HELLO message broadcasts. If the next hop neighbor vi +1 chooses to be within this conservative neighborhood range of vi, then vi +1 will not exceed the transmission range of vi within this interval, and any links in the primary path will not be broken and the primary path will not need to be backed up until the next HELLO beacon broadcast, which is referred to as greedy-based conservative neighborhood range backup routing protocol (GBR-CNR).

And thirdly, in the transmission range, using the nodes with less neighbors as next hop nodes.

In order to improve the anti-interference capability of GBR-CNR, the number of neighbors of a receiving node is considered, and a GBR-CNR-LN (GBR-CNR with less neighbors) method is provided. Thus in fig. 2, node a would select B2 instead of B1 as the next hop because the number of neighbors of B2 is less than the number of neighbors of B1. Fewer neighbors will reduce the probability of a packet being corrupted, thereby increasing network throughput.

The invention has the beneficial effects that: the invention provides a method for reducing communication interference by selecting nodes with fewer neighbors in an Ad Hoc route, which obviously improves the packet transmission performance, ensures higher network stability and improves the communication reliability.

Drawings

FIG. 1 is a schematic representation of the GBR-CNR model of the present invention;

FIG. 2 is a schematic diagram of the present invention in selecting a next hop node;

FIG. 3 is a histogram of the total number of packets transferred in the simulation results of the embodiment of the present invention;

FIG. 4 is a histogram of the maximum number of times a node is included in different connections in the simulation results of the embodiment of the present invention;

FIG. 5 is a histogram of the percentage of packet loss in simulation results for an embodiment of the present invention;

FIG. 6 is a histogram of the percentage of damaged packets in the simulation results of an embodiment of the present invention.

Detailed Description

The invention will be described in further detail below with reference to the drawings and specific examples.

Examples

In order to compare and analyze the performance of GBR, GBR-CNR and GBR-CNR-LN, Matlab is used for simulation in the embodiment, and the average performance result can be obtained for better analysis.

For all methods, we construct the primary path as described in the first and second steps above, and determine the backup path in addition to the GBR method. The simulation environment adopts network parameters of 2500m × 2500m, 400 nodes, the maximum transmission range of R =250m, each simulation time is 600 seconds, and enough data packets are used for simulation time. There are 20 pairs of constant bit rate data streams in the network layer, with different source and destination streams being chosen randomly. Each stream has not changed its source and target throughout the simulation. At the start of the simulation, the direction in which the node can move is given at random. For each different node density, 28 randomly distributed connectivity graphs are used as the starting network topology for each run of all methods, with the speed selection the same for all nodes at V =10m/s and the HELLO beacon interval t set to 2 seconds. At the end of the two second interval, if a path fails to be determined in the next two second interval, a new path is determined between the source and target at the beginning of the next HELLO interval.

Simulation results as shown in fig. 3-6, the number of packets sent and transmitted for the original GBR is much smaller compared to the CNR-based version, as shown in fig. 3, due to the path being broken and either having to be re-established using a backup path or requiring a full re-calculation before the end of the HELLO beacon interval. Accordingly, the percentage of lost packets is highest in GBR as shown in fig. 5.

It should be noted that the total number of packets delivered by all methods will be the total number of uncorrupted and corrupted packets during the entire simulation time, as shown in fig. 6, and the percentage of corrupted packets is also highest for GBR.

Finally, it is noted that over-utilization of certain nodes in sensor networks and the like MANETs can lead to node failure, which is the maximum number of distinct paths that a node may be a member. In fig. 4, it can again be seen that the original GBR method may increase the usage of some nodes by a factor of 5 higher than the corresponding maximum used node in the CNR version.

Simulation experiments show that the proposed GBR-CNR-LN method remarkably improves the packet transfer performance and ensures higher network stability.

It will be apparent to those skilled in the art that various changes and modifications may be made in the present invention without departing from the spirit and scope of the invention. Thus, if such modifications and variations of the present invention fall within the scope of the claims of the present invention and their equivalents, the present invention is intended to include such modifications and variations.

Claims

A method of selecting nodes with fewer neighbors in an Ad Hoc route to reduce communication interference, characterized by: comprises the following steps: a first step of using location-based routing in a MANETs network;

a second step of introducing a conservative transmission range that takes into account the possibility that nodes will go out of range during the interval and then avoid including them in the path;

and thirdly, using the nodes with fewer neighbors in the range of the previous step as the next hop nodes.
2. The method of selecting nodes with fewer neighbors in Ad Hoc routing of claim 1 to reduce interference to communications, wherein: the location-based routing in the first step uses one or two geometry-based routes, namely greedy-based routing and surface-based routing.
3. The method of selecting nodes with fewer neighbors in Ad Hoc routing of claim 2 to reduce interference to communications, characterized by: the first step uses a hybrid route, the advantages of greedy route and surface route are fully combined, and when the greedy-based route cannot find a node closer to a destination, the surface-based route is beneficial to obtaining a standby node.
4. The method of selecting nodes with fewer neighbors in Ad Hoc routing of claim 1 to reduce interference to communications, wherein: the first step uses Greedy-based Backup routing protocol (GBR).
5. The method of selecting nodes with fewer neighbors in Ad Hoc routing of claim 4 to reduce interference to communications, wherein: in the second step, a Conservative Neighbor Range (CNR) is introduced to improve GBR, which takes into account the possibility that nodes will go out of Range during the interval and then avoid including them in the path.
6. The method of selecting nodes with fewer neighbors in Ad Hoc routing of claim 5 to reduce interference to communications, wherein: in the third step, a GBR-CNR-LN (GBR-CNR with less neighbors) method is used, and nodes with fewer neighbors are selected as next hop nodes.