Access and routing protocol for ad hoc network using synchronous collision resolution and node state dissemination

• US 7,266,085 B2
• Filed: 03/21/2002
• Issued: 09/04/2007
• Est. Priority Date: 03/21/2001
• Status: Active Grant

• Current Assignee: SCR Networks LLC
• Original Assignee: John A. Stine
• Inventors: Stine, John A.
• Primary Examiner(s): Nguyen; Chau
• Assistant Examiner(s): Juntima; Nittaya
• Application Number:
  US10/104,336
• Publication Number:
  US 20030033394A1
• Time in Patent Office: 1,993 Days
• Field of Search: 370328-329, 370/338, 370/351, 370/229, 370/235, 370254-255, 370/238, 370/252, 370/345, 370/347, 370/348, 370/445, 370/447, 370/458, 370461-462, 370/465, 370/468
• US Class Current: 370/252
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/40 Wormhole routing
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/726 Reserving resources in multiple paths to be used simultaneously by balancing the load H04L47/125
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/824 Applicable to portable or mobile terminals
• CPC Class Codes: H04L 47/83 based on usage prediction
• CPC Class Codes: H04W 28/021 in wireless networks with changing topologies, e.g. ad-hoc networks self-organizing networks H04W84/18
• CPC Class Codes: H04W 28/0221 power availability or consumption
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/30 : for proactive routing
• CPC Class Codes: H04W 52/0216 : using a pre-established activity schedule, e.g. traffic indication frame
• CPC Class Codes: H04W 52/0219 : where the power saving management affects multiple terminals
• CPC Class Codes: H04W 56/00 : Synchronisation arrangements
• CPC Class Codes: H04W 72/12 : Wireless traffic scheduling
• CPC Class Codes: H04W 74/08 : Non-scheduled access, e.g. ALOHA hybrid access H04W74/02
• CPC Class Codes: H04W 74/0816 : with collision avoidance
• CPC Class Codes: H04W 8/04 : Registration at HLR or HSS [Home Subscriber Server]
• 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

An ad hoc network organizes itself to provide communications without need for an a priori designated central control mechanism or base stations. Such self-organization is challenging in a multihop ad hoc network having member nodes that are highly mobile and widely distributed. A Synchronous Collision Resolution (SCR) protocol and a Node State Routing (NSR) protocol are well suited to provide efficient ad hoc network organization. SCR is an access protocol that achieves high capacity collision free access using a signaling approach that creates a random cellular-like network after each signaling period. NSR is a routing protocol that uses the dissemination of node states to predict link availability and to assign metrics to those links for the creation of optimized routes. In use, the present invention provides quality of service and supports energy conservation for the mobile nodes.

Claims

1. A method of operating an ad hoc wireless network, comprising:

synchronizing nodes on a wireless channel of the ad hoc wireless network to a common time;

dividing a wireless channel into transmission slots;

establishing a plurality of signaling phases on the wireless channel at the beginning of a transmission slot, wherein each of the plurality of signaling phases is associated with a signaling process selected from the group consisting of a first to assert signaling process and a last to assert signaling process, and wherein each of the plurality of signaling phases comprises one or more signaling slots;

synchronizing transmission of access signals of contending nodes relative to the signaling phases, wherein each of the contending nodes comprises a packet to send and wherein each of the contending nodes contends simultaneously for access to the wireless channel;

determining surviving nodes of a signaling phase among the contending nodes by applying the signaling process associated with the signaling phase to the access signals transmitted by the contending nodes;

determining ultimate survivors of a channel access attempt among the surviving nodes by identifying the surviving nodes of each of the plurality of signaling phases among the contending nodes;

authorizing the ultimate survivors of the access attempt to transmit packets;

disseminating node state information among nodes;

inferring connectivity links between nodes based on the node state information;

assigning route metrics to the connectivity links using the node state information;

building routing tables based on the route metrics; and

routing packets based on the routing table.

2. The method of operating an ad hoc wireless network of claim 1, wherein the node state information comprises a node location, and a listing of node path loss exponents by directional sector, and one or more of the states selected from the list consisting of an interface, a channel identifier, an energy state, a receive fraction, a class, a velocity, a direction, a dozing state, a p-supporter address, a doze offset, a doze period, and a time stamp.

3. The method of operating an ad hoc wireless network of claim 1, wherein inferring a connectivity links between nodes comprises:

determining the distance, d, between a first node and a second node;

obtaining a first path loss exponent of the first node for a path from the first node to second node and obtaining a second path loss exponent of the second node for a path from the second node to the first node; and

inferring a link to exist between the first node and second node if a specified received signal strength p_r can be achieved using the path loss equation

p_r=k·

p_t/dⁿ 

 

(5)

