Neighbor based TDMA slot assignment

• US 20070019594A1
• Filed: 07/25/2005
• Published: 01/25/2007
• Est. Priority Date: 07/25/2005
• Status: Active Grant

• Current Assignee: Ademco Inc. (Resideo Technologies, Inc.)
• Original Assignee: Honeywell International Inc.
• Inventors: Raina, Manik, Perumal, Kannan, Patro, Ranicer, Mohan, Balamurugan, Ghosh, Subhas
• Granted Patent: US 7,804,803 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: H04W 16/10 Dynamic resource partitioning
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 72/54 based on quality criteria
• CPC Class Codes: H04W 8/22 Processing or transfer of terminal data, e.g. status or physical capabilities
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Non-overlapping time slots are allocated to a plurality of nodes in a network by a mobile agent that moves from node to node of the network. At a current node of the network, the mobile agent accesses neighbor information that includes time slot information relative to neighbor nodes of the current node. The neighbor nodes are neighbors of the current node. At the current node of the network, the mobile agent also assigns mutually exclusive time slots for the neighbor nodes.

Claims

1. A method of allocating non-overlapping time slots to a plurality of nodes in a network comprising:

executing a mobile agent at a current node of the network;

accessing neighbor information by execution of the mobile agent, wherein the neighbor information includes time slot information relative to neighbor nodes of the network, and wherein the neighbor nodes are neighbors of the current node; and

,

assigning mutually exclusive time slots for the neighbor nodes by execution of the mobile agent.

2. The method of claim 1 wherein the neighbor nodes are one-hop neighbors of the first node.

3. The method of claim 1 further comprising setting a flag indicating that the current node has been visited.

4. The method of claim 1 further comprising communicating the time slot assignments to the neighbor nodes.

5. The method of claim 1 wherein the current node comprises an old current node, wherein the neighbor nodes comprise old neighbor nodes, wherein the neighbor information comprise old neighbor information, and wherein the method further comprises:

moving the mobile agent from the old current node to one of the old neighbor nodes such that the one old neighbor node becomes a new current node;

executing the mobile agent at the new current node;

accessing new neighbor information by execution of the mobile agent, wherein the new neighbor information includes time slot information relative to new neighbor nodes, and wherein the new neighbor nodes are neighbors of the new current node; and

,

assigning mutually exclusive time slots for the new neighbor nodes by execution of the mobile agent.

6. The method of claim 5 wherein the moving of the mobile agent from the old current node to the new current node comprises:

determining that at least one of the old neighbor nodes has not been visited by the mobile agent; and

,

moving the mobile agent from the old current node to one of the old neighbor nodes that has not been visited by the mobile agent, wherein the one old neighbor node comprises the new current node.

7. The method of claim 1 further comprising:

determining whether at least one of the neighbor nodes has been visited by the mobile agent;

if all of the neighbor nodes have been visited by the mobile agent, backtracking the mobile agent to a previously visited neighbor node;

if at least one of the neighbor nodes has not been visited by the mobile agent, moving the mobile agent from the current node to the at least one neighbor node that has not been visited by the mobile agent; and

,

executing the mobile agent at the at least one neighbor node that has not been visited by the mobile agent.

8. The method of claim 7 further comprising ending movement of the mobile agent to nodes if all of the neighbor nodes of the current node have been visited by the mobile agent and if the current node is a node where the mobile agent began operation.

9. The method of claim 1 wherein the assigning of mutually exclusive time slots for the neighbor nodes comprises assigning a smallest possible integer as the time slot to each of the neighbor nodes, and wherein the smallest possible integer comprises an integer that is not in the neighbor information of the neighbor nodes and that has not been previously assigned by the current node.

10. A wireless network comprising:

a plurality of wireless sensor nodes, wherein each node has a communication radius and a sensing radius, wherein the communication radius defines a distance over which a corresponding node is capable of effectively communicating, wherein the sensing radius defines a distance over which a corresponding node is capable of effectively sensing a condition, and wherein the communication radius of each node should be at least as great as the sensing radius of the corresponding node; and

