CN101409905A - Routing method for mobile multi-hop grouping wireless network based on random broadcast mode - Google Patents

Abstract

The embodiment of the present invention provides a mobile multi-hop packet wireless network routing method based on anycast mode, comprising: the source node sends a routing request packet containing the service value and the address of the anycast group where the source node is located; receiving the routing request The forwarding node of the packet searches for the destination node in the anycast group where the forwarding node is located. If the destination node is not found, the function algorithm is used to determine the anycast group closest to the anycast group where the forwarding node is located according to the anycast group address information, and the The routing request packet is sent to the nearest anycast group to continue searching for the destination node in the nearest anycast group; and so on until the destination node is found; establish communication between the source node and the destination node connect. Through this method, the purpose node can be quickly searched, and the efficiency of resource retrieval and query is improved.

Description

A Routing Method for Mobile Multi-hop Packet Wireless Network Based on Anycast

technical field

The invention relates to the technical field of wireless communication, in particular to an anycast-based mobile multi-hop packet wireless network routing method.

Background technique

With the development of wireless communication technology, the fusion technology of Ad Hoc (mobile multi-hop packet wireless) network technology and Peer-to-Peer (peer-to-peer computing network technology) has been paid more and more attention. Ad Hoc network is not dependent on any infrastructure, non-central self-organizing distributed multi-hop wireless network, the nodes in the network are all mobile hosts. In an Ad Hoc network, if two mobile hosts are within the communication coverage of each other, they can communicate directly; however, due to the limited communication coverage of the mobile hosts, if two mobile hosts that are far apart need to communicate, they must rely on this Other mobile hosts between two mobile hosts forward data to achieve communication. Therefore, in the Ad Hoc network, each mobile host is responsible for finding routes and forwarding data. Routing generally needs to go through multiple hops, and data can only reach the destination after being forwarded by multiple mobile hosts.

At present, the AODV (Ad Hoc On-Demand Distance Vector) protocol based on anycast, referred to as AAODV (Anycast AODV), is applied to the Ad Hoc network.

Anycast technology is a new network application that can support assigning an address to multiple nodes to provide specific services, and data packets with anycast destination addresses can use the same anycast address and be sent to the above-mentioned any one of many nodes. Therefore, in a given routing area, an anycast address can correspond to multiple nodes. The anycast protocol must establish and maintain the message information necessary for anycast addresses to forward data to nodes.

The working process of the AAODV protocol is as follows: When the mobile node needs to send data but cannot find a suitable path in the routing table, the mobile node broadcasts routing request information. If the routing request information can reach the destination node, the destination node will return a reply request information to the mobile node; otherwise, an error report will be returned. The mobile node can also broadcast some relevant information periodically in a local area, so as to obtain the location of the next hop node, update the routing table in time, and detect whether there is a new mobile node joining the network. In order to reduce additional communication overhead, according to the AAODV protocol, anycast addresses can be mapped to unicast addresses through control signaling.

However, the existing AAODV protocol does not take into account the particularity of Peer-to-Peer services, especially when there are many mobile nodes in the Ad Hoc network, it will consume a lot of network resources and time to forward data through a large number of nodes to find the destination node, and The AAODV protocol also does not adopt a service retrieval method suitable for Peer-to-Peer, and lacks support for retrieval services. Therefore, the AAODV protocol is not suitable for Peer-to-Peer services.

Contents of the invention

In view of the problems existing in the above-mentioned prior art, embodiments of the present invention provide an Ad Hoc network routing method (Anycast based AODV routing protocol for peer to peer services in MANET) suitable for Peer-to-Peer services based on anycast mode, Abbreviated as AAPP. This method is suitable for "resource-centric" routing of peer topeer services.

In order to achieve the above object, the present invention provides a mobile multi-hop packet wireless network routing method based on anycast mode, comprising: the source node sends a routing request packet containing the service value and the address of the anycast group where the source node is located; The forwarding node of the routing request packet searches for the destination node in the anycast group where the forwarding node is located. If it is not found, the function algorithm is used to determine the anycast group closest to the anycast group where the forwarding node is located according to the anycast group address information. , and send the route request packet to the nearest anycast group to continue searching for the destination node in the nearest anycast group; and so on until the destination node is found; establish source node and destination node The communication link of the node.

