Method and device for implementing ad hoc network routing protocol in multi-agent system

Patent metadata

Field	Value
Publication number	US-11576102-B2
Application number	US-202217747574-A
Country	US
Kind code	B2
Filing date	May 18, 2022
Priority date	May 18, 2021
Publication date	Feb 7, 2023
Grant date	Feb 7, 2023

Abstract

Disclosed are a method and device for implementing an ad hoc network routing protocol in a multi-agent system. The device includes a trajectory information acquisition module, a data packet delivery module, a delivery confirmation module, a data packet forwarding module, a data transmission feedback module and a data storage module. The method includes: acquiring a separation and rendezvous timing table and an adjacency matrix of an ad hoc network composed of multiple agents at a given moment; if a source node has message sending requirement, performing data packet delivery and delivery confirmation based on the separation and rendezvous timing table and the adjacency matrix; and performing data packet forwarding and transmission status feedback by a non-source node.

First claim

What is claimed is:

1. A device for implementing an ad hoc network routing protocol in a multi-agent system (MAS), comprising:
a trajectory information acquisition module;
a data packet delivery module;
a delivery confirmation module;
a data packet forwarding module;
a data transmission feedback module; and
a data storage module;
wherein the trajectory information acquisition module, the data packet delivery module, the delivery confirmation module, the data packet forwarding module, the data transmission feedback module and the data storage module are arranged at each of a plurality of nodes of the MAS;
the trajectory information acquisition module is configured to obtain a separation and rendezvous timing table and an adjacency matrix of an ad hoc network of the multi-agent system at a given moment; the separation and rendezvous timing table is configured to record a separation moment and a rendezvous moment of each node in the ad hoc network; and the adjacency matrix is configured to record a communication link between the plurality of nodes;
when a current node has message sending requirement, a corresponding data packet delivery module is called; the data packet delivery module is configured to read the separation and rendezvous timing table to determine whether the current node is capable of rendezvousing with a destination node within a message validity period; if not, the data packet delivery module is configured to notify the current node to cancel a sending task; otherwise, the data packet delivery module is configured to read the adjacency matrix to determine whether there is a path from the current node to the destination node within the message validity period; if not, the data packet delivery module is configured to notify the current node to cancel the sending task; otherwise, the data packet delivery module is configured to find an optimal path from the current node to the destination node within the message validity period, add the optimal path to a packet header of a to-be-sent data packet, send the to-be-sent data packet at a moment when the destination node is reachable, and store the to-be-sent data packet in the data storage module of the current node;
the delivery confirmation module is configured to determine whether to redeliver the to-be-sent data packet within the message validity period according to whether a route reply (RREP) packet back fed back by the destination node or a route error (RRER) packet fed back by an intermediate node is received after the current node sends the to-be-sent data packet;
the delivery confirmation module is configured to notify the current node that the to-be-sent data packet has been delivered when receiving the RREP packet fed back by the destination node within a predetermined period; if the RREP packet fed back by the destination node is not received within the predetermined period but the RRER packet fed back by the intermediate node has been received within the message validity period, the delivery confirmation module is configured to remove an error node and notify the data packet delivery module to re-generate an optimal path from the current node to the destination node, and resend the to-be-sent data packet, wherein the error node is a next hop node of the intermediate node; and if the RRER packet fed back by the intermediate node is not received within the message validity period, the delivery confirmation module is configured to remove a next hop node of the current node and notify the data packet delivery module to re-generate an optimal path and resend the to-be-sent data packet;
the data packet forwarding module is configured to perform packet forwarding according to a packet type recorded in a packet header of a packet received by the current node; if the data packet is a control packet, the data packet forwarding module is configured to directly forward the data packet based on a reverse path of a store path in the packet header of the data packet, wherein the control packet is the RREP packet or the RRER packet; and if the data packet is a data packet, the data packet forwarding module is configured to forward the data packet based on routing hop count and routing node address recorded in the packet header of the data packet and store the packet header of the data packet in the data storage module of the current node;
the data transmission feedback module is configured to feed data transmission status back to a source node after the current node receives a data packet; if the current node is the destination node, the data transmission feedback module is configured to feed the RREP packet back to the source node based on the reverse path of a stored path in a packet header of the data packet; and if the current node is not the destination node, and a control packet fed back by a successor node is not received within the predetermined period after forwarding the data packet, the data transmission feedback module is configured to feed the RRER packet to the source node based on the reverse path of a stored path in a packet header of a data packet forwarded and stored in the data storage module; and
the data storage module is configured to store the to-be-sent data packet of the current node and the packet header of the data packet forwarded by the current node.

2. The device of claim 1 , wherein the packet header of the to-be-sent data packet and the packet header of the data packet forwarded are set to comprise a Hop field, a Seq field, a Type field and an Address field;
wherein the Hop field indicates the number of routing node hops experienced when delivering the to-be-sent data packet and the to-be-forwarded data packet along the optimal path;
the Seq field indicates a sequence number of a data packet generated by the source node and sent to the destination node, and is configured to identify individual data packets;
the Type field indicates a type of the received packet, and is configured to distinguish the data packet, the RREP packet and the RRER packet; and
the Address field indicates all nodes on the optimal path from the source node to the destination node, and is configured to store an IP address of each node and a cascaded string cascade uniquely identifying each node.

3. The device of claim 2 , wherein every time the current node forwards a data packet, the data transmission feedback module is configured to correspondingly start a control packet wait timer; if the control packet fed back by a successor node on a transmission path of the data packet has not been received when the control packet wait timer expires, the data transmission feedback module is configured to feed the RRER packet to the source node; otherwise, the data transmission feedback module is configured to turn off the control packet wait timer.

4. The device of claim 2 , wherein the separation and rendezvous timing table is configured to record a separation moment and a rendezvous moment of each node set in the ad hoc network; and nodes in the same node set are capable of communicating with each other.

5. The device of claim 1 , wherein every time the current node forwards a data packet, the data transmission feedback module is configured to correspondingly start a control packet wait timer; if the control packet fed back by a successor node on a transmission path of the data packet has not been received when the control packet wait timer expires, the data transmission feedback module is configured to feed the RRER packet to the source node; otherwise, the data transmission feedback module is configured to turn off the control packet wait timer.

6. The device of claim 1 , wherein in the data storage module, the to-be-sent data packet comprises the destination node, a sequence number of the to-be-sent data packet, a storage validity period of

Assignees

• Univ Beijing Posts & Telecomm

Inventors

• Yang Shaoshi
• Hu Die
• Ma Zhao
• Ma Jun
• Wen Yonglu
• Gong Min
• Zhu Xuejun

Classifications

• H04W84/18

  Self-organising networks, e.g. ad-hoc networks or sensor networks · CPC title

• H04W40/026 Primary

  Route selection considering the moving speed of individual devices · CPC title

• H04W40/20

  based on geographic position or location · CPC title

• H04W40/02 Primary

  Communication route or path selection, e.g. power-based or shortest path routing · CPC title

• H04W40/248

  Connectivity information update · CPC title