where, k is a constant, p_t is transmission power, d is source destination separation distance, and n is the larger of the first path loss exponent and the second path loss exponent.

4. The method of operating an ad hoc wireless network of claim 1, further comprising:

determining a route for sending a payload packet from a contending node to a destination node using a routing table, wherein the route comprises a next hop node;

sending a request to send (RTS) message from the contending node for receipt by the next hop node;

sending a clear to send (CTS) messages from the next hop node if the RTS message is received by the next hop node;

sending the payload packet from the contending node to the next hop node if the CTS message is received by the contending node; and

sending an acknowledgement (ACK) message from the next hop node for receipt by the contending node if the payload packet is received by the next hop node.

5. The method of operating an ad hoc wireless network of claim 4, further comprising:

recovering from a condition wherein multiple transmitting nodes block each other at a receiving node, wherein recovering is performed by a method selected from the group consisting of;

at a receiving node, detecting a node block caused by the simultaneous arrival of a plurality of signals for the receiving node; and

implementing a recovery procedure to rectify the node block selected from the group consisting of signal echoing to suppress interfering contending nodes; and

reducing the threshold of signal detection after a transmission slot in which a node has survived signaling but failed to transmit data and increasing the power used in CR signaling after a transmission slot where a node has survived signaling but failed to transmit data.

6. The method of operating an ad hoc wireless network of claim 1, wherein using a plurality of signaling phases to resolve the channel access attempts among the contending nodes comprises:

assigning a service priority to a signaling slot within a signaling phase based on a packet differentiator;

permitting contending nodes having packets to transmit comprising the packet differentiator to transmit a contention signal in the priority signaling slot based on the packet differentiator of a payload packet;

applying a first-to-assert preemption rule to the priority phase; and

determining at the contending nodes whether the contending node survived the priority phase contention.

7. The method of operating an ad hoc wireless network of claim 6, further comprising:

organizing the transmission slots into constant bit rate (CBR) frames; and

repeating the CBR frames at a rate where one slot per frame supports a lowest CBR service.

8. The method of operating an ad hoc wireless network of claim 7, further comprising reserving transmission slots on a use-or-lose basis comprising:

implementing a QoS priority for initial access to a transmission slot in a CBR frame;

implementing a CBR priority for subsequent access to the same transmission slot of the next CBR frame;

implementing a policy whereby only nodes that have used a QoS or CBR signaling slot in a transmission slot of the previous CBR frame may use the CBR signaling slot in the same transmission slot of the current CBR frame;

implementing a cooperative signaling slot in the first position of a subsequent first to assert signaling phase that is used in tandem with the use of the CBR signaling slot;

implementing a policy whereby only a service that contends using the CBR signaling slot may also signal using the cooperative signaling slot; and

implementing a policy whereby destinations also signal using the cooperative signaling slot when two conditions apply;

a node received traffic in the same transmission slot of the previous CBR frame from a node that used either the Qos or CBR signaling slots to gain access and the CBR signaling slot was used in the priority phase of the current transmission slot.

9. The method of operating an ad hoc wireless network of claim 8, wherein reserving transmission slots on a use-or-lose basis comprises reserving a multihop connection between end nodes that meets predetermined delay and bandwidth constraints by incrementally reserving transmission slots between pairs of nodes along the path, further comprising:

limiting the transmission slots that a node may reserve based on delay effects across the path;

implementing a policy whereby nodes along the path hold the reserved links while waiting for a complete path to be established; and

implementing a policy to automatically cancel the reserved path as soon as it is no longer used.

10. The method of operating an ad hoc wireless network of claim 8, further comprising each node queuing and scheduling packets by:

forming multiple queues, each associated with a different priority of service, including separate constant bit rate (CBR) stream queues and variable bit rate (VBR) streams queues;

providing a queue for each new CBR and VBR streams;

implementing a policy to send packets from highest priority queues first; and

implementing a policy to associate CBR and VBR queues to specific reserved transmission slots in each CBR frame wherein the node contends to send packets from the queues using the CBR priority signaling group.

11. The method of operating an ad hoc wireless network of claim 1, further comprising:

allowing a node to enter a low energy state;

implementing a slot-based policy whereby the node can enter the low energy state for the remainder of a transmission if it has no pending traffic for that slot;

implementing a channel-based policy whereby the node can enter a low energy state for a predefined period if the channel is not in use; and

implementing a coordination policy whereby the node coordinates with other nodes to define a period for entering and remaining in a low energy state.

12. The method of operating an ad hoc wireless network of claim 1, further comprising:

associating signal tones with a specified node behavior; and

a contending node utilizing the signal tones in a collision resolution signal to elicit the specified behavior from another node.

13. The method of operating an ad hoc wireless network of claim 1, further comprising:

