摘要：We propose a ben chmarking algorithm to determin e the sequ ence of longest-living stable d ata gathering trees for wireless mobile sensor networks whose topolo gy changes dynamically with time due to the random movement of the sensor nodes. Referred to as the Max.Stab ility-DG algorithm, the algorithm assumes the a vailability of complete knowledge of future topology changes and is based on th e following greedy principle coupled with the idea of graph intersections: Whenever a new data gathering tree is required at time instant t corresponding to a round of data aggregation, choose the longest-living data gathering tree from time t. The above strategy is repeated for subsequent ro unds over the duration o f the lifetime of the sensor network to obtain the sequence of longest-livin g stable data gathering trees spannin g all the live sensor nodes in the network such that the number of tree discoveries is the global minimum. Thus, the number of tree discoveries incurred with the Max.Stability-DG algorithm will serve as the lower bound for the number of discoveries for any network-wide communication topology (like spannin g trees and connected dominating sets) determin ed through any other algorithm for data gathering in mobile sensor networks under identical operating conditions. In addition to theoretically proving the correctness of the Max.Stab ility-DG algorithm, we also conduct exhaustive simulations to evaluate the performance of the Max.Stability-DG trees and compare to that of the minimum-distance spannin g tree based data gathering trees with respect to metrics such as tree lifetime, delay per round, node lifetime, network lifetime and coverage loss time, under both sufficient-energy and energy-constrained scenarios
关键词：stability; data gathering tree; mobile sensor networks; tree lifetime; network lifetime; coverage loss ti me
