Routing method for mobile infrastructureless network

• US 20040146007A1
• Filed: 01/17/2003
• Published: 07/29/2004
• Est. Priority Date: 01/17/2003
• Status: Active Grant

• Current Assignee: City College of New York
• Original Assignee: City University of New York
• Inventors: Hussein, Osama, Saadawi, Tarek
• Granted Patent: US 6,940,832 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/08 Learning-based routing, e.g. using neural networks or artificial intelligence

Abstract

The present invention provides a method for selecting and routing data in an ad-hoc mobile wireless network having a plurality of Nodes including multiple sources and destinations. The method includes sending a forward control packet from a source to the destination via at least one intermediate Node at intervals of time, where the intermediate Node is randomly selected. Each of the intermediate Nodes store weights of the neighbor Nodes. When the forward control packets reach the destination Node, they are evaluated in accordance with one or more given parameters and send back as backward control packets storing the evaluation results. As each of the intermediate Nodes receive the backward control packets, the weights of the corresponding neighbor Nodes are modified based on the stored evaluation results. Similarly, as the backward control packets are received at the source Nodes and the weights of the corresponding neighbor Nodes are modified based on the stored evaluation results. Finally, a group of routing routes to the destination are selected based on the modified weights of the neighbor Nodes and data packets are send from the source to the destination via the intermediate Nodes upon selection of the group.

Claims

1. A method for selecting a routing evaluation result in an ad-hoc mobile wireless network having a plurality of Nodes including multiple sources and destinations, comprising:

sending from a source at least one forward control packet via at least one intermediate Node to one or more destinations at intervals of time, wherein said intermediate Node is randomly selected and each of the intermediate Nodes storing weights for each of its neighbor Nodes;

evaluating each of said forward control packets at said destinations in accordance with one or more given parameters;

sending from the destination backward control packets storing evaluation results which correspond to each of the forward control packets, through the same intermediate Nodes originally traveled by the forward control packets to the source;

receiving the backward control packets at the intermediate Nodes;

modifying the weights of each of said neighbor Nodes at each of the intermediate Nodes based on the evaluation results stored in the backward control packets;

receiving said backward control packets at said source Nodes;

modifying the weights of each of said neighbor Nodes at the source Node based on the evaluation results stored in the backward control packets; and

selecting a group of routing evaluation results to said destinations via said intermediate Nodes based on the modified weights of said neighbor Nodes.

2. The method of claim 1 further comprising:

sending data packets from the sources to the destinations via said intermediate Nodes upon selection of said group of routing evaluation results.

3. The method of claim 1 further comprising:

selecting an optimal routing evaluation result to said destinations via said intermediate Nodes based on the modified weight of said neighbor Nodes.

4. The method of claim 3 further comprising:

sending data packets from the sources to the destinations via said intermediate Nodes upon the selection of the optimal routing evaluation result.

5. The method of claim 3 wherein said group of routing evaluation results are selected as next best routing evaluation results after the optimal routing evaluation result.

6. The method of claim 1 wherein said parameters include distance from the source to the destination, energy of the Nodes, bandwidth between the Nodes, signal to noise ratio between the Nodes, delay between Nodes, error rate of the packet transmission, power consumption of the links between Nodes, or combination thereof.

7. The method of claim 1 further comprising:

adding identity information and measured information of the intermediate Nodes to the forward control packets;

wherein the measured information comprises values of said parameters.

8. The method of claim 7 further comprising:

receiving from the forward control packets the identity and the information of the intermediate Nodes at said destinations; and

comparing the measured information to a reference value of the parameters.

9. The method of claim 8 wherein said reference value is constant.

10. The method of claim 8 wherein said reference value is dynamic and dependent on the measured information received from the forward control packets.

11. The method of claim 1 wherein said destination is a known destination.

12. The method of claim 1 wherein said destination is an unknown destination.

13. The method of claim 1 wherein the modified weights correspond to said destination.

14. The method of claim 1 wherein said intermediate Node is randomly selected using probability routing function.

15. The method of claim 14 wherein said probability routing function depends on said weights and local information.

16. The method of claim 15 wherein said local information include energy of the Nodes, bandwidth between the Nodes, signal to noise ratio between the Nodes, delay between Nodes, error rate of the packet transmission, power consumption of the links between Nodes, or combination thereof.

17. The method of claim 1, further comprising:

receiving a signal at the intermediate Node;

evaluating said signal and immediately upon receipt of the forward control packet at the intermediate Node, sending a negative backward control packet storing evaluation results of the signal, through the same intermediate Nodes originally traveled by the forward control packets;

receiving the negative backward control packets at the intermediate Nodes;

modifying the weights of each of said neighbor Nodes at each of the intermediate Nodes based on the evaluation results stored in the negative backward control packets;

