초록 ▼

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

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.

대표청구항 ▼

What is claimed is: 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

What is claimed is: 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 modtp, 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 modtp. 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.