Methods, systems, and computer readable media for topology management and geographic routing in mobile ad-hoc networks

Patent metadata

Field	Value
Publication number	US-9832705-B1
Application number	US-201615256192-A
Country	US
Kind code	B1
Filing date	Sep 2, 2016
Priority date	Sep 2, 2016
Publication date	Nov 28, 2017
Grant date	Nov 28, 2017

Abstract

Methods, systems, and computer readable media for topology management and geographic routing in mobile ad-hoc networks are disclosed. One method for geographic routing in mobile ad-hoc networks includes receiving a first packet requiring routing at a first mobile node configured to operate in a mobile ad-hoc network where the first mobile node and other mobile nodes move relative to each other and are connected using directional wireless communications links. The method also includes performing greedy routing for the first packet, and in response to determining that no next hop neighbor node is closer to the destination than the first mobile node, performing face routing of the first packet, wherein performing greedy routing or face routing includes storing local topology information at the mobile nodes and using the local topology information when making routing decisions.

First claim

What is claimed is:

1. A method for geographic routing in mobile ad-hoc networks,
the method comprising:
receiving a first packet requiring routing at a first mobile node configured to operate in a mobile ad-hoc network where the first mobile node and other mobile nodes move relative to each other and are connected using directional wireless communications links;
performing greedy routing for the first packet, wherein performing greedy routing includes determining whether a next hop neighbor node of the first mobile node is closer to a destination for the first packet and, in response to determining that the next hop neighbor node is closer to the destination for the first packet, forwarding the first packet to the next hop neighbor node;
in response to determining that no next hop neighbor node is closer to the destination than the first mobile node, performing face routing of the first packet, wherein performing face routing includes advancing from the first mobile node through nodes along a face boundary of a planar graph until a face routing early termination condition is met, the first mobile node is reached, or the destination is reached;
wherein performing greedy routing further comprising using local topology information at the mobile nodes; and
wherein performing face routing further comprises using the local topology information at the mobile nodes, wherein the local topology information at a second mobile node includes positions and identifiers of nodes directly connected to the second mobile node at different times, wherein the nodes directly connected to the second mobile node at a current time are different than the nodes directly connected to the second mobile node at the time face routing began, wherein the local topology information at the second mobile node is usable for making a routing decision at the second mobile node based on the nodes directly connected to the second mobile node at the time face routing began.

2. The method of claim 1 wherein using the local topology information comprises:
at the second mobile node along the face boundary:
receiving the first packet, wherein the first packet indicates the time at which the face routing began; and
using the time in the first packet and the positions and identifiers to determine a next node to be visited along the face boundary at the time at which face routing began.

3. The method of claim 2 comprising:
at the second mobile node along the face boundary:
determining that the next node along the face boundary at the time at which the face routing began is not currently connected to the first mobile node;
in response to determining that the next node along the face boundary is not currently connected to the first mobile node, adding additional header information to the first packet indicating the next node along the face boundary as a provisional destination for the first packet; and
routing to the next node along the face boundary before removing the additional header information and continuing face routing towards the original destination.

4. The method of claim 1 comprising:
at the second mobile node along the face boundary:
determining whether, in a projection of the nodes and connections onto a 2-dimensional plane, a line segment from the projection of the first mobile node to the projection of the destination intersects a second line segment from the projection of the second mobile node to the projection of a next node to be visited along the face boundary; and
in response to determining that the line segment intersects the second line segment, restarting face routing from the second mobile node.

5. The method of claim 1 wherein the directional wireless communications links use radio frequency (RF) or free-space optics (FSO) technology.

6. The method of claim 1 wherein using the local topology information includes utilizing the local topology information for determining a direction to begin the face routing, a size of a bounding circle, or the next hop for greedy routing.

7. The method of claim 6 wherein the local topology information includes node position information received via automatic dependent surveillance—broadcast (ADS-B).

8. The method of claim 1 wherein the first mobile node performs topology management using a degree-constrained planar topology management algorithm.

9. The method of claim 8 wherein the degree constrained planar topology management algorithm includes a degree-constrained planar Kruskal (DCP-Kruskal) algorithm, a DCP-Kruskal plus long algorithm (DCP-Kruskal+L), a DCP-Kruskal plus short algorithm (DCP-Kruskal+S), a degree-constrained planar tree-based reliable topology plus long (DCP-TRT+L) algorithm, a degree-constrained Gabriel graph algorithm (DCP-GG), or a Gabriel graph plus long algorithm (DCP-GG+L).

10. A system for geographic routing in mobile ad-hoc networks,
the system comprising:
a first mobile node comprising:
at least one memory;
at least one processor; and
a routing module (RM) implemented using the at least one processor and the at least one memory, wherein the RM is configured for:
receiving a first packet requiring routing at the first mobile node configured to operate in a mobile ad-hoc network where the first mobile node and other mobile nodes move relative to each other and are connected using directional wireless communications links;
performing greedy routing for the first packet, wherein performing greedy routing includes determining whether a next hop neighbor node of the first mobile node is closer to a destination for the first packet and, in response to determining that the next hop neighbor node is closer to the destination for the first packet, forwarding the first packet to the next hop neighbor node;
in response to determining that no next hop neighbor node is closer to the destination than the first mobile node, performing face routing of the first packet, wherein performing face routing includes advancing from the first mobile node through nodes along a face boundary of a planar graph until a face routing early termination condition is met, the first mobile node is reached, or the destination is reached;
wherein performing greedy routing further comprising using local topology information at the mobile nodes; and
wherein performing face routing further comprises using the local topology information at the mobile nodes, wherein the local topology information at a second mobile node includes positions and identifiers of nodes directly connected to the second mobile node at different times, wherein the nodes directly connected to the second mobile node at a current time are different than the nodes directly connected to the second mobile node at the time face routing began, wherein the local topology information at the second mobile node is usable for making a routing decision at the second mobile node based on the nodes directly connected to the second mobile node at the time face routing began.

11. The system of claim 10 wherein using the local topology information comprises:
at the second mobile node along the face boundary:
receiving the first packet, wherein the first packet indicates the time at which the face routing began; and
using the time in the first packet and the positions and identifiers to determine a next node to be visited along the face boundary at the time at which face routing began.

12. The system of claim 11 comprising:
at the second mobile node along the face boundary:
determining that the next node along the face boundary at the time at which the face routing began is not currently connected to the first mobile node;
in response to determining that the next node along th

Assignees

• Univ North Carolina Chapel Hill

Inventors

• Newton Benjamin
• Jeffay Kevin
• Aikat Jayashree

Classifications

• H04W84/18

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

• H04W28/021

  in wireless networks with changing topologies, e.g. ad-hoc networks (self-organizing networks H04W84/18) · CPC title

• H04W40/20 Primary

  based on geographic position or location · CPC title

• H04W40/24

  Connectivity information management, e.g. connectivity discovery or connectivity update · CPC title