identifying a loop at a node by detecting a return of a packet that the node has previously sent;

the node broadcasting all node states in its node state list in sequential node state packets upon identifying a loop;

the node recalculating its routing tables; and

the node routing the packet using a recalculated routing table.

14. The method of operating an ad hoc wireless network of claim 1, further comprising:

identifying nodes to participate in a given path;

directing the nodes to establish the path;

disseminating the path within the ad hoc network as a wormhole state; and

assigning a metric to the wormhole.

15. The method of operating an ad hoc wireless network of claim 1, wherein building routing tables based on the route metrics comprises:

selecting a routing objective comprising routing objective criteria;

selecting at a node eligible participating nodes that meet the routing objective criteria;

inferring links between the node and the eligible participating nodes using the selected objective;

assigning a metric to the inferred links using the selected objective;

calculating routes among the node and the eligible participating nodes using the selected objective; and

creating a table of the routes associated with the selected objective.

16. The method of operating an ad hoc wireless network of claim 1, further comprising supporting the selection of a unique channel for the exchange of peer-to-peer traffic between nodes using signaling slots comprising:

providing a receiver directed channel for every node;

providing a broadcast channel used by every node;

providing a broadcast priority group comprising a subset of priority signaling slots;

implementing a policy whereby nodes listen for packets on their receiver directed channel whenever any priority signaling slot other than a signaling slot from the broadcast priority group is used; and

implementing a policy whereby all nodes listen for subsequent packets in the broadcast channel whenever the broadcast priority group was used to gain access.

17. The method of operating an ad hoc wireless network of claim 16, further comprising the nodes transmitting multiple different packets of data to different destinations simultaneously at the same node, each transceiver being on a different channel.

18. The method of operating an ad hoc wireless network of claim 16, further comprising the nodes transmitting multiple different packets of data to different destination simultaneously using a single transceiver adapted to code-multiplex a signal from the single transceiver.

19. The method of operating an ad hoc wireless network of claim 1 further comprising:

creating multiple routing tables at a node, wherein each of the multiple routing tables supports a routing objective;

selecting a routing objective for routing the packets; and

selecting a routing table from the multiple routing tables that supports the selected routing objective.

20. A method of operating a node on an ad hoc network, comprising:

synchronizing a clock of the node with other nodes of the ad hoc network to a common time;

synchronizing channel access attempts of the node with other nodes;

using a plurality of signaling phases on the channel at the beginning of a transmission slot to resolve access attempts with other contending nodes;

receiving node states of other nodes;

broadcasting node states known to the node to other nodes on a wireless channel of the ad hoc wireless network;

inferring connectivity links between nodes based on a pathloss model whose parameters are included in the node states;

building a routing table based on route metrics of the connectivity links; and

routing packets from the node based on the routing table.

21. A method of operating an ad hoc wireless network comprising:

disseminating node state information among the nodes, wherein disseminating node state information among the nodes comprises;

applying a set of rules for selecting node states to be included in a node state packet; and

transmitting the selected node states in the node state packet;

inferring connectivity links between the nodes based on the node state information;

assigning route metrics to the connectivity links using the node state information; and

building routing tables based on the route metrics.

22. The method of operating an ad hoc wireless network of claim 21, wherein the node state packet is transmitted on a periodic basis.

23. The method of operating an ad hoc wireless network of claim 21, wherein the node state packet is transmitted when a change has occurred in the selected node states.

24. The method of operating an ad hoc wireless network of claim 21, wherein disseminating node state information among the nodes further comprises transmitting a set of wormhole states in the node state packet.

25. The method of operating an ad hoc wireless network of claim 21 further comprising:

establishing a minimum time between transmitting the node state packet and a subsequent node state packet, and

transmitting the subsequent node state packet after the minimum time.

26. A method of operating an ad hoc wireless network, comprising:

synchronizing nodes on a wireless channel of the ad hoc wireless network to a common time;

dividing a wireless channel into transmission slots;

establishing a plurality of signaling phases on the wireless channel at the beginning of a transmission slot, wherein each of the plurality of signaling phases is associated with a signaling process selected from the group consisting of a first to assert signaling process and a last to assert signaling process, and wherein each of the plurality of signaling phases comprises one or more signaling slots;

synchronizing transmission of access signals of contending nodes relative to the signaling phases, wherein each of the contending nodes comprises a packet to send and wherein each of the contending nodes contends simultaneously for access to the wireless channel;

determining surviving nodes of a signaling phase among the contending nodes by applying the signaling process associated with the signaling phase to the access signals transmitted by the contending nodes;

determining ultimate survivors of a channel access attempt among the surviving nodes by identifying the surviving nodes of each of the plurality of signaling phases among the contending nodes; and

authorizing the ultimate survivors of the access attempt to transmit packets.