It can be seen from the description of the above-mentioned technical solution that the embodiment of the present invention realizes a fast process by establishing an anycast group in an Ad Hoc network, adding a service value and an anycast group address in a routing request packet, and using a function algorithm to search for a target anycast group at the same time. Finding the corresponding destination node improves the efficiency of resource retrieval and query, balances network traffic, reduces transmission delay, improves link utilization efficiency, improves network performance, and better supports peer to peer services. Through this method, the resource discovery and positioning method of peer to peer is integrated with the routing method of Ad Hoc network, and the characteristics of anycast routing are combined, which is especially suitable for the "resource-centered" routing of peer to peer business.

Description of drawings

Fig. 1 is the schematic diagram of the RREQ packet format that the embodiment of the present invention provides;

Fig. 2 is a schematic diagram of the RREP packet format provided by the embodiment of the present invention;

Fig. 3 is that the RREQ packet that the embodiment of the present invention provides produces, sends flow chart;

Fig. 4 is the flow chart of forwarding node processing and forwarding RREQ packet provided by the embodiment of the present invention;

Fig. 5 is a model diagram of utilizing the Chord algorithm to process anycast group ID provided by the embodiment of the present invention;

FIG. 6 is a diagram of a service location and discovery model provided by an embodiment of the present invention;

Fig. 7 is a flow chart of implementing service discovery and location provided by an embodiment of the present invention.

Detailed ways

Embodiments of the present invention set up anycast groups in the Ad Hoc network, add service value and anycast group address (i.e. anycast group ID) in the routing request packet, and can quickly find the destination anycast group of the routing request packet through the function algorithm address, and quickly determine the destination node in the anycast group, and establish a communication connection between the source node and the destination node, which greatly improves the efficiency of network resource retrieval.

In the embodiment of the present invention, several nodes are formed into an anycast group, each anycast group has a unique anycast group ID, and nodes in each group share an anycast group ID. The source node sends a routing request packet containing the service value and the address of the anycast group it belongs to. The service value is obtained by hashing the keyword of the service requested by the source node, that is, the routing request packet contains the service information, the forwarding node that receives the routing request packet searches for the destination node in the anycast group where the forwarding node is located. The nearest anycast group of the broadcast group, and send the route request packet to the nearest anycast group, so as to continue to search for the destination node in the nearest anycast group; and so on, until the destination node is found Node; establish a communication connection between the source node and the destination node.

Embodiments of the present invention will be described in detail below in conjunction with the accompanying drawings.

In the prior art, there are no service value and anycast group ID fields in the RREQ (routing request packet) format. In the AAPP provided by the embodiment of the present invention, the service value and anycast group ID fields are added in the RREQ packet. The format of the RREQ packet with the above fields added is shown in FIG. 1 . Figure 1 is a schematic diagram of the format of the RREQ packet provided by the embodiment of the present invention. The newly added Service Key in the figure represents the service value, and the Anycase groupID represents the address of anycast group. It can be seen that other original formats of the RREQ packet have not changed.

Similarly, in the AAPP provided by the embodiment of the present invention, an anycast group ID field is added in the RREP (routing response packet), and the format of the RREP packet with the added anycast group ID field is shown in FIG. 2 . Figure 2 is a schematic diagram of the format of the RREP packet provided by the embodiment of the present invention, in which the newly added Anycase groupID represents the anycast group address, and it can be seen that other original formats of the RREP packet have not changed.

In the embodiment of the present invention, the RREQ packet is generated and sent by the source node. In an anycast group, when a node (source node) needs to be routed to another node (destination node) in the same group, the source node will first check all newly joined nodes that have the same anycast group address as the source node, and judge Whether there are multiple links between the source node and the destination node; if there are multiple links, the source node will choose a link with the smallest number of hops, and at the same time use the destination node as a server node to store relevant information; if not link, the source node anycasts a RREQ packet to find a route to the destination node, the hop count field in the RREQ packet is cleared, and the RREQ packet stores the IP address and serial number of each node in the anycast group , the configuration of other fields is similar to that of unicast. After the destination node receives the request packet from the source node, the routing response packet sent when replying to the source node in unicast mode includes: the IP address of the destination node and the anycast group address of the anycast group where the destination node is located. Fig. 3 is the flow chart of RREQ bag generation, sending process, below in conjunction with Fig. 3 this flow process is described in detail, the steps are as follows:

