Methods systems, and devices for robustness improvement in a mobile ad hoc network using reputation-based routing

• US 8,774,192 B2
• Filed: 09/10/2012
• Issued: 07/08/2014
• Est. Priority Date: 09/10/2011
• Status: Expired due to Fees

• Current Assignee: Arnab Das, Santanu Das
• Original Assignee: Arnab Das, Santanu Das
• Inventors: Das, Arnab, Das, Santanu
• Primary Examiner(s): Zhu, Alvin A
• Application Number:
  US13/608,738
• Publication Number:
  US 20130094398A1
• Time in Patent Office: 666 Days
• Field of Search: 370/255, 370/395.2, 370/395.21, 370/395.3, 370/395.31, 370/395.32
• US Class Current: 370/395.21
• CPC Class Codes: H04B 7/15507 Relay station based processing for cell extension or control of coverage area, network planning with network coordinated processing with regard to cell extension H04W16/26; network topologies using dedicated repeater stations H04W84/047; terminal devices adapted for relaying to or from an other terminal H04W88/04
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04W 12/102 Route integrity, e.g. using trusted paths
• CPC Class Codes: H04W 24/04 Arrangements for maintaining operational condition
• CPC Class Codes: H04W 40/04 based on wireless node resources
• CPC Class Codes: H04W 40/06 based on characteristics of available antennas
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Aspect of the present disclosure include A Mobile Ad Hoc Network (MANET) in which an intermediate relay node may engage in discreet packet-dropping practices for selfish (e.g., to conserve power) or other reasons. Each node in such a MANET has a dynamic reputation level known to all other nodes. Embodiments include improving the overall performance or robustness of such a MANET by adopting a routing strategy (e.g. routing protocol) which considers the reputation levels of intermediate relaying nodes in determining the best route from a source to a destination. Embodiments of the present disclosure also include a system for discovering a route between two nodes in a communication network. One or more nodes: (i) determine a reputation level of each neighboring node; (ii) sending a route discovery message that is addressed to the destination node to one neighboring node having a highest reputation level.

Claims

1. A method for sending data packets from any source node to any destination node in a communication network having a plurality of nodes, the method comprising:

(a) measuring recent packet delivery performance of each node in the communication network by every other node;

(b) determining reputation level of each node by every other node based on the measured recent packet delivery performance wherein the measuring of recent packet delivery performance is based on one or more node characteristics;

(c) sending a route discovery message from a source node to a destination node through a neighboring node having a highest reputation level;

(d) sending the route discovery message by each intermediate node between the source node and the destination node to the neighboring node that has the highest reputation level until the route discovery message is received by the destination node resulting in determining a set of highest reputation level intermediate nodes between the source node and destination node;

(e) sending data packets from the source node to the destination node through the determined one or more intermediate nodes of highest reputation level.

2. The method of claim 1, wherein if two or more neighboring nodes have equal, highest reputation level, then the node arbitrarily sends the route discovery message to one of the two or more neighboring nodes.

3. The method of claim 1, wherein the sending of the route discovery message to one neighboring node is based on a reputation threshold.

4. The method of claim 3, further comprising determining the reputation threshold for a node based on one or more node characteristics.

5. The method of claim 1, wherein the sending the route discovery message to a neighboring node is based on using a modification of a protocol that uses route discovery message to be sent from the source node to the destination node to determine the intermediate nodes for relaying data packets from the source node to the destination node.

6. The method of claim 5, wherein the protocol is selected from the group consisting of ad-hoc on demand distance vector protocol (AODV), dynamic source routing protocol (DSR), spanning tree based routing protocol, Destination Sequenced Distance Vector Protocol (DSDV), Location-Aided Routing (LAR) and any combination thereof.

7. The method of claim 1, wherein the one or more node characteristics of recent packet delivery performance is selected from the group consisting of recent packet loss rate, recent packet dropping rate, recent buffer overflow rate, recent bit error rate, recent traffic loading, recent power consumption, recent memory capacity, recent quality associated with outgoing wireless links, recent packet forwarding rate, recent residual energy level, and any combination thereof.

8. The method of claim 1, wherein the measuring of recent packet delivery performance is based on one or more network characteristics wherein the one or more network characteristics is selected from the group consisting of network size requirement, mean network throughput requirement, delay requirement, latency requirement, mean packet size, bit error rate requirement, jitter characteristics, and any combination thereof.

9. The method of claim 1, wherein the communication network is selected from the group consisting of a mobile ad-hoc network, a wireless network, a cellular network, an Internet Protocol-based network, wireless sensor network, wireless mesh network, wireline network, WiFi network, fixed network and any combination thereof.

10. A system for sending data packets from any source node to any destination node in a communication network having a plurality of nodes, the system comprising:

a source node;

a destination node;

one or more intermediate nodes coupled to the source node and the destination node through the communication network;

wherein;

(a) each node measures recent packet delivery performance of every other node in the communication network;