receiving said negative backward control packets at said source Nodes; and

modifying the weights of each of said neighbor Nodes at the source Node based on the evaluation results stored in the negative backward control packets.

18. The method of claim 17 wherein said signal includes link failure, long evaluation result, loop detection, security alert, unidirectional links, or combination thereof.

19. The method of claim 1 further comprising:

sending from a destination at least one trail control packet via at least one intermediate Node at intervals of time, wherein said intermediate Node is randomly selected and each of the intermediate Nodes storing weights for each of its neighbor Nodes;

receiving the trail control packets at the intermediate Nodes; and

modifying the weights of each of the neighbor Nodes at each of the intermediate Nodes immediately upon receipt of the trail control packets at the intermediate Nodes.

20. A method for sending data in an ad-hoc mobile wireless network having a plurality of Nodes including multiple sources and destinations, comprising:

sending from a source at least one forward control packet storing the data to be routed, via at least one intermediate Node to one or more destinations at intervals of time, wherein said intermediate Node is randomly selected and each of the intermediate Nodes storing weights for each of its neighbor Nodes;

evaluating each of said forward control packets at said destinations in accordance with one or more given parameters;

sending from the destination backward control packets storing evaluation results which correspond to each of the forward control packets, through the same intermediate Nodes originally traveled by the forward control packets to the source;

receiving the backward control packets at the intermediate Nodes;

modifying the weights of each of said neighbor Nodes at each of the intermediate Nodes based on the evaluation results stored in the backward control packets;

receiving said backward control packets at said source Nodes;

modifying the weights of each of said neighbor Nodes at the source Node based on the evaluation results stored in the backward control packets; and

sending the data to said destinations via said intermediate Nodes based on criteria of said weights of the neighbor Nodes for said intermediate Node.

21. The method of claim 20 wherein said criteria comprise weights equal or greater than a predetermined value.

22. The method of claim 21 wherein said criteria comprise maximum weight.

23. The method of claim 20 wherein said parameters include distance from the source to the destination, energy of the Nodes, bandwidth between the Nodes, signal to noise ratio between the Nodes, delay between Nodes, error rate of the packet transmission, power consumption of the links between Nodes, or combination thereof.

24. The method of claim 20 further comprising:

adding identity information and measured information of the intermediate Nodes to the forward control packets;

wherein the measured information comprises values of said parameters.

25. The method of claim 24 further comprising:

receiving from the forward control packets the identity information and the measured information of the intermediate Nodes at said destinations; and

comparing the measured information to a reference value of the parameters.

26. The method of claim 25 wherein said reference value is constant.

27. The method of claim 25 wherein said reference value is dynamic and dependent on the measured information received from the forward control packets.

28. The method of claim 20 wherein said destination is a known destination.

29. The method of claim 20 wherein said destination is an unknown destination.

30. The method of claim 20 wherein the modified weights correspond to said destination.

31. The method of claim 20 wherein said intermediate Node is randomly selected using probability routing function.

32. The method of claim 31 wherein said probability routing function depends on said weights and local information.

33. The method of claim 32 wherein said local information include energy of the Nodes, bandwidth between the Nodes, signal to noise ratio between the Nodes, delay between Nodes, error rate of the packet transmission, power consumption of the links between Nodes, or combination thereof.

34. The method of claim 20 further comprising:

receiving a signal at the intermediate Node;

evaluating said signal and immediately upon receipt of the forward control packet at the intermediate Node, sending a negative backward control packet storing evaluation results of the signal, through the same intermediate Nodes originally traveled;

receiving the negative backward control packets at the intermediate Nodes;

modifying the weights of each of said neighbor Nodes at each of the intermediate Nodes based on the evaluation results stored in the negative backward control packets;

receiving said negative backward control packets at said source Nodes; and

modifying the weights of each of said neighbor Nodes at the source Node based on the evaluation results stored in the negative backward control packets.

35. The method of claim 34 wherein said signal includes link failure, long evaluation result, loop detection, security alert, unidirectional links, or combination thereof.

36. The method of claim 20 further comprising:

sending from a destination at least one trail control packet via at least one intermediate Node at intervals of time, wherein said intermediate Node is randomly selected and each of the intermediate Nodes storing weights for each of its neighbor Nodes;

receiving the trail control packets at the intermediate Nodes; and

modifying the weights of each of the neighbor Nodes at each of the intermediate Nodes immediately upon receipt of the trail control packets at the intermediate Nodes.

37. A method for sending data in an ad-hoc mobile wireless network having a plurality of Nodes including multiple sources and destinations, comprising:

sending from a source at least one forward control packet storing the data to be sent, via at least one intermediate Node to one or more destinations at intervals of time, wherein said intermediate Node is randomly selected and each of the intermediate Nodes storing weights for each of its neighbor Nodes;