,

a mobile agent that moves to a current node in the network, that accesses neighbor information including time slot information relative to one-hop neighbor nodes of the current node, and that assigns mutually exclusive time slots to only the one-hop neighbor nodes.

11. The wireless network of claim 10 wherein the communication radius of each node should be about twice as great as the sensing radius of the corresponding node.

12. The wireless network of claim 10 wherein the mobile agent sets a flag at the current node indicating that the mobile agent has visited the current node.

13. The wireless network of claim 10 wherein the mobile agent communicates the time slot assignments to the neighbor nodes.

16. The wireless network of claim 10 wherein the mobile agent comprises a mobile agent that determines whether at least one of the neighbor nodes has been visited by the mobile agent, that backtracks, if all of the neighbor nodes have been visited by the mobile agent, to a previously visited neighbor node, that moves, if at least one of the neighbor nodes has not been visited by the mobile agent, from the current node to the at least one neighbor node that has not been visited by the mobile agent, and that executes at the at least one neighbor node that has not been visited by the mobile agent.

17. The wireless network of claim 16 wherein the mobile agent comprises a mobile agent that ends movement if all of the neighbor nodes of the current node have been visited by the mobile agent and if the current node is a node where the mobile agent began operation.

18. The wireless network of claim 10 wherein the mobile agent comprises a mobile agent that assigns a smallest possible integer as the time slot to each of the neighbor nodes, and wherein the smallest possible integer comprises an integer that is not in the neighbor information of the neighbor nodes and that has not been previously assigned by the current node.

19. The wireless network of claim 10 wherein each node of the network is located within the communication radius of at least one other node.

14. The wireless network of claim 14 wherein the current node comprises an old current node, wherein the neighbor nodes comprise old neighbor nodes, wherein the neighbor information comprise old neighbor information, and wherein the mobile agent comprises a mobile agent that moves from the old current node to one of the old neighbor nodes such that the one old neighbor node becomes a new current node, that accesses new neighbor information including time slot information relative to new one-hop neighbor nodes of the new current node, and that assigns mutually exclusive time slots to only the new neighbor nodes.

15. The wireless network of claim 14 wherein the mobile agent comprises a mobile agent that determines at the old current node that at least one of the old neighbor nodes has not been visited by the mobile agent, and that moves from the old current node to the one old neighbor node that has not been visited by the mobile agent, wherein the one old neighbor node comprises the new current node.

20. A computer readable storage medium having a mobile agent stored thereon such that execution of the mobile agent at a current node of the network performs the following functions:

querying each neighbor node of the current node for a time slot list of the neighbor node and for a flag indication of whether the mobile agent MA has previously visited the neighbor node;

updating the time slot list of each neighbor node of the current node by assigning a mutually exclusive time slot to an ID of the current node;

determining from the flag indications whether the mobile agent has visited all of the neighbor nodes of the current node;

if the mobile agent has not visited all of the neighbor nodes of the current node, moving to an unvisited one of the neighbor nodes; and

,

if the mobile agent has visited all of the neighbor nodes of the current node, backtracking to a previously visited one of the neighbor nodes.

21. The computer readable storage medium of claim 20 wherein the neighbor nodes of the current node are one-hop neighbors of the current node.

22. The computer readable storage medium of claim 20 wherein the mobile agent further performs the function of setting a flag indicating that the current node has been visited by the mobile agent.

23. The computer readable storage medium of claim 20 wherein the mobile agent further performs the function of communicating the time slot lists back to the corresponding neighbor nodes of the current node.

24. The computer readable storage medium of claim 20 wherein the mobile agent further performs the function of ending movement if all of the neighbor nodes of the current node have been visited by the mobile agent and if the current node is a node where the mobile agent began operation.

25. The computer readable storage medium of claim 20 wherein the mobile agent further performs the function of assigning a smallest possible integer as the time slot to each of the neighbor nodes, and wherein the smallest possible integer comprises an integer that is not in the time slot lists of the neighbor nodes and that has not been previously assigned by the current node.