|
Abstract:
|
Delaunay triangulation (DT ) is a useful geometric structure for net -working applications . We define a distributed DT and present a necessary and sufficient condition for a distributed DT to be correct . This condition is used as a guide for protocol design . We investigate the design of join , leave , failure , and maintenance protocols for a set of nodes in d -dimension (d > 1 ) to construct and maintain a distributed DT in a dynamic environment . The join , leave , and failure protocols in the suite are proved to be correct for a single join , leave , and failure , respectively . For a system under churn , it is impossible to maintain a correct distributed DT continually . We define an accuracy metric such that accuracy is 100 % if and only if the distributed DT is correct . The suite also includes a maintenance protocol designed to recover from incorrect system states and to improve accuracy . In designing the protocols , we make use of two novel observations to substantially improve protocol efficiency . First , in the neighbor discovery process of a node , many replies to the node's queries contain redundant information . Second , the use of a new failure protocol that employs a proactive approach to recovery is better than the reactive approaches used in prior work . Experimental results show that our new suite of protocols maintains high accuracy for systems under churn and each system converges to 100 % accuracy after churning stopped . They are much more efficient than protocols in prior work . To illustrate the usefulness of distributed DT for networking applications , we also present several application protocols including greedy routing , finding a closest existing node , clustering , broadcast , and geocast . Bose and Morin proved in 2004 that greedy routing always succeeds to find the destination node on a DT . We prove that greedy routing always finds a closest existing node to a given point , and our broadcast and geocast protocols always deliver a message to every target node . Our broadcast and geocast protocols are also efficient in the sense that very few target nodes receive duplicate messages , and non -target nodes receive no message . Performance characteristics of greedy routing , broadcast , and geocast are investigated using simulation experiments . We also investigate the impact of inaccurate coordinates on the performance of greedy routing , broadcast , and geocast . |