(b) each node determines reputation level of every other node based on the measured recent packet delivery performance wherein the measuring of recent packet delivery performance is based on one or more node characteristics;

(c) each node sends a route discovery message to the destination node through a neighboring node having highest reputation level wherein sending of the route discovery message is repeated by each intermediate node between the source node and the destination node to the a neighboring node that has the highest reputation level until the route discovery message is received by the destination node resulting in determining a set of highest reputation level intermediate nodes between the source node and destination node;

(d) each node sends data packets to the destination node through the determined one or more intermediate nodes of highest reputation level.

11. The system of claim 10, wherein if two or more neighboring nodes have equal, highest reputation level, then the source node and the one or more intermediate nodes arbitrarily sends the route discovery message to one of the two or more neighboring nodes.

12. The system of claim 10, wherein sending of the route discovery message to one neighboring node is based on a reputation threshold.

13. The system of claim 12, wherein determining the reputation threshold for a node is based on one or more node characteristics.

14. The system of claim 10, wherein sending the route discovery message to a neighboring node is based on using a modification of a protocol that uses route discovery message to be sent from the source node to the destination node to determine the intermediate nodes for relaying data packets from the source node to the destination node.

15. The system of claim 14, wherein the protocol is selected from the group consisting of ad-hoc on demand distance vector protocol (AODV), dynamic source routing protocol (DSR), spanning tree based routing protocol, Destination Sequenced Distance Vector Protocol (DSDV), Location-Aided Routing (LAR) and any combination thereof.

16. The system of claim 10, wherein the one or more node characteristics of recent packet delivery performance is selected from the group consisting of recent packet loss rate, recent packet dropping rate, recent buffer overflow rate, recent bit error rate, recent traffic loading, recent power consumption, recent memory capacity, recent quality associated with outgoing wireless links, recent packet forwarding rate, recent residual energy level, and any combination thereof.

17. The system of claim 10, wherein the measuring of recent packet delivery performance is based on one or more network characteristics wherein the one or more network characteristics is selected from the group consisting of network size requirement, mean network throughput requirement, delay requirement, latency requirement, mean packet size, bit error rate requirement, jitter characteristics, and any combination thereof.

18. The system of claim 10, wherein the communication network is selected from the group consisting of a mobile ad-hoc network, a wireless network, a cellular network, an Internet Protocol-based network, wireless sensor network, wireless mesh network, wireline network, WiFi network, fixed network and any combination thereof.

19. A node device for sending data packets from any source node to any destination node in a communication network, the node device comprising:

a storage device;

one or more communication interfaces coupled to the communication network;

a processor coupled to the one or more communication interfaces and the storage device;

wherein the node using the processor;

(a) measures recent packet delivery performance of each node in the communication network;

(b) determines reputation level of each node based on the measured recent packet delivery performance wherein the measuring of recent packet delivery performance is based on one or more node characteristics;

(c) sends a route discovery message to a destination node through a neighboring node having highest reputation level and a set of highest reputation level intermediate nodes;

(d) sends data packet to the destination node through the determined neighboring node and one or more intermediate nodes of highest reputation level.

20. The node device of claim 19, wherein if two or more neighboring nodes have equal, highest reputation level, then the node arbitrarily sends the route discovery message to one of the two or more neighboring nodes.

21. The node device of claim 19, wherein sending of the route discovery message to one neighboring node is based on a reputation threshold.

22. The node device of claim 21, wherein the node using the processor determines the reputation threshold based on one or more node characteristics.

23. The node device of claim 19, wherein sending the route discovery message to a neighboring node is based on using a modification of a protocol that uses route discovery message to be sent from the source node to the destination node to determine the intermediate nodes for relaying data packets from any source node to any destination node.

24. The node device of claim 23, wherein the protocol is selected from the group consisting of ad-hoc on demand distance vector protocol (AODV), dynamic source routing protocol (DSR), spanning tree based routing protocol, Destination Sequenced Distance Vector Protocol (DSDV), Location-Aided Routing (LAR) and any combination thereof.

25. The node device of claim 19, wherein the one or more node characteristics of recent packet delivery performance is selected from the group consisting of recent packet loss rate, recent packet dropping rate, recent bit error rate, recent buffer overflow rate, recent traffic loading, recent power consumption, recent memory capacity, recent quality associated with outgoing wireless links, recent packet forwarding rate, recent residual energy level, and any combination thereof.

26. The node device of claim 19, wherein the measuring of recent packet delivery performance is based on one or more network characteristics wherein the one or more network characteristics is selected from the group consisting of network size requirement, mean network throughput requirement, delay requirement, latency requirement, mean packet size, bit error rate requirement, jitter characteristics, and any combination thereof.

27. The node device of claim 19, wherein the communication network is selected from the group consisting of a mobile ad-hoc network, a wireless network, a cellular network, an Internet Protocol-based network, wireless sensor network, wireless mesh network, wireline network, WiFi network, fixed network and any combination thereof.