Coverage Algorithms in GPS-less Wireless Mobile Sensor Networks
讲座时间：2013年4月15日 10:00 am
Chang Wu Yu (俞征武) was born in Taoyuan, Taiwan in 1964. He received the BS degree from Soochow University in 1985, MS degree from National Tsing Hua University in 1989, and Ph.D. degree from National Taiwan University in 1993, all in computer sciences. Currently, he is a professor of the Department of Computer Science & Information Engineering, Chung Hua University, Taiwan.
Prof. Yu received best paper awards at 2008 ACM International Conference on Sensor, Ad Hoc, and Mesh Networks and at both 2004 and 2007 Mobile Computing Workshop. Prof. Yu have published more than 60 papers (including Journal on Selected Areas in Communica-tions (JSAC), IEEE Transactions on Parallel and Distributed Systems, Theoretical Computer Science, ACM/Springer WINET, Elsevier Com-puter Communications, Ad Hoc Network).
The coverage problem, being one of fundamental problems in wireless sensor networks, has been received lots of attention. To preserve the coverage of network, some researches suggest moving redundant mobile sensor nodes to uncovered areas for mitigating the problem. Most of previous approaches require location information of sensor nodes to calculate and determine redundant nodes, to detect uncovered areas, and to move those nodes to their pre-determined areas. However, to acquire location information will increase the cost of hardware for deployment, extra computation and communication delay, and additional message overhead and power consumption. In some cases, it becomes difficult to acquire location information. In this work, without exploiting any location and distance information, six distributed algorithms are devised for mitigating the un-coverage problem. The first three distributed algorithms including the neighborhood density detecting algorithm, the random walk algorithm, and the dripping rain algorithm detect uncovered areas, redundant mobile sensor nodes, and direct them to move to cover the uncovered areas, only basing on the number of neighbors of each node and consuming little extra control packets. The expected number of required neighbors and the probability of an arbitrary node being a redundant node are derived theoretically. Moreover, based on the obtained formula, the last three randomized algorithms are developed by modifying the first three algorithms. Simulation results demonstrate that the proposed coverage algorithms can achieve at most 90% coverage rate in a GPS-less sensor network