System and method for ad hoc network access employing the distributed election of a shared transmission schedule

• US 7,046,639 B2
• Filed: 09/28/2001
• Issued: 05/16/2006
• Est. Priority Date: 09/29/2000
• Status: Expired due to Fees

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Garcia-Luna-Aceves, J. J., Bao, Lichun
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Pham, Brenda
• Application Number:
  US09/967,901
• Publication Number:
  US 20020067736A1
• Time in Patent Office: 1,691 Days
• Field of Search: 370/314, 370/445, 370/235, 370/258, 370/310.2, 370/321, 370/322, 370/326, 370/328, 370/329, 370/336, 370/338, 370/341, 370/347, 370/348, 370/395.4, 370/449, 370/450, 370/458, 370/468, 370/515
• US Class Current: 370/314
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 72/535 based on resource usage policies
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A system and method of providing distributed election of a shared transmission schedule within an ad hoc network. The invention includes a collision-free access protocol which resolves channel access contentions for time division multiple access (TDMA) of a single channel. Time-slots are organized into part numbers, which are included within sections, a sequence of which define a block. Each node is given a ring number according to its location within the network topology and maintains local neighbor information along with its own part number and message digest. Collision-free channel access is automatically scheduled and repetitious contention phases are resolved by a random permutation algorithm operating in message digests. An empty time-slot utilization method is also described and data packets may also be transmitted subject to a non-zero collision probability within a blind section of the block.

Claims

1. A method of scheduling collision-free topology-dependent time division multiple access (TDMA) data transmission on a channel having time-slots within a given block of an ad hoc network having a plurality of nodes, comprising:

mapping time-slots of local neighbors;

computing a random permutation of contending local neighbors; and

transmitting one or more data frames within a given time-slot by a node selected according to said random permutation

wherein each of said nodes is located on a specific ring within the topology of said network, as determined by the number of hops to reach a given reference node; and

wherein each of said nodes is assigned a unique node ID;

wherein said reference node is a central node which communicates a ring number and assigns a node ID to each of said nodes;

wherein the choice of said central node is dependent on the specific needs of the communication application; and

wherein said central node may be algorithmically selected based on topological information about said network.

2. A method as recited in claim 1, wherein said local neighbors comprise neighbors which are located within a two-hop neighborhood.

3. A method as recited in claim 1, wherein a sequence of said time-slots is organized into a part, or equivalent.

4. A method as recited in claim 3, wherein each node is associated with a given part number within which it may be allowed to transmit.

5. A method as recited in claim 4, wherein said mapping of time-slots for local neighbors comprises:

broadcasting said node ID and said part number by each of said nodes to neighboring nodes located within one hop; and

registering information from said broadcasts from neighboring nodes into a map of local neighbors.

6. A method as recited in claim 5, wherein a node that does not gain transmission access for broadcasting said node ID and said part number information to neighboring nodes may wait until the transmission can be performed collision-free in a subsequent block.

7. A method as recited in claim 4, wherein said part number is derived from said ring number.

8. A method as recited in claim 7, wherein the value of said part number p for a given node is determined by modulo three evaluation of said ring number r for said node, as given by p≡

r mod 3.

9. A method as recited in claim 7, wherein said nodes within said network are allowed to transmit collision-free data frames during their part number within a section of said block.

10. A method as recited in claim 3, wherein a sequence of said parts is organized into a section within which each node can vie for transmission of data frames within their respective part number.

11. A method as recited in claim 10, wherein a random section seed number is assigned to each said section.

12. A method as recited in claim 11, wherein said random section seed number is originally issued by said central node.

13. A method as recited in claim 12, wherein said random section seed number regenerates itself using a random-number generator.

14. A method as recited in claim 11, further comprising determining a message digest for one of said nodes based on the node ID for said node and said random section seed number for the current said section.

15. A method as recited in claim 14, wherein said message digest comprises the computation (iXORs) wherein i represents the node ID, and s represents said random section seed.

16. A method as recited in claim 14, wherein said message digest md determines the time-slot t which may be allocated to one of said nodes.

17. A method as recited in claim 16, wherein said time-slot is determined by way of hashing.

18. A method as recited in claim 17, wherein said time-slot is determined by hashing said message digest md according to the relationship t≡

md modt_p, which determines the time-slot within said part within which transmission may be allowed.

19. A method as recited in claim 18, wherein neighboring nodes may contend with one another for the same time-slot in response to being hashed to the same time-slot according to said message digest.

20. A method as recited in claim 19, wherein said computation of a random permutation of contending neighbors comprises:

