Section 3 introduces our graph theory algorithm to generate a rooted directed minimum-weight spanning tree of the sensor network and describes the execution of the pre-order, in-order and post-order traversal algorithms.
Algorithm for Post-Order Traversal of the Rooted Directed Minimum-weight Spanning Tree Input: Rooted Directed Tree rd-MST([V.sup.rd], [E.sup.rd]), Root node r-node Output: PostOrder-Sequence Auxiliary Variables: Child-Nodes-List, Sensor node u Initialization: PostOrder-Sequence = [PHI] u [left arrow] r-node Begin PostOrder-Traversal (u) 1.
The maximum relative improvement in the round of first node failure can be as large as 30% (obtained for post-order traversal on 100m x 100m network, TDMA system).
In terms of the absolute values, the chain obtained through a post-order traversal of the rd-MST yields the largest value for node lifetime in all the four scenarios shown in Fig.
Among the tree traversal algorithms, PEGASIS chain constructed based on pre-order traversal resulted in the largest energy loss per node and the PEGASIS chain constructed based on post-order traversal yielded the lowest energy loss per node.
The high-level technical contribution of this paper is to illustrate the effectiveness of using the traditional graph theory tree traversal algorithms (such as the pre-order, in-order and post-order traversals) to generate the chain of sensor nodes for PEGASIS data aggregation.
Depending on the order in which the vertices are visited, starting with the root vertex, there exist three different types of tree traversal algorithms: pre-order, in-order and post-order traversals. The three traversal algorithms can be easily described through recursion (as illustrated in the pseudo codes of Fig.