Step 30: When the source node needs to establish a link to the destination node, check the routing table to determine whether there is at least one link between the source node and the destination node. If there is no such link, proceed to step 310, and if such a link exists, proceed to step 31.

Step 31: If there is at least one link between the source node and the destination node, the source node selects a link with the least number of hops.

Step 32: After the source node selects the link with the least number of hops, determine whether there is a link with the same number of hops, that is, determine whether there is a link with the same number of hops as the link with the least number of hops; if it exists, go to step 33 , if not, go to step 34.

Step 33: The source node selects the link with the longest lifetime as the link connected to the destination node.

Step 34: Establish a connection between the source node and the destination node according to the selected link, and use the destination node as a server node to store relevant information.

Step 310: Since the source node does not find a path to the destination node, the source node creates a RREQ packet and initializes the RREQ packet, that is, the hop count field in the packet is cleared to zero, and the packet stored in the same path as the source node The IP addresses and serial numbers of other nodes in the anycast group. The configuration of other fields is similar to that of unicast.

Step 311: The source node anycasts the RREQ packet.

When a forwarding node receives a RREQ packet, it first judges the value of flagA of the RREQ packet; if A is zero, it means that the RREQ packet is a unicast data packet, and the forwarding node processes the RREQ packet in a unicast manner ; If A is 1, it means that the RREQ packet is an anycast packet, and the forwarding node needs to judge whether it has received the same RREQ at the same time according to the anycast group ID and the initial IP address in the RREQ packet. For the same RREQ packet, the newly received same RREQ packet is discarded. If the forwarding node judges that it has not received the same RREQ packet before, it first checks the same node with the node address in the routing table and the source address of the RREQ packet, and judges whether the IP address of the source node has changed (because each node position in the network, The address may change at any time), if there is a change, the source node address in the RREQ packet is updated to the new IP address of the source node, and the update operation is similar to the unicast update operation. Then, if the forwarding node and the destination node are in the same anycast group or there is at least one path from the forwarding node to the anycast group where the destination node is located, the forwarding node creates an RREP packet and sends it in unicast mode To the source node, inform the source node of the path to the destination node; if the forwarding node and the destination node are not in the same anycast group, and there is no path from the forwarding node to the anycast group where the destination node is located, then the forwarding The node updates the above RREQ packet, and then broadcasts it to find a route to the destination node. Fig. 4 is the flowchart of forwarding node processing and forwarding RREQ packet, and the steps of forwarding node processing and forwarding RREQ packet are as follows:

Step 401: After receiving the RREQ packet, the forwarding node judges the flagA flag of the RREQ packet. If A is equal to zero, proceed to step 403; if A is equal to 1, proceed to step 402.

Step 402: The forwarding node judges whether it has received the same RREQ at the same time according to the anycast group ID and the initial IP address in the RREQ packet, if it has received the same RREQ packet, then proceed to step 404, if not, proceed to Step 405.

Step 403: the forwarding node processes the RREQ packet in a unicast manner.

Step 404: The forwarding node discards the newly received RREQ packet identical to the above RREQ packet.

Step 405: The forwarding node checks the node in the routing table with the same IP address as the source node of the RREQ packet, and judges whether the IP address of the source node has changed, and if so, updates the IP address of the source node in the RREQ packet to the new IP of the source node address.

Step 406: The forwarding node judges whether there is a path between the node and the destination node of the RREQ packet, if yes, go to step 407, if not, go to step 408.

Step 407: The forwarding node initializes the RREP packet, which carries the IP address of the destination node and the anycast group address of the destination node. Go to step 409.

Step 408: Since there is no path from the forwarding node to the destination node, the forwarding node broadcasts the RREQ packet after updating it.

Step 409: the forwarding node sends the RREP packet to the source node in a unicast manner.