evaluating each of said forward control packets at said destinations in accordance with one or more given parameters;

sending from the destination backward control packets storing evaluation results which correspond to each of the forward control packets through the same intermediate Nodes originally traveled by the forward control packets to the source;

receiving the backward control packets at the intermediate Nodes;

modifying the weight of each of said neighbor Nodes at each of the intermediate Nodes based on the evaluation results stored in the backward control packets;

receiving said backward control packets at said source Nodes; and

modifying the weights of each of said neighbor Nodes at the source Node based on the evaluation results stored in the backward control packets.

38. The method of claim 37 wherein said parameters include distance from the source to the destination, energy of the Nodes, bandwidth between the Nodes, signal to noise ratio between the Nodes, delay between Nodes, error rate of the packet transmission, power consumption of the links between Nodes, or combination thereof.

39. The method of claim 37 further comprising:

adding identity information and measured information of the intermediate Nodes to the forward control packets;

wherein the measured information comprises values of said parameters.

40. The method of claim 39 further comprising:

receiving from the forward control packets the identity information and the measured information of the intermediate Nodes at said destinations; and

comparing the measured information to a reference value of the parameters.

41. The method of claim 40 wherein said reference value is constant.

42. The method of claim 40 wherein said reference value is dynamic and dependent on the measured information received from the forward control packets.

43. The method of claim 37 wherein said destination is a known destination.

44. The method of claim 37 wherein said destination is an unknown destination.

45. The method of claim 37 wherein the modified weights correspond to said destination.

46. The method of claim 37 wherein said intermediate Node is randomly selected using probability routing function.

47. The method of claim 46 wherein said probability routing function depends on said weights and local information.

48. The method of claim 47 wherein said local information include energy of the Nodes, bandwidth between the Nodes, signal to noise ratio between the Nodes, delay between Nodes, error rate of the packet transmission, power consumption of the links between Nodes, or combination thereof.

49. The method of claim 37, further comprising:

receiving a signal at the intermediate Node;

evaluating said signal and immediately upon receipt of the forward control packet at the intermediate Node, sending a negative backward control packet storing evaluation results of the signal, through the same intermediate Nodes originally traveled;

receiving the negative backward control packets at the intermediate Nodes;

modifying the weights of each of said neighbor Nodes at each of the intermediate Nodes based on the evaluation results stored in the negative backward control packets;

receiving said negative backward control packets at said source Nodes; and

modifying the weights of each of said neighbor Nodes at the source Node based on the evaluation results stored in the negative backward control packets.

50. The method of claim 49 wherein said signal includes link failure, long evaluation result, loop detection, security alert, unidirectional links, or combination thereof.

51. The method of claim 37 further comprising:

sending from a destination at least one trail control packet via at least one intermediate Node at intervals of time, wherein said intermediate Node is randomly selected and each of the intermediate Nodes storing weights for each of its neighbor Nodes;

receiving the trail control packets at the intermediate Nodes; and

modifying the weights of each of the neighbor Nodes at each of the intermediate Nodes immediately upon receipt of the trail control packets at the intermediate Nodes.

52. A method for biasing a routing process in an ad-hoc mobile wireless network having a plurality of Nodes including multiple sources and destinations, comprising:

sending from a destination at least one trail control packet via at least one intermediate Node at intervals of time, wherein said intermediate Node is randomly selected and each of the intermediate Nodes storing weights for each of its neighbor Nodes;

receiving the trail control packets at the intermediate Nodes; and

modifying the weights of each of the neighbor Nodes at each of the intermediate Nodes immediately upon receipt of the trail control packets at the intermediate Nodes.

53. The method of claim 52 further comprising:

selecting a group of routing evaluation results to said destinations via said intermediate Nodes based on the modified weights of said neighbor Nodes.

54. The method of claim 53 further comprising:

sending data packets from the sources to the destinations via said intermediate Nodes upon the selection of said group of routing evaluation results.

55. The method of claim 52 further comprising:

selecting the optimal routing evaluation result to said destinations via said intermediate Nodes based on the modified weight of said neighbor Nodes.

56. The method of claim 55 further comprising:

sending data packets from the sources to the destinations via said intermediate Nodes upon the selection of the optimal routing evaluation result.

57. The method of claim 52 further comprising:

sending the data to said destinations via said intermediate Nodes based on criteria of said weights of the neighbor Nodes for said intermediate Node.

58. The method of claim 57 wherein said criteria comprise weights equal to or greater than a value.

59. The method of claim 57 wherein said criteria comprise maximum weight.

60. The method of claim 52 further comprising:

sending from a source at least one forward control packet storing the data to be sent, via at least one intermediate Node to one or more destinations at intervals of time, wherein said intermediate Node is randomly selected and each of the intermediate Nodes storing weights for each of its neighbor Nodes.