Research On Some Routing Related Problems In Wireless Sensor Networks

Wireless Sensor networks (WSNs) are integration of sensor techniques, nestedcomputation techniques, distributed computation techniques and wirelesscommunication techniques. They can be used for testing, sensing, collecting andprocessing information of monitored objects and transferring the processed informationto users. Sensor network is a new research area of computer science and technologyand has a wide application future. Both academia and industries are very interested init.Many technologies related to WSNs are still explored, such as routing algorithm,energy management, data security and QoS assurance, etc. If they can be designedsuccessfully and implemented effectively, WSNs' potential and great values can beproduced and transformed into productivity. Therefore, this paper mainly focuses onrouting model and algorithm for WSNs, some model and algorithm of designingWSNs' routing are discussed and presented as follows:1. The QoS assurance of WSNs is discussed in this paper. On the basis of theframework of WSNs' layer, the QoS requirement of individual layer is anlysiseddetailedly.2. The delay constainted energy efficient routing problem is analysed in the paper.The formal description of problem and its NP-Complete is given with reduction fromthe knapsack problem. Both central and distributed approximation algorithm for theproblem is presented with performance of algorithms is discussed. And theexperiments show: the approximation algorithm is near to the optimal with its runningtime is small which is much better than the SAR Protocol.3. On the basis of analysing the used energy of sensor nodes' communicationstatus, a model with reformed finite-state machine to predict the remaining energy ofits neighbor nodes is presented in this paper. In the reformed finite-state machine, theatributes which we extend is attached to the status and events of machine and join thecomputation. And an energy-prediction-based routing algorithm based on this reformedfinite-state machine is designed, which balance the energy consuming of sensor nodes,prolong the network survival, without extra mechanism to gather the information aboutresidual energy of neighbor nodes. The experiments show: this energy prediction basedrouting algorithm is better than the Gossiping protocol with longer network survival.4. In this paper we address the problem of optimizing a scalable hiberarchyrouting model and the goal of the optimization is to reduce the cost of deployment of the hiberarchy infrastructure by identifying a minimum cluster header set subject todelay constraint on the routing path. This problem is NP-hard by provement withreduction from vertex cover problem and approximation algorithm for the selection ofcluster header and distributed algorithm for the assignment of cluster member arepresented. The performance and running time of approximation algorithm is analysed.The experiments compare the different way about assignment of cluster member anddiscuss the influence of network attibute on relative imbalance factor.5. In wireless sensor network, given a collection of source-destination pairs, howcan we schedule the packet through link in wireless sensor network which can transferdata from the sources to their corresponding destinations efficiently? There are manyfactors effecting this question and this problem is non-trivial to solve in the case ofwireless sensor networks due to interference. In this paper the problem of efficientlylink scheduling algorithm in wireless sensor networks with interference is focused andit is NP-Complete by provement with reduction from vertex cover problem. Centralalgorithm with performance guarantee is presented. And distributed algorithm withprediction of collision number and analysis of running time is presented.