Opportunistic wireless mesh network methods

• US 7,760,649 B2
• Filed: 09/21/2007
• Issued: 07/20/2010
• Est. Priority Date: 09/22/2006
• Status: Active Grant

• Current Assignee: Sennet Communications
• Original Assignee: Sennet Communications
• Inventors: Song, Liang
• Primary Examiner(s): Nguyen; Brian D
• Application Number:
  US11/902,411
• Publication Number:
  US 20080075010A1
• Time in Patent Office: 1,033 Days
• Field of Search: 370/238, 370/238.1, 370/338, 370/390, 370/432, 370/252, 370/328, 370/329, 370/311, 370/312, 370/392
• US Class Current: 370/238
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• 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

The invention relates to opportunistic wireless mesh networks which operate under random networking conditions. Such random network conditions typically limit the effectiveness of prior art wireless mesh networks, and more particularly to those supporting low power devices within the wireless network. Random network conditions include: random power supply, random node distribution, random node mobility, high mobility of nodes, random wireless link fluctuations, and random application traffic. The opportunistic wireless mesh network utilizes a two-layer architecture Embedded Wireless Interconnect (EWI) framework, which is adopted as the architecture reference model. A mesh network according to the invention supports opportunistically determining both mesh interconnections and network transmission routes by providing nodes with broadcast modules and unicast modules. The methods provide novel low power opportunistic wireless mesh networks that support interconnection with existing network infrastructures such as Open System Interconnect (OSI) based wired or wireless networks. Network embodiments provide protocol translation at network borders to allow micro- and macro-mobility management for wireless devices and their associated users. Additionally embodiments of the opportunistic wireless mesh networks address reduction in power consumption.

Claims

1. A method of opportunistic data communications comprising the steps of:

providing a data packet to a first node for transmission therefrom, the first node being identified by a first address;

providing a plurality of second nodes;

each second node being identified by a second address;

providing an indication of the destination address of the data packet;

determining at least an indication of a cost of data delivery to each second node within a current subset of the plurality of second nodes;

determining opportunistically for the data packet whether to at least one of broadcast and unicast from the first node;

wherein,

upon determining to broadcast from the first node;

broadcasting the data packet upon at least a wireless channel;

and upon determining to unicast from the first node;

determining opportunistically at least one second node of the current subset of the plurality of second nodes to transmit the data packet to based upon a predetermined cost decision; and

transmitting the data packet from the first node to the at least one second node upon at least a wireless channel.

2. A method of opportunistic data communications according to claim 1 wherein;

determining opportunistically to at least one of broadcast and unicast comprises determining opportunistically for each data packet in dependence upon at least a transmission criteria, the transmission criteria being at least one of establishing with the first node of a second address of at least one of the plurality of second nodes, establishing the cost of data delivery to at least one of the plurality of second nodes, receiving an acceptable wireless status of at least one of the plurality of second nodes, the first node address, the destination address, and receiving a management command.

3. A method of opportunistic data communications according claim 1 wherein;

determining opportunistically the at least one second node comprises determining the at least one node in dependence upon at least updating the cost of data delivery to the current subset of second nodes and selecting the lowest cost of data delivery.

4. A method of opportunistic data communications according to claim 1 wherein;

determining at least one of the cost of delivery and predetermined cost decision comprises determining the at least one of in dependence upon at least one of a first characteristic and a second characteristic, wherein

the first characteristic relates at least one of the first and second nodes and is selected from the group comprising available battery power, size of the data packet to be transmitted, a measure of direction of movement of the node relative to another node of the current subset of second nodes, a measure of velocity relative to the other second node of the current subset of second nodes, and an indication that the cost of next data delivery from the one second node to another second node of the plurality of second nodes is lower than or equal to the cost of the data delivery from the first node to the one second node; and

the second characteristic relates to a transceiver associated with one of the first and second nodes and is selected from the group comprising maximum potential output power of the transceiver, current output power setting, and transmission speed.

5. A method of opportunistic data communications according to claim 1 wherein;

providing an address for a node comprises determining an address for the node in dependence upon at least one of physical location coordinates of the node, a triangulation from a known set of landmarks, an application specific parameter, from data provided by a global positioning system, a number of relay hops to a landmark, an application specific parameter updated by an application running on a system layer of the node, a measure of mobility of the node, and for every data packet to be transmitted.

6. A method of opportunistic data communications according to claim 1 wherein;

