On Optimal Path Computations in Intensive Messaging Environments
Sudarsanan Nesamony · The University of Queensland · 2008
Recent manifestations of messaging environments are prominently in the form of RFID tags and wireless Sensor Networks. New practical applications are envisioned and the existing ones are benefitted by flexible and comfortable execution of processes, with immediate access to real data. There is a plethora of research issues from various spheres, associated with every stage of the network, from setup until maintenance. Driven by a specific Sensor Network as the motivational application, we focus on the computational aspects of setting up such a network from an algorithmic perspective, in this dissertation. The network in consideration contains stationary sensor nodes scattered in a hostile ground and a sink node equipped with mobility which is regulated to perform desired tasks like data-collection, calibration, recharging etc. over the set of sensors. Of the many associated design problems in such a setting, we specifically concentrate on computing the optimal path of the sink node in various characterisations of the application environment. Firstly, a taxonomy of shortest path problems in their abstract form derived from the application background is constructed and the generalisation relations are specified. A particular case of having k sink nodes, where k > 1, is taken for consideration where they are to visit the sensors’ positions to orchestrate the desired tasks. We address the problem with the objective function being minimising the longest path travelled by the sinks, bounded by application specific constraints. The problem is formulated and thoroughly analysed for the related literature and considering its intractability, certain heuristic approaches are presented for the special case consisting of two sinks. We further examine the case where the shortest path of a single mobile sink is sought, which collects data from all the positioned sensor nodes. This problem is abstracted and formalised and is identified to be a version of the TSPN problem. A regressive method to solve the problem in the general case, is constructed based on a set of developed conjectures. Two additional problems are then attended, with one being the case of the calibrating mobile sink and the other being the conceptual generalisation of both the previous and the above TSPN problem. They both are reduced to the solved TSPN problem instances. The proposed algorithms are evaluated over randomly generated dataset to test their performance and endurance. The methods are pitted against corresponding brute force methods and different approaches within the developed procedures are also compared against each another. The traditional trade off between accuracy and execution time reverberates in the observation of our results and the compromise reached by the developed procedures is very favourable. Finally, following the discussion on the generality and specificity of the studied problems, the possible extensions are highlighted which are promising enough to take the existing research forward.