In the embodiment of the present invention, the anycast group where the destination node is located is quickly searched according to the function algorithm, and the principle of determining the destination node after determining the anycast group where the destination node is located is as follows: In AAPP, after the anycast group is established, each node maintains an Routing table, the routing table entry (that is, the first node in the routing table) includes: anycast group ID, destination IP address, destination serial number, interface, hop count, last hop count, next hop, life cycle and route marking . The AAPP provided in the embodiment of the present invention is a routing improvement protocol based on the AODV protocol. An anycast group ID field is added to the routing table of the initiating routing node, and multiple adjacent tasks are stored in the routing table of each node in the anycast group. broadcast group address to form an anycast group address ID list. By querying the list of anycast group IDs, nodes can quickly find relevant anycast groups. When the source node sends a RREQ packet, the service value in the packet indicates the service required by the source node. After receiving the RREQ packet, the forwarding node can use the function algorithm to perform calculations, and combine the address information of the anycast group to obtain the address of the current node. Anycast group The address of the nearest anycast group. In the embodiment of the present invention, the function algorithm used to find the destination node is the Chord algorithm. In other words, the Chord algorithm can be used to locate anycast groups providing services. The source node sends a routing request packet containing the service value and the address of the anycast group where the source node is located. After receiving the routing request packet, the forwarding node searches for the destination node in the anycast group where the forwarding node is located. If not found, then Use a function algorithm to determine the nearest anycast group to the anycast group where the forwarding node is located according to the anycast group address information, and send the routing request packet to the nearest anycast group, so as to be in the nearest anycast group continue to search for the destination node; and so on, until the destination node is found in the anycast group through anycast routing technology, the communication connection between the source node and the destination node is established. When the nodes in each anycast group in the network provide similar services, and anycast groups providing different services are distributed in the network with a certain rule, the embodiment of the present invention can find the destination node faster.

In the same anycast group, the ID of each node is an identifier different from other nodes, and the node ID corresponds to the IP address of the node one by one.

The method for processing anycast group IDs by using the Chord algorithm will be introduced below with reference to FIG. 5 . Fig. 5 is a model diagram of processing an anycast group ID by using the Chord algorithm. In FIG. 5 , G ₁ , G ₂ , G _t , and G _k are several anycast groups among the many anycast groups on the Chord ring. Assume that there are ²³² nodes in the network, and they are in each anycast group on the Chord ring. When the routing request packet is looking for the destination node, it uses the Chord algorithm to determine the anycast group address closest to the anycast group address where the source node is located, and enters the adjacent anycast group along the NRI (Next Ring Interval, next hop in the ring) direction. Group search, and so on, can quickly find the target anycast group.

Here are several expressions in the Chord algorithm:

Entry[j].start: represents the initial position of the anycast group where the jth node is located on the Chord ring,

Entry[j].start=(n+2 ^j-1 )mod2 ³² , 1≤j≤32(1) (where n represents the offset of the jth node, that is, the position in the Chord ring, this value is already set during initialization)

Expression (1) expresses the algorithm for the location of the anycast group where the jth node is located on the Chord ring.

NRI[j]=[Entry[j].start, Entry[j+1].start], 1≤j≤32 (2)

Expression (2) expresses the ring interval between the anycast group where the j node is located and the anycast group where the next hop node is located, that is, the range of the ring covered by the jth node.

Entry[j].start→GID(G), 1≤j≤32(3) (G indicates the anycast group where the jth node is located)

Expression (3) indicates that when there is no destination node in the anycast group where node j is located, determine the anycast group address closest to the anycast group where the current node is located according to the Chord algorithm, and enter the anycast group along the NRI direction to find the destination node node.

The following describes in detail the use of the Chord algorithm to find the destination anycast group. When a source node A needs a specific service, the source node A first generates a service value, which is obtained by hashing the service key of the above service, and then the source node sends a RREQ packet carrying the service value.

When the destination node of the routing request packet is not in the same anycast group as the source node, if a forwarding node receives the RREQ, and the forwarding node is a unicast node, it does not provide any service, so it only broadcasts the value, or unicast the RREQ packet of the default anycast group ID to neighboring nodes.

