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

• US 20030033394A1
• Filed: 03/21/2002
• Published: 02/13/2003
• Est. Priority Date: 03/21/2001
• Status: Active Grant

• Current Assignee: SCR Networks LLC
• Original Assignee: John A. Stine
• Inventors: Stine, John A.
• Granted Patent: US 7,266,085 B2
• Time in Patent Office: Days
• US Class Current: 709/222
• 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/823 Prediction of resource usage
• 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;

synchronizing channel access attempts of all nodes;

using signaling to resolve access attempts between contending nodes;

disseminating node states among nodes on a wireless channel of the ad hoc wireless network;

inferring connectivity links between nodes based on said node states;

building routing tables based on route metrics of said connectivity links; and

routing packets based on said routing tables.

2. The method of operating an ad hoc wireless network of claim 1, further comprising assigning said route metric for each connectivity link selected from the group consisting of energy consumption, node mobility, node activity, and trust.

3. The method of operating an ad hoc wireless network of claim 1, wherein inferring connectivity links comprises inferring the link to exist if a specified received signal strength p_r can be achieved using the path loss equation

4. The method of operating an ad hoc wireless network of claim 2, further comprising assigning a weight to each connectivity link identified, wherein each weight is calculated by the equation

5. The method of operating an ad hoc wireless network of claim 1, wherein routing network links further comprises calculating a lowest cost path via Dijkstra'"'"'s algorithm, where cost is the sum of the route metrics assigned to the connectivity links of a path.

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

dividing the wireless channel into transmission slots;

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.

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

dividing the transmission slots into synchronous phases;

selecting a preferred subset of contending nodes with a contention resolution (CR) signaling phase;

signaling the preferred subset of contending nodes to announce their intended distinction with a request-to-send (RTS) phase;

destination nodes responding to sources acknowledging receipt of a RTS packets addressed to them with a cleared-to-send (CTS) phase;

a protocol data unit (PDU) phase for source nodes to transmit payload packets; and

an acknowledgement (ACK) phase for the destination nodes to acknowledge receipt of a PDU;

thereby allowing spatial reuse of the wireless channel and avoidance of collisions in transmission of data over the wireless channel.

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

dividing the CR signaling phase into multiple signaling subphases governed by a policy where nodes may signal starting or ending in specified slots, each sub-phase comprising multiple signaling slots, the signaling slots further comprising:

a detectable signal;

a first to assert signaling phase whereby the node that signals first survives the signaling phase;

a last to assert signaling phase where the node that signals last survives the signaling phase;

a discrete signaling approach where single pulses are sent in each phase; and

a continuous signaling approach where continuous signals starts at a slot in a first to assert phase and continues until the end of the phase or starts at the beginning of a last to assert phase and continues until a subsequent slot in the same phase.

9. The method of operating an ad hoc wireless network of claim 8, wherein the CR signaling further comprises differentiating constant bit rate (CBR), variable bit rate (VBR), broadcast, quality of service (QoS), and multiple best effort services comprising:

a first to assert signaling phase where each service is assigned a slot or group of slots; and

an ordering of slot assignments that matches service priority.

10. The method of operating an ad hoc wireless network of claim 6, 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.

11. The method of operating an ad hoc wireless network of claim 10, 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.

12. The method of operating an ad hoc wireless network of claim 10, 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 stream;

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.

13. The method of operating an ad hoc wireless network of claim 1, further comprising recovering from routing loops by:

nodes identifying a loop by detecting a return of a packet that the node has already handled;

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 table; and

the node forwarding the packet.

14. The method of operating an ad hoc wireless network of claim 6, further comprising minimizing energy consumption by:

allowing nodes to enter low energy states;

implementing a default policy whereby a node can enter a low energy state for the remainder of a transmission slot once ascertaining it has no pending traffic that slot;

implementing a policy whereby nodes can enter a low energy state for a predefined period if they detect no use of the wireless channel; and

implementing a policy whereby nodes coordinate with other nodes to define their own period for entering and remaining in a low energy state.

15. The method of operating an ad hoc wireless network of claim 6, further comprising associating signal tones with specific source node-destination node pairs and tone multiplexing additional information to the detectable signal.

16. The method of operating an ad hoc wireless network of claim 7, further comprising recovering from a condition where multiple source nodes block each other at a destination node, wherein recovering is performed by a method selected from the group consisting of:

detecting multiple signals arriving for the node and signal echoing to suppress interfering contending nodes; and

reducing the threshold of signal detection after a transmission slot where 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.

17. The method of operating an ad hoc wireless network of claim 1, further comprising engineering traffic with wormholes comprising:

identifying nodes to participate in a given path;

directing the nodes to establish the path;

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

assigning a metric to wormhole links.

18. The method of operating an ad hoc wireless network of claim 1, further comprising establishing multiple routing tables for routing packets selected from the group consisting of service requirements, other user objectives, and network objectives.

19. 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 the broadcast priority signaling slot 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.

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

21. The method of operating an ad hoc wireless network of claim 19, 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.

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

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

synchronizing channel access attempts with other nodes;

using signaling to resolve access attempts with contending other nodes;

receiving node states of other nodes;

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

inferring connectivity links between nodes based on said node states;

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

routing any packets from said node based on said routing table.

23. An ad hoc network comprising:

a plurality of nodes on a wireless channel of the ad hoc network, wherein each node has a node clock;

means for synchronizing the node clocks;

means for synchronizing channel access attempts of all nodes;

signaling means to resolve access attempts between contending nodes;

means for disseminating node states among nodes of the ad hoc network;

means for inferring connectivity links between nodes based on said node states;

means for building routing tables based on route metrics of said connectivity links; and

means for routing packets based on said routing tables.