Method and apparatus for optimizing convergecast operations in a wireless sensor network
View Patent ↗A system that optimizes packet transmissions during a convergecast operation in a convergecast network. During operation, the system receives a request to perform the convergecast operation in the convergecast network. In response to the request, the system constructs a convergecast-tree, which includes the base-station and the plurality of nodes, based on hop counts from the plurality of nodes to the base-station. Next, the system linearizes the convergecast-tree so that the convergecast-tree contains a plurality of linear branches. The system then schedules packet transmission for each of the linear branches and each node in each branch based on a set of predetermined criteria to obtain a scheduled order. Finally, the system performs packet transmissions in the convergecast-tree using the scheduled order. Note that performing the convergecast operation in this way substantially optimizes the convergecast operation by reducing a total number of timeslots required to complete the convergecast operation.
1. A method for optimizing packet transmission during a convergecast operation in a convergecast network, the method comprising:
receiving a request to perform the convergecast operation in the convergecast network, wherein the convergecast network comprises a base-station and a plurality of nodes, and wherein during the convergecast operation the plurality of nodes communicate packets to the base-station;
constructing a convergecast-tree, which includes the base-station and the plurality of nodes, based on hop counts from the plurality of nodes to the base-station;
linearizing the convergecast-tree so that the convergecast-tree contains a plurality of linear branches;
scheduling packet transmissions for each of the plurality of linear branches and each node in each branch based on a set of predetermined criteria to obtain a scheduled order, wherein obtaining the convergecast schedule for each node involves performing a traversal of the convergecast-tree from each node in the plurality of the nodes to the base-station; and
performing packet transmissions in the convergecast-tree using the scheduled order;
wherein performing the convergecast operation using the scheduled order substantially optimizes the convergecast operation by reducing a total number of timeslots required to complete the convergecast operation.
2. The method of claim 1 , wherein constructing the convergecast-tree involves:
broadcasting a message from the base-station to all one-hop neighbors of the base-station;
propagating the message to each node in the plurality of the nodes through broadcast forwarding with duplicate suppression; and
constructing a shortest-hop-count tree to form the convergecast-tree.
3. The method of claim 1 , further comprising obtaining a hop-count for each node in the plurality of the nodes prior to scheduling the packet transmissions.
4. The method of claim 1 , wherein each node in the plurality of nodes can be in one of the following states during each timeslot of the convergecast operation:
a receiving state, during which the node may receive a packet from a neighboring node;
a transmitting state, during which the node may transmit a packet to a neighboring node; and
an idle state, during which the node neither transmits nor receives.
5. The method of claim 1 , wherein linearizing the convergecast-tree involves decomposing the convergecast-tree into a plurality of logically linear branches.
6. The method of claim 1 , wherein the scheduling of packet transmissions for the plurality of linear branches involves iteratively:
selecting up to three linear branches from the plurality of linear branches; and
scheduling an order of packet transmission among the selected linear branches based on the set of predetermined criteria.
7. The method of claim 1 , wherein the set of predetermined criteria can include:
a number of nodes in a linear branch; and
an identifier for the linear branch.
8. The method of claim 1 , wherein each node in the plurality of nodes computes its own scheduled order during the convergecast operation.
9. The method of claim 1 , wherein the convergecast-tree can be decomposed into a set of one-hop-subtrees, wherein the root of each of the set of one-hop-subtrees is an one-hop neighbor of the base-station.
10. The method of claim 1 , wherein the total number of timeslots required to complete the convergecast operation based on the scheduled order is at most max (3n k −1, N), wherein:
n k is the number of nodes in the largest linear branch; and
N is the number of nodes in the convergecast-tree.
11. The method of claim 1 , wherein the convergecast network is a wireless network.
12. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for optimizing packet transmission during a convergecast operation in a convergecast network, the method comprising:
receiving a request to perform the convergecast operation in the convergecast network, wherein the convergecast network comprises a base-station and a plurality of nodes, and wherein during the convergecast operation the plurality of nodes communicate packets to the base-station;
constructing a convergecast-tree, which includes the base-station and the plurality of nodes, based on hop counts from the plurality of nodes to the base-station;
linearizing the convergecast-tree so that the convergecast-tree contains a plurality of linear branches;
scheduling packet transmissions for each of the plurality of linear branches and each node in each branch based on a set of predetermined criteria to obtain a scheduled order, wherein obtaining the convergecast schedule for each node involves performing a traversal of the convergecast-tree from each node in the plurality of the nodes to the base-station; and
performing packet transmissions in the convergecast-tree using the scheduled order;
wherein performing the convergecast operation using the scheduled order substantially optimizes the convergecast operation by reducing a total number of timeslots required to complete the convergecast operation.
13. The computer-readable storage medium of claim 12 , wherein constructing the convergecast-tree involves:
broadcasting a message from the base-station to all one-hop neighbors of the base-station;
propagating the message to each node in the plurality of the nodes through broadcast forwarding with duplicate suppression; and
constructing a shortest-hop-count tree to form the convergecast-tree.
14. The computer-readable storage medium of claim 12 , further comprising obtaining a hop-count for each node in the plurality of the nodes prior the scheduling the packet transmissions.
15. The computer-readable storage medium of claim 12 , wherein each node in the plurality of nodes can be in one of the following states during each timeslot of the convergecast operation:
a receiving state, during which the node may receive a packet from a neighboring node;
a transmitting state, during which the node may transmit a packet to a neighboring node; and
an idle state, during which the node neither transmits nor receives.
16. The computer-readable storage medium of claim 12 , wherein linearizing the convergecast-tree involves decomposing the convergecast-tree into a plurality of logically linear branches.
17. The computer-readable storage medium of claim 12 , wherein the scheduling of packet transmissions for the plurality of linear branches involves iteratively:
selecting up to three linear branches from the plurality of linear branches; and
scheduling an order of packet transmission among the selected linear branches based on the set of predetermined criteria.
18. The computer-readable storage medium of claim 12 , wherein the set of predetermined criteria can be include:
a number of nodes in a linear branch; and
an identifier for the linear branch.
19. The computer-readable storage medium of claim 12 , wherein each node in the plurality of nodes computes its own scheduled order during the convergecast operation.
20. The computer-readable storage medium of claim 12 , wherein the convergecast-tree can be decomposed into a set of one-hop-subtrees, wherein the root of each of the set of one-hop-subtrees is an one-hop neighbor to the base-station.
21. The computer-readable storage medium of claim 12 , wherein the total number of timeslots required to complete the convergecast operation based on the scheduled order is at most max(3n k −1, N), wherein:
n k is the number of nodes in the largest linear branch; and
N is the number of nodes in the convergecast-tree.
22. The computer-readable storage medium of claim 12 , wherein the convergecast network is a wireless network.
23. An apparatus that optimizes packet transmission during a convergecast operation in a convergecast network, comprising:
a receiving mechanism configured to receive a request to perform the convergecast operation in the convergecast network, wherein the convergecast network comprises a base-station and a plurality of nodes, and wherein during the convergecast operation the plurality of nodes communicate packets to the base-station;
a construction mechanism configured to construct a convergecast-tree, which includes the base-station and the plurality of nodes, based on hop counts from the plurality of nodes to the base-station;
a linearization mechanism configured to linearize the convergecast-tree so that the convergecast-tree contains a plurality of linear branches;
a scheduling mechanism configured to schedule packet transmission for each of the plurality of linear branches and each node in each branch based on a set of predetermined criteria to obtain a scheduled order, wherein obtaining the convergecast schedule for each node involves performing a traversal of the convergecast-tree from each node in the plurality of the nodes to the base-station; and
a transmitting mechanism configured to perform packet transmissions in the convergecast-tree using the scheduled order;
wherein performing the convergecast operation using the scheduled order substantially optimizes the convergecast operation by reducing a total number of timeslots required to complete the convergecast operation.
24. The apparatus of claim 23 , wherein the construction mechanism includes:
a broadcasting mechanism configured to broadcast a message from the base-station to all one-hop neighbors of the base-station; a
a propagation mechanism configured to propagate the message to each node in the plurality of the nodes through broadcast forwarding with duplicate suppression; and
a tree-construction mechanism configured to construct a shortest-hop-count tree to form the convergecast-tree.