determining the indication of the cost of data delivery to a second node comprises determining the cost of data delivery in dependence upon at least applying a formula comprising at least a term varying in dependence of a node characteristic, the node characteristic selected from a group comprising the first address, the second address, a measure of distance between the first node and second node, the destination address, a measure of distance between the second address and the destination address, the number of hops to at least one of a landmark and the destination, a wireless channel status indicator of the second node, and a response time of the second node to a request to send control message from the first node.

7. A method of opportunistic data communications according to claim 1 wherein;

providing at least one of the first node and a second node comprises providing a transceiver, the transceiver providing at least one of a broadcast capability and a unicast capability and having at least one of a fixed output power and a variable output power, the variable output power determined in dependence upon at least one of a measure of quality of service, the cost of data delivery to the opportunistically determined at least one second node, and the predetermined cost decision.

8. A method of opportunistic data communications according to claim 1 wherein;

each of the broadcasting and transmitting the data packet comprises initiating at least one node activity, the at least a node activity being selected from a group comprising transmitting the data and network management information in the form of a transmitted data packet, calculating at a receiving node a cost of data delivery, initiating a cost of data delivery transfer to the first node, acknowledging receipt of the broadcast data packet, failure to deliver the data packet, and transmitting the data packet with a predetermined unicast cost of data delivery.

9. A method of opportunistic data communications according to claim 1 wherein;

transmitting the data packet from the first node to the at least one second node in a upon at least a wireless channel comprises utilizing a message comprising at least one of a request to send message, a clear to send message, an acknowledge message, a data message, a quality of service indicator, and an address.

10. A method of opportunistic data communications according to claim 1 wherein;

transmitting the data packet comprises providing the data packet to a data radio, the data radio for transmitting at least a modulated wireless signal upon a selected channel from a plurality of predetermined channels.

11. A method of opportunistic data communications according to claim 1 wherein, determining opportunistically at least one of the at least one second node and current subset of the plurality of second nodes is made at least in dependence upon receiving indications of availability from at least one of the plurality of second nodes.

12. A method of opportunistic data communications according to claim 1 wherein, determining opportunistically for the data packet whether to at least one of broadcast and unicast from the first node is made at least in dependence upon at least an indication of availability of at least one second node of the plurality of second nodes.

13. A method of opportunistic data communications according to claim 1 wherein;

determining the predetermined cost decision comprises determining the predetermined cost decision at least one of for each data packet individually, in dependence upon only the basis of cost of data delivery, and in dependence upon a response time of the second node to a request to send control message from the first node.

14. A method of opportunistic data communications according to claim 1 wherein;

determining the at least one second node comprises determining the at least one second node in dependence upon a weighted combination of factors, the factors selected from the group comprising cost of data delivery, an available budget for data delivery determined in dependence upon a characteristic of at least one of the first node and a second node of the current subset of second nodes, a measure of quality-of-service of a connection between the first node and at least one second node of the current subset of second nodes, an indication of second nodes already tried with the data packet, and a commercial weighting.

15. A method of opportunistic data communications according to claim 14 wherein;

providing a commercial weighting comprises providing a weighting based upon the second node to which it applies being at least one of part of the same service provider network as the first node, part of a network comprising at least a part thereof outside a predefined geographical limit, part of an unsecured communications network, part of a network having a commercial agreement with the service provider network of the first node, and part of a network on a banned network list.

16. A method of opportunistic data communications according to claim 1 wherein;

transmitting the data packet comprises delaying the transmission of the data packet for a predetermined period of time determined in dependence upon at least one of a network management command, establishing that a delayed transmission will reduce the cost of data delivery, receiving no clear to send message in response to a request to send, and a status of the first node.

17. A method of opportunistic data communications according to claim 1 wherein;

determining the predetermined cost decision comprises determining that the cost of data delivery from the first node to the second node shall be less than or equal to the cost of data delivery to the first node from a preceding hop node.

18. A method of opportunistic data communications according to claim 1 wherein;

providing at least one of the first node and one of the plurality of second nodes comprises providing a border gateway;

the border gateway for providing an interface between the network comprising the border gateway and another network, the another network operating according to at least one of the method of opportunistic data communications according to claim 1 and an open industry standard.

19. A method of opportunistic data communications according to claim 18 wherein;

providing the border gateway comprises providing a mapper, the mapper for at least one of translating between protocols of the network comprising the border gateway and the another network, mapping addresses between the network comprising the border gateway and the another network, implementing micro-user mobility management, and implementing macro-user mobility management.

20. A method of opportunistic data communications comprising the steps of:

