Path discovery and message transfer in partially connected mobile ad hoc networks

• US 8,228,927 B2
• Filed: 10/21/2008
• Issued: 07/24/2012
• Est. Priority Date: 09/17/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tan, Kun, Zhu, Wenwu, Zhang, Qian
• Primary Examiner(s): Phan, M.
• Application Number:
  US12/255,406
• Publication Number:
  US 20090046603A1
• Time in Patent Office: 1,372 Days
• Field of Search: 370229-351, 370401-428, 709224-243, 455418-445
• US Class Current: 370/401
• 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 computer-implemented 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, the expected path length from a source node to a destination node over time is an expectation time defined by a pair of the source node and the destination node, such that the source node sends a message at time 0, and a distribution of probability that the destination node receives the message is determined by a topology of a stochastic model;

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

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

using the 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, where the path with the shortest expected path length is the primary path;

delivering messages to another device to propagate messages between the networks; and

purging a cache of messages having a high probability of delivery.

2. The computer-implemented method of claim 1, wherein the expected path length is reset to infinite when the mobile device receives a new message.

3. The computer-implemented method of claim 1, further comprising determining an expected path length of the primary path using equation

4. A computer-implemented 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;

evaluating routes for delivering the message according to an expected path length, the expected path length from a source s to a destination d over time t is an expectation time defined by a pair of nodes <

s,d>

, the node s sends a message at time 0, and a distribution of probability that d receives the message, represented as Π

, where Π

is determined by a topology of a stochastic model;

storing the expected path length;

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

determining a shortest expected path route from the evaluated routes;

delivering messages to the neighboring mobile device to propagate messages between the networks, wherein the topology of the networks dynamically vary; and

purging a cache of messages having a high probability of delivery.

5. The computer-implemented method of claim 4, wherein the discovering comprises a listen and announce protocol.

6. The computer-implemented method of claim 4, wherein the expected path length is set to infinite when the mobile device receives a new message.

7. The computer-implemented method of claim 4, wherein the expected path length is updated to the expected path length from the neighboring mobile device to the destination of the message.

8. The computer-implemented method of claim 4, wherein the choosing comprises:

deriving the 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.

9. The computer-implemented method of claim 8, wherein the choosing further comprises assigning a probabilistic weight representing a probability of a connection between two nodes in the topology.

10. A computer readable storage device 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, the expected path length from a source s to a destination d over time t is an expectation time defined by a pair of nodes <

s,d>

, the node s sends a message at time 0, and a distribution of probability that d receives the message, represented as Π

, where Π

is determined by a topology of a stochastic model;

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

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

11. The computer readable storage device of claim 10, wherein discovering comprises a listen and announce protocol.

12. The computer readable storage device of claim 10, wherein the choosing comprises:

deriving the 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.

13. The computer readable storage device of claim 12, wherein the choosing further comprises assigning a probabilistic weight representing a probability of a connection between two nodes in the topology.

14. The computer readable storage device of claim 10, wherein the effective path length is reset to infinite when the mobile device receives a new message.

15. The computer readable storage device of claim 10, 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.

16. The computer readable storage device of claim 10, further comprising purging a cache of messages having a high probability of delivery.

17. The computer readable storage device of claim 10, further comprising determining an expected path length of a primary path using equation