An important requirement in some wireless sensor network (WSN) applications is the need to guide a mobile agent, such as a mobile robot, user, or unmanned aerial vehicle (UAV), toward event-triggered sensor nodes or a specific event location. If the event locations change dynamically, it is necessary to dynamically update the path from the mobile agent to the sensor nodes of the newly triggered event. This paper proposes a distributed protocol to construct and update the dynamic paths between the mobile agents and the event sensor nodes. The distributed algorithm uses Voronoi diagrams containing the event-triggered nodes, and is shown to provide suboptimal paths with a competitive ratio O(log k), where k is the number of event sensor nodes.
The paper first discusses Voronoi diagram construction in WSNs. The authors propose and describe the distributed protocol steps to be run on the sensor nodes: 1) initialization and maintenance of Voronoi diagrams; 2) nearest event search and locking; 3) Voronoi diagram updating; and 4) path updating. The data packet payload and communication overload necessary for such distributed protocol steps is discussed. The authors describe their theoretical analysis of the length of the constructed path and the competitive ratio when compared to the optimal constructed path.
They also discuss some extensions to the distributed algorithm for tasks such as updating paths with moving users, deleting events, constructing event node visiting tours (rather than paths) that come back to the original agent position after visiting the event nodes, constructing paths for multiple users, and handling node failures. Finally, a simulation study is performed to evaluate performance parameters such as path length and message complexity. The proposed algorithm is compared with two algorithms: the greedy vertex algorithm (GVA) and the traveling salesman problem (TSP) solution.
Although this research problem has been attempted previously in the literature, I recommend this paper for professionals interested in using Voronoi diagrams for a graph theory approach to WSNs.