PATH DISCOVERY AND MESSAGE TRANSFER IN PARTIALLY CONNECTED MOBILE AD HOC NETWORKS

• US 20090046603A1
• Filed: 10/21/2008
• Published: 02/19/2009
• Est. Priority Date: 09/17/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Qian, Tan, Kun, Zhu, Wenwu
• Granted Patent: US 8,228,927 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04L 67/564 Enhancement of application control based on intercepted application data
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 92/02 Inter-networking arrangements
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A method and system is presented for path discovery and asynchronous message transfer in a partially connected middleware communication space comprising mobile ad hoc networks. Embodiments of the present invention use mobile devices to bridge separated islands of networks and store and propagate messages. The system and software architecture supports methods for routing, messaging caching, and transferring. More specifically, embodiments provide methods and systems that extend a communication space concept into a distributed environment and combine it with the standard Web Services technologies, i.e., SOAP, and WS series protocols. The communication space provides an extension of Web Services to mobile ad hoc networks and provides asynchronous message caching, transferring and routing.

Claims

1. A method for a mobile device to perform as a messaging bridge between two or more networks in a dynamically changing ad-hoc topology, the method comprising:

performing discovery to determine one or more neighboring mobile devices according to a listen and announce protocol;

maintaining storage for metadata including storage for an expected path length;

choosing a neighbor device for receipt of one or more messages, the choosing comprising;

deriving a stochastic model of the dynamically changing topology wherein the mobile device is a node in the topology;

using a stochastic model, evaluating routes for delivering the messages according to the expected path length, and assigning a probabilistic weight representing a probability of a connection between two nodes in the topology;

determining a shortest expected path route from the evaluated routes; and

delivering messages to another device to propagate messages between the networks.

2. The method of claim 1, wherein the expected path length from a source to a destination over time t is an expected time defined by

$E$

( T ) = E path = ∑

t = 1 ∞



t ·

∏

( t )

where Π

is a distribution of probability that d receives the message and Π

is determined by the topology of the stochastic network model.

3. The method of claim 1, wherein the effective path length is reset to infinite when the device receives a new message.

4. The method of claim 1, further comprising purging a cache of messages having a high probability of delivery.

5. The method of claim 1, further comprising determining an expected path length of a primary path using equation

$E_{\mathrm{path}}\approx$

E primary = ∑

i ∈

P primary 

1 p i

where p_i is the connection probability of link i on the primary path.

6. A method of transferring messages between communication networks via a mobile device in an ad-hoc topology, the method comprising:

discovering one or more neighboring mobile devices;

determining and storing an expected path length;

choosing a neighbor device for receipt of one or more messages;

determining a shortest expected path route from the evaluated routes; and

delivering messages to the neighboring device to propagate messages between the networks.

7. The method of claim 6, wherein the discovering comprises a listen and announce protocol.

8. The method of claim 6, wherein the expected path length is set to infinite when the device receives a new message.

9. The method of claim 6, wherein the expected path length is updated to the expected path length from the target device to the destination of the message.

10. The method of claim 6, wherein the choosing comprises:

deriving a stochastic model of the dynamically changing topology wherein the mobile device is a node in the topology; and

using the stochastic model to evaluate routes for delivering the messages according to the expected path length.

11. The method of claim 10, wherein the choosing further comprises assigning a probabilistic weight representing a probability of a connection between two nodes in the topology.

12. A computer readable medium having computer executable code thereon to perform acts that enable a mobile device to route messages between communication networks via a mobile device in an ad-hoc topology, the acts comprising:

discovering one or more neighboring mobile devices and/or communication networks;

determining an expected path length and a shortest expected path route from a set of evaluated routes; and

choosing a neighbor device and/or communication network for receipt of one or more messages;

delivering messages to the neighboring device and/or communication network.

13. The computer readable medium of claim 12, wherein discovering comprises a listen and announce protocol.

14. The computer readable medium of claim 12, wherein the choosing comprises:

deriving a stochastic model of the topology including mobile device nodes and communication network nodes; and

using the stochastic model to evaluate routes for delivering the messages according to the expected path length.

15. The computer readable medium of claim 14, wherein the choosing further comprises assigning a probabilistic weight representing a probability of a connection between two nodes in the topology.

16. The computer readable medium of claim 12, wherein the expected path length from a source to a destination over time t is an expected time defined by

$E$

( T ) = E path = ∑

t = 1 ∞



t ·

∏

( t )

where Π

is a distribution of probability that d receives the message and Π

is determined by the topology of the stochastic network model.

17. The computer readable medium of claim 12, wherein the effective path length is reset to infinite when the device receives a new message.

18. The computer readable medium of claim 12, wherein the effective path length on a source device is updated to the expected path length from the target device to the destination of the message.

19. The computer readable medium of claim 12, further comprising purging a cache of messages having a high probability of delivery.

20. The computer readable medium of claim 12, further comprising determining an expected path length of a primary path using equation

$E_{\mathrm{path}}\approx$

E primary = ∑

i ∈

P primary 

1 p i

where p_i is the connection probability of link i on the primary path.