providing a node of a plurality of nodes, each nodes identified by an address and capable of wirelessly communicating by at least one of transmitting and receiving a data packet upon one channel of a plurality of channels according to at least a standard and at least one of transmitting and receiving a pilot tone of a plurality of pilot tones;

receiving at the node a data packet for transmission, the data packet having associated a destination address other than the address of the node;

transmitting an indication of the availability of the data packet for transmission from the node using a first pilot tone, the pilot tone associated with at least one of the node and the one channel;

receiving an indication of an availability to receive the data packet from at least a second other node of the plurality of nodes, the availability indicated by receiving at least one of a second pilot tone and the address of the second other node, the second pilot tone associated with at least one of the second other node and the one channel;

providing at least one of an indication of an address and an indication of mobility associated with the at least a second other node of the plurality of nodes;

determining at least an indication of a cost of data delivery to at least each available second node within a current subset of at plurality of second nodes in dependence upon at least one of the address indication and mobility indication; and

determining opportunistically an action for the node for that data packet, the action one of broadcasting, unicasting, discarding, and temporarily storing the data packet;

wherein

broadcasting the data packet upon at least the one channel upon determining opportunistically to broadcast without at least one of regard to and knowledge of the addresses of the plurality of nodes;

unicasting the data packet upon at least the one channel upon determining opportunistically to unicast, the unicast being to at least one second other node of the plurality of nodes in dependence upon at least one of a predetermined cost decision and a declared availability;

discarding the data packet upon determining opportunistically to discard the data packet, the determination based upon the cost of data delivery to any available second other nodes exceeds available funds; and

temporarily storing the data packet upon determining opportunistically to store the data packet for a predetermined period of time, the predetermined period of time established in dependence upon at least one of lowering the cost of data delivery to a selected second other node at least one of further and to below available funds.

21. A method of opportunistic data communications according to claim 20 wherein,

transmitting at least one of the first pilot tone and second pilot tone comprises transmitting at least one of a continuous CW frequency, a CW frequency for a predetermined period of time, and a control packet.

22. A method of opportunistic data communications according to claim 20 wherein,

determining at least one of the cost of delivery and predetermined cost decision comprises determining the at least one of in dependence upon at least one of a first characteristic and a second characteristic, wherein

the first characteristic relates at least one of the node and the second node and is selected from the group comprising available battery power, size of the data packet to be transmitted, a measure of direction of movement of the node relative to another node of the current subset of second nodes, a measure of velocity relative to the other second node of the current subset of second nodes, and an indication that the cost of next data delivery from the one second node to another second node of the plurality of second nodes is lower than or equal to the cost of the data delivery from the first node to the one second node;

and

the second characteristic relates to a transceiver associated with one of the node and the second node and is selected from the group comprising maximum potential output power of the transceiver, current output power setting, and transmission speed.

23. A method of opportunistic data communications comprising the steps of:

providing a node of a plurality of nodes supporting transmission of at least a data packet on at least one data channel of a plurality of data channels according to a standard and capable of bidirectional communications relating to node status upon at least one message channel of a plurality of message channels, each message channel other than one of the plurality of data channels;

monitoring a predetermined set of the message channels to provide an indication of activity;

receiving a data packet for communication from the node;

transmitting the data packet according to the standard upon the indication of activity meeting a first predetermined criterion without regard to the plurality of message channels;

transmitting the data packet according to an opportunistic method upon the indication of activity meeting a second predetermined criterion, the opportunistic method including a decision as to whether at least one of opportunistically broadcast and opportunistically unicast from the node for the data packet;

wherein, opportunistically broadcasting comprises broadcasting the data packet without at least one of regard to any addresses of the plurality of nodes and knowledge of the plurality of second addresses upon at least a data channel; and

opportunistically unicasting comprises determining at least one other node of the current plurality of nodes to transmit the data to based upon a determined cost of data delivery to the one other node meeting a predetermined cost decision and transmitting the data packet from the node to the at least one determined other node upon at least a data channel.

24. A method of opportunistic data communications according to claim 23 wherein,

determining the other node of the plurality of nodes comprises transmitting a request-to-send signal on a first message channel of the plurality of message channels and determining the presence of a clear-to-send signal on at least one second message channel of a plurality of second message channels, each of the request-to-send and clear-to-send signals being other than digital data.

25. A method of opportunistic data communications according to claim 24 wherein,

the first message channel and second message channel of the plurality of message channels are associated with the same data channel of the plurality of data channels;

and

the plurality of message channels are unmodulated frequency tones.