When an anycast node receives the RREQ packet as a forwarding node, if the anycast node just provides the service corresponding to the service value, it sends a packet containing the IP address of the destination node and the anycast group ID of the destination node to the source node. RREP packet; if the anycast node is not the destination node and is not in the same anycast group as the destination node, then the anycast node checks the finger table of the anycast group where it is located (the finger table is a table used to maintain the Chord ring design in the Chord algorithm , from this table, you can find the neighbor nodes in the Chord ring, that is, the next hop node), and use the Chord algorithm to select an anycast group S that is closest to the current node's anycast group. Then, the anycast node checks all nodes with the same ID as the anycast group S in the routing table to determine whether there is a communication link. If there are many links, choose the one with the least number of hops, and use the destination node as the server node. If there is no such link in anycast group S, it will rebroadcast RREQ packets to its neighbor nodes to find the route to the destination node.

FIG. 6 is a diagram of a service location and discovery model provided by an embodiment of the present invention. The search for the destination anycast group using the Chord algorithm will be described in detail below in conjunction with FIG. 6 . In Figure 6, nodes E, F, and G are in the anycast group G(S ₁ ), and G(S ₁ ) provides services corresponding to service value k ₁ ; nodes I, J, and K are in the anycast group G(S _i ) , G(S _i ) provides services corresponding to the service value k _i ; nodes L, M, and N are in the anycast group G(S _t ), and G(S _t ) provides services corresponding to the service value k _t . When the unicast node A needs a specific service corresponding to the service value k _t , it unicasts to the neighboring nodes the default anycast group ID and the RREQ(k _t , Default) packet carrying the service value k _t . The RREQ(k _t , Default) packet is unicast to anycast node E via node D, and when node E finds that there is no destination node in the anycast group after searching, it determines that the nearest anycast group is S ₂ according to the Chord algorithm, and The G node sends the RREQ(k _t , S ₂ ) packet to the anycast group G(S ₂ ). By analogy, the RREQ(k _t , S _t ) packet quickly reaches the destination anycast group G(S _t ), and is routed to the destination node. After receiving the RREQ packet, the destination node sends an RREP packet carrying the IP address of the destination node and the anycast group address of the destination node to the source node in unicast mode.

Fig. 7 is a flow chart of realizing service discovery and positioning provided by an embodiment of the present invention, and the steps of the process are as follows:

Step 701: A unicast node needs a service corresponding to the service value k _t , so it broadcasts a RREQ(k _t ) packet to find a route to the destination node. After the forwarding node receives the RREQ packet, it judges whether the node is the source node, if it is the source node, go to step 702, if it is not the source node, go to step 703.

Step 702: The node broadcasts the RREQ(k _t , Default) packet of the default anycast group address.

Step 703: The node (forwarding node) receives the RREQ(k _t , Default) packet, and after searching, finds that there is no link between the node and the destination node.

Step 704: After the forwarding node updates the RREQ(k _t , Default) packet, it broadcasts it to find a route to the destination node.

Step 705: After another forwarding node receives the RREQ(k _t , Default) packet, if the node is a unicast node, proceed to step 703, and if the node is an anycast node, proceed to step 706.

Step 706: Determine whether the anycast node is in the anycast group, if it is in the anycast group, go to step 707, if not in the anycast group, go to step 708.

Step 707: After the anycast node in the anycast group receives the RREQ(k _t , Default) packet, it checks whether there is a path with the destination node through anycast in the anycast group, and finds that it does not exist, and proceeds to step 708 .

Step 708: Use the Chord algorithm to locate the anycast group where the node with the service value k _t is located. That is, the node determines the nearest anycast group address of the anycast group where the current node is located through the Chord algorithm according to the finger table of the anycast group.

Step 709: The anycast node broadcasts a RREQ(k _t , S _i+1 ) packet to search for a route to the destination node.

Step 710: After the anycast node in the anycast group S _i receives the above request packet, if it is found that the anycast group S _i is the destination anycast group, that is, the anycast node obtained according to the Chord algorithm in step 708 is the same as the current node. If the anycast group is the nearest anycast group, then go to step 711, if not, then go to step 709 after it is determined that there is no destination node in the S _i group.