concatenating said message digest with said node ID for each node as determined by said map of local neighbors to generate a set of results; and

sorting said results to select a node for transmission within said time-slot according to said random permutation.

21. A method as recited in claim 10, wherein each said section may be subject to different time-slot allocation rules.

22. A method as recited in claim 21, wherein each of said time-slots is formatted into segments whose composition is responsive to said time-slot allocation rules.

23. A method as recited in claim 10, wherein a sequence of said sections is organized into a block.

24. A method as recited in claim 23, further comprising maintaining rotary counters within each of said nodes for segment, time-slot, part number, and section number within said block.

25. A method as recited in claim 23, wherein at least one said section of said block comprises a hush section for introducing new member nodes into said network.

26. A method as recited in claim 25, wherein a node may join said network as a new member node subject to communicating their existence to neighboring nodes.

27. A method as recited in claim 26, wherein said hush section comprises a plurality of time-slots in which said new members announce their existence to the network.

28. A method as recited in claim 27, wherein said time-slots within said hush section are divided into segments of sufficient duration to allow a signal to be broadcast by said new members of said network.

29. A method as recited in claim 28, wherein a new local neighbor synchronizes itself with said section seed by listening to data frames transmitted within said time-slots of said block.

30. A method for resolving time-slot contentions between nodes contending for a single communication channel within an ad hoc time division multiple access network, comprising:

assigning a node ID to each of said nodes within said network;

creating a message digest, or equivalent, based on said node ID and a random seed value for each of said nodes;

concatenating said message digest with node ID, for all of said nodes in contention, into a contention list;

sorting said contention list according to a random-permutation algorithm; and

granting access to a node at a predetermined position within said sorted list.

31. A method as recited in claim 30, wherein said predetermined position comprises the top of said list.

32. A method for topology-dependent access scheduling which allows a node on a network to access a time-slot within a given block of a communication channel to transmit, comprising:

dividing said block into sections of contiguous parts that each contain a series of time-slots;

establishing a ring number for each of said nodes on said network according to its topological distance from a central node;

mapping a unique node ID for each of said nodes within said network;

calculating a part number for each of said nodes based on said ring number;

establishing a section seed for each of said sections of contiguous parts within said block;

calculating message digests for all neighboring nodes;

determining if contention exists for a given time-slot as based on said message digests;

resolving any said contention by executing a random-permutation algorithm of said message digests to select a winning node to transmit in said time-slot; and

transmitting one or more data packets during said part number in said time-slot.

33. A method as recited in claim 32, wherein the non-winning nodes may attempt to gain access to said time-slot in subsequent sections of said block.

34. A method as recited in claim 32, wherein one of said nodes in a ring r is only authorized to transmit when the part number within said section of said block matches the part number p determined for said node.

35. A method as recited in claim 32, wherein said part number is determined for one of said nodes according to the relation p≡

r mod3, where p is the part number, and r is the ring number as determined by the topological distance to a central node.

36. A method as recited in claim 32, wherein within said part number a node with said message digest md for the current section is allowed to transmit in time-slot t, only where t≡

md modt_p.

37. A method as recited in claim 32, wherein spare, otherwise unallocated, time-slots may be utilized by nodes within a given part that otherwise would not be entitled to use said time-slot according to their message digest.

38. A method as recited in claim 37,

further comprising resolving contention for said spare, otherwise unallocated, time-slots;

wherein two or more of said nodes compete for a given spare time-slot within their respective part numbers;

calculating a spare slot message digest which incorporates the spare slot number;

resolving said contention by executing a random-permutation algorithm; and

awarding said spare time-slot to a winner of the random-permutation according to position within the list of results.

39. A method as recited in claim 32, further comprising:

setting aside a blind section within said sections of said block for use with blind transmissions; and

wherein a node unable to gain access to a collision-free time-slot may attempt transmission during said blind section without computing transmission priorities.

40. A method for resolving contentions for time division multiple access to a single communication channel, comprising:

assuming a synchronized function generating random-permutation of contending parties for collision-freedom, which implies knowledge of two-hop neighbors in a network topology by each node in the network;

wherein the permutation corresponds to an array of sorted message digests of all contending parties;

wherein each message digest comprises a fingerprint of each contending party identification (ID) and a seed, plus the contending party ID;

wherein the seed is synchronized at all parties and regenerates itself by a common random function from time to time so that the message digest of each party varies every time to assure the randomness of the permutation;

wherein once a party finds itself at the first position of the sorted sequence, the party is authorized to access the common channel; and

wherein for others that find themselves at other positions, they remain quiet for the time slot.