A Restricted Delaunay Triangulation Graph Based Algorithm

Journal of Computational Information Systems 6:10 (2010) 3155-3162 Available at http://www.Jofcis.com A Restricted Delaunay Triangulation Graph Based Algorithm for Self-Deployment in Mobile Sensor Networks † Jun LI , Baihai ZHANG, Lingguo CUI School of Automation, Beijing Institute of Technology, Beijing, 100081, China Abstract Self-deployment is one of the main research issues in wireless mobile sensor networks. It determines quality of service of networks, such as coverage and connectivity. A suitable topology is very important for self-deployment based on virtual force.

In this paper, we discussed the performances of topology graph by theory analysis. Then we presented a restricted Delaunay triangulation graph based algorithm (RDTG) for self-deployment in mobile sensor networks. RDTG constructs a logical topology graph without intersection of edges, and tries to make the node’s neighbor equal to 6 by moving the node according the property of maximum the minimum angle of the triangles in TDG. Simulation results show that self-deployment by virtual force based on RTDG is effective to reach the ideal deployment with good performances. Keywords: Restricted Delaunay Triangulation Graph; Virtual Force; Self-Deployment; Mobile Sensor Networks 1. Introduction Mobile sensor network is composed of nodes which have communication, sensing, computation, and locomotion capabilities. In many working environments, such as remote harsh fields, disaster areas, and toxic gas regions, sensor nodes cannot be deployed manually. In these situations, to deploy mobile sensor nodes by air drop is one possible solution. Mobility of sensor nodes allows more complex application scenarios. Coverage is one of the most important issues of wireless sensor networks. It can be consider as the measure of QoS in a WSNs. There are two aspects of work on coverage in mobile sensor networks. Many efforts have been put on algorithms to reposition sensors in order to obtain a required placement for improving coverage. In this self-deployment issue, sensor nodes remain stationary after the reposition. Another related research focuses on the dynamic behavior of nodes’ movement for detecting and monitoring targets. In this paper, we study the self-deployment problem. Because of random errors in stochastic placement, the initial deployment may not satisfy the requirement. Mobile sensor nodes can self-deployment after the initial deployment, enhance the coverage and reach more precise placement. Previous work on self-deployment issue of mobile sensor networks can be divided into three categories: force based, grid based and computational geometry based. In force based strategy, nodes move toward or away each other by their virtual forces or fields. Potential fields (PFA) proposed by Howard [1], Virtual † Corresponding author. Email address: lijunfigo@bit.edu.cn (Jun LI), smczhang@bit.edu.cn (Baihai ZHANG) 1553-9105/ Copyright © 2010 Binary Information Press October, 2010 3156 J. Li et al. /Journal of Computational Information Systems 6:10 (2010) 3155-3162 forces (VFA) proposed by Zou [2], DSSA proposed by Nejeong [3] and SDDC proposed by Chang [4] are force based self-deployment algorithms. Almost all the virtual force algorithms assume that the communication range R c...

Website: www.jofcis.com | Filesize: -
No of Page(s): 8
Download A Restricted Delaunay Triangulation Graph Based Algorithm for Self ....pdf