Step 711: By anycasting in the group to find the destination node, judge whether there is a destination node with service value k _t in the anycast group, if yes, go to step 712, if not, go to step 708.

Step 712: the destination node sends an RREP packet with the IP address of the destination node and the corresponding anycast group ID to the source node.

Step 713: The source node determines a shortest path to the destination node according to the IP address of the destination node.

Step 714: the service discovery and location process ends.

In summary, the embodiment of the present invention realizes quickly determining the destination anycast group by establishing an anycast group in the Ad Hoc network, adding a service value and an anycast group address in the routing request packet, and searching for the corresponding anycast group through anycast routing. Nodes improve the efficiency of resource retrieval and query, balance network traffic, reduce transmission delay, improve link utilization efficiency, improve network performance, and better support peer to peer services. Therefore, invalid data retransmission can be effectively avoided, and data transmission resources and time can be saved, thereby greatly improving data transmission efficiency.

Although the present invention has been described by way of example, those of ordinary skill in the art know that there are many variations and changes in the present invention without departing from the spirit of the invention, and the claims of the application document of the present invention include these variations and changes.

Claims (9)

1, a kind of routing method for mobile multi-hop grouping wireless network based on random broadcast mode is characterized in that, described method comprises:

Source node sends a routing request packet that comprises traffic value and anycast group address, source node place;

The forward node that receives described routing request packet is searched destination node in the anycast group at this forward node place, if do not find, then adopt function algorithm to determine and the nearest anycast group of this forward node place anycast group according to the anycast group address information, and described routing request packet is sent to described nearest anycast group, in described nearest anycast group, to continue to search described destination node; By that analogy, up to finding destination node;

Set up communicating to connect of source node and destination node.

2, the method for claim 1 is characterized in that, described anycast group is made up of plurality of nodes, and each anycast group has unique anycast group address, the anycast group address of nodes sharing in each anycast group.

3, method as claimed in claim 1 or 2 is characterized in that, the traffic value that comprises in the described routing request packet is to be undertaken obtaining after the functional operation by the keyword to the business of source node request.

4, method as claimed in claim 1 or 2 is characterized in that, a plurality of adjacent anycast groups of storage address in the routing table of each node forms the anycast group address list in the anycast group.

5, method as claimed in claim 1 or 2, it is characterized in that, after described destination node is received the request package of source node, when replying source node, in the route replies bag of its transmission, comprise: the anycast group address of the IP address of destination node and destination node place anycast group with mode of unicast.

6, method as claimed in claim 1 or 2 is characterized in that, described method also comprises, when source node need communicate to connect with the destination node in the same anycast group:

If source node finds and destination node between have multilink, then source node is selected the link that jumping figure is minimum, sets up and the communicating to connect of destination node, and simultaneously destination node is stored relevant information as server node;

If source node can not find and destination node between link, source node is appointed and is broadcast a routing request packet, searches the route to destination node, each address of node and sequence number in the anycast group of storage source node place in this routing request packet.

7, method as claimed in claim 1 or 2, it is characterized in that, described destination node and source node during when routing request packet not at same anycast group, if receiving the forward node of routing request packet is the clean culture node, then this clean culture node broadcasts has the routing request packet of traffic value, or the routing request packet of the default anycast group of adjacent node address is given in clean culture.

8, method as claimed in claim 4, it is characterized in that, described destination node and source node during when routing request packet not at same anycast group, if receive the forward node of routing request packet is to appoint to broadcast node, broadcast the finger table that node is checked to comprise anycast group address list information, and adopt functional operation to determine and the described nearest anycast group address of anycast group of broadcasting the node place for described.

9, method as claimed in claim 8 is characterized in that, broadcasts node for described and checks in the routing table node in the anycast group identical with described nearest anycast group address, judges whether to exist the communication link of destination node;

If there are many links to destination node, then appoint and broadcast node and select that minimum link of jumping figure, and destination node as server node;

If there is not such link, broadcast node for then described and broadcast routing request packet again to his neighbor node, search route to destination node.

Images