TMCnet News
A Nodes Deployment Algorithm in Wireless Sensor Network Based on Distribution [Sensors & Transducers (Canada)](Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: Wireless sensor network coverage is a basic problem of wireless sensor network. In this paper, we propose a wireless sensor network node deployment algorithm base on distribution in order to form an efficient wireless sensor network. The iteratively greedy algorithm is used in this paper to choose priority nodes into active until the entire network is covered by wireless sensor nodes, the whole network to multiply connected. The simulation results show that the distributed wireless sensor network node deployment algorithm can form a multiply connected wireless sensor network. Copyright © 2014 IFSA Publishing, S. L. Keywords: Wireless sensor network, Nodes deployment, Distributed. (ProQuest: ... denotes formulae omitted.) 1. Introduction With the rapid development of wireless communication, integrated circuits, sensors and Microelectro Mechanical Systems (MEMS), etc., sensor information acquisition technology has been gradually developed from simplification in past towards the direction of integrated, microcomputer and network, thus wireless sensor networks bom out. Wireless sensor network is known as the key technology of the fourth industrial revolution of the IT industry and the first of the ten technologies affecting humans, which have the characteristics of large-scale, self-organizing, strong data processing energy, good adaptability, etc. [1]. In other countries, wireless sensor networks were first proposed by Defense Advanced Research Projects Agency (DARPA) in 1978, based on research projects for military applications. Subsequently the University of California's "Low Power Wireless Integrated Microsensor" research submitted to DARPA definite the characteristics and promising of the network structure. More well-known laboratories and research projects, includes the Wireless Integrated Network Sensors (WINS) project and Center for Embedded Networked Sensing (CENS) Laboratory in University of California, Los Angeles (UCLA), Berkeley Wireless Research Center (BWRC) and Wireless Embedded System (WEBS), Bay Area Research Wireless Access Network (BARWAN) of University of California, Berkeley (UC Berkeley), CodeBlue of Harvard University and Yale University's Embedded Networks and Application, etc. [2], To date, researchers have developed many operating systems which can be used for the actual sensor nodes and wireless sensor networks. Among them, the most representative of sensor nodes include PicoNode from BWRC, and MICA series node exploited with Crossbow Company, Medusa MK-2 node developed by UCLA, and Intel Mote node developed by Intel. More famous sensor network operating system includes TinyOS exploited by UCB, SOS exploited by UCLA and MANTIS exploited by Colorado. UCB sensor network operating system developed at the University of TinyOS system. U.S. Department of Transportation also proposed to be fully operational, "the National Intelligent Transportation System Project Plan" in 2025 [3]. In China, the research for wireless sensor networks started late, in 2002 it was formally conduct research projects in wireless sensor networks, but investment is very large. Currently, the domestic large number of sensor networks is based on the majority of studies of some famous node hardware platform, and mainly focused on the research of wireless communication protocols, data fusion technology, low energy consumption and high safety performance, positioning technology and so on [4], Since then, some issues and related projects based on wireless sensor network platform are verified by the National Natural Science Foundation of China successively. In 2004, the theory and technology based on the characteristics of self-organization of wireless sensor networks distribution were included in major special projects of the National Natural Science Foundation of China. In the next year, basic theoretical and applied research related technology was included in the 863 major issues; in 2006, China began to carry out related research underwater mobile wireless sensor network deployment and positioning. In March 2006, researchers proposed three cutting-edge information technology development direction of China in the 'Long-term Science and Technology Development Plan' issued by the State, there are two directions based on wireless sensor network technology which are IntelliSense technology and self-organizing network technology [5]. There are a total of 157 IT technology in a major report on the technical scientific research of the future can be achieved in two decades published in 2009, and seven of which are based on wireless sensor networks. Wireless sensor network technology has become the focus of development of the industry in the National Vision Plan and the "Eleventh FiveYear Plan" assigned in 2010[6]. At present, the research results has the 3DP core communication protocol for wireless sensor networks, which is independently developed with independent intellectual property rights by laboratory of wireless sensor networks of Graduate University of Chinese Academy of Sciences, and its key performance indicators are better than other international mainstream ZigBee protocol. Shanghai Institute of Microsystem and Information Technology of Chinese Academy of Science make some of the key technology and equipment for wireless sensor networks deep into a large-scale civilian system within seven years, such as transportation, public safety systems, etc. [7]. The research of wireless sensor networks identified a number of future research directions and trends, which is as follows: 1) Miniaturized nodes. It is an important research direction to design micro-volume sensor nodes using modem technology. The smallest volume of the sensor nodes are dust sensor nodes developed by the University of Berkeley, approaching 1 mm 3 size, and they can float in the air [8]. 2) Adaptive network protocol. Depending on difference of the application environment for wireless sensor networks, wireless sensor networks have different characteristics required. The wireless sensor networks used in temperature detection don't ask for timeliness, military requirements for adaptability are very high, and traffic warning has high requirements for the speed and timeliness. Therefore, the network protocols deployed sensor network is based on different applications vary widely. And with expanding of the application its network protocols need to have more capability flexibility, adaptability, self-configuration [9]. 3) Integration of wireless sensor networks and other networks. With the development of Internet and mobile communications networks, wireless sensor networks are maturing. The wireless sensor network is a closed network, and its storage is limited, therefore, the wireless sensor network seamless access to the Internet or mobile communications networks, can not only expand the store of wireless sensor network, but also achieve a wide range of information sharing. In addition, a data collection which is the unique characteristics wireless sensor networks have can be used as infrastructure been vigorously promoted. Also greatly enhance the wireless sensor network data processing capabilities. In this integration the of value wireless sensor network technology its will increase sharply [10]. Wireless sensor networks are multi-hop ad-hoc network formed via the radio communication which is deployed in the detection area of a large number of tiny sensor nodes. Wireless sensor networks have many sensor types, which be used to detect temperature, electromagnetic, humidity, pressure, composition of the soil, the speed and direction of the moving object, etc., and assist real-time to percept, collect, process and release information in the network coverage area to detect objects. It is widely used in military, disaster relief, environmental monitoring, health care, disaster warning, space exploration, industrial automation, and so on. With ease of deployment, communication and flexible, low cost, low power consumption [11]. Depending on the difference of configuration of the sensor nodes wireless sensor networks can be deployed into deterministic and random deployment [12]. 4) Deterministic coverage. When the wireless sensor network environment to be deployed is known and working state is fixed relatively to a known and the state, it's deterministic manner deployment deployed by a robot or manual deployment. Also a first pre-configured sensor node position to determine the network topology of a coverage problem. Thus, certainty deployed node location is obtained by calculating the optimization in front of the network node configuration. Its data transmission path also planed advanced. In short, the problem is the certainty deployment is a particular network or path planning problem. 5) Randomness coverage. Compared to deterministic deployment, the difference in the randomness of deployment is its particularity of application environment. It's often used in war, fire, earthquake or other dangerous or harsh environments. It's more difficult to implement or not implement deterministic nodes deployed in such environments, and therefore use more random throw random deployment to solve the problem. Nodes spilled random don't know position information of them in advance, is formed by the self-organizing network and the topology control, complete coverage of the detection areas task. In this process the first need is the minimum density of the node in detect area, to run a sufficient amount of sensor nodes to ensure that their degree of coverage and network connectivity. Then starting from the energy efficiency and network performance perspective, to analysis and calculate receiver / transmitter or cluster head position. Usually it can be divided into two categories of random node deployment and dynamic network deployments. Working status of wireless sensor networks is in the operation of the wireless sensor network, whether the node moves, and whether a node is sleeping or replaced. The network is dynamic if the node moves or nodes working conditions often change; on the contrary, the network is static. The static deployment: Once the static deployment of nodes are completed, in the course of their work throughout the network, either working condition location of the node or network structure will no longer be any change, until the node energy is depleted or destructed then bring down the network. The evaluation of the best location is based on the optimization strategy or performance index alternatively, and run mode usually passes data through predefined route. And deployment scenarios are independent of the state of the network and work throughout the network lifecycle. According to optimize the object, the static deployment can be divided into extent of coverage, network connectivity and energy efficiency. Such as data transfer rate, the perception radius and the multi-hop affect its performance. The dynamic deployment: Dynamic deployment of network can be divided into two cases: First, the node has a function of mobile. Nodes can be deployed individually. Deployed position according to the optimal target by the node have been deployed calculate the next node, to achieve the finally optimal results; Another case is the work process in the network, when a node can not work due to depletion of energy resources or destroyed, can be re-deployed throughout the network via a mobile node and continue to ensure the normal operation of the network. The latter is the case for the other when there is redundant network node via the sleep command node so that the network has enough reserve nodes. Node covering method can be centralized, distributed or local. For a centralized algorithm, it is calculated by a decision node and determines node deployment based on the information of the entire network. For example: covering the application of the method used the Voronoi diagram proposed by Anthony et al for determining, using the concept of order k Voronoi diagram to test network coverage. Such algorithms run slower, low efficiency, the communication capacity of decision nodes and energy demanding are high. The nodes in distributed or local algorithms decide the status information of the node based on their neighbors. For example, Wang et al proposed the CCP and SPAN protocol combining methods to achieve coverage and network connectivity. CCP algorithm is a distributed control strategy. They determine the status of the nodes, local, meanwhile and autonomously. Its efficient is higher than centralized algorithm. Existing coverage algorithm does not consider the connectivity of the multi-node, especially when the communication radius is smaller than the sensor radius under 2. For example, a heuristic greedy deployment algorithm proposed by Yan et al, which consider only the coverage of the target node and not considered connectivity. Chinh, who proposed a distributed algorithm based on the perimeter covered only consider the situation when communication radius greater than or equal to 2 of the sensor radius. Algorithm proposed by Wang and Tian dose not considers node energy when select a node, and has a high redundancy node. In this paper, we present a distributed node deployment algorithm under the circumstances when communication radius is less than 2 to the sensor radius. The monitoring area is divided into a grid. We select the node into an active state according to the energy grid node and coverage contribution, making the monitoring area to achieve k covering and the multiple nodes to achieve connectivity, while the remaining nodes go into hibernation. 2. Description of the Problem 2.1. Network Model Wireless sensor network layout of rectangle target area in a two-dimensional plane A. Nodes are randomly deployed in the area A. The node uses the most common model, Boolean model (0/1 model): 1) Assume the Euclidean distance between s deployed in (x^,^) and p deployed in (xp,yp) is d(s,p), then the 0/1 model can be expressed as: ... (1) where R is the sensor radius, C (5) is the probability of P covered by s. 2) The two nodes S. and S is expressed as Euclidean distance, if d(s,p) < Rs, then S. and S can communicate with each other directly, otherwise it cannot communicate directly. Usually a sensor node includes the following modules: MCU: Primarily responsible for computing; Radio: Send and receive messages; Sensor: Aware of their surroundings, to collect relevant information; Node state usually has three modes: listening state, active, dormant state. Definition 1: If the P is covered by K sensor nodes, then called the P as K covered. If any point in a given area R achieves K coverage, said the region R is K covered. Definition 2: The set of a given region R of the n node is S = if for any 2 nodes S.,S. G S, there is at least 1 path between them, then called node in the network is connected. If there are at least 2 paths between them, then called node in the network achieves multi-connected. Definition 3: For a given region R and the node set S, if S', the subset of S is the set covering of the region R, then S' is called for the minimal covering set. Among them, including the number of nodes at the minimum covering set called the minimum covering set. Definition 4: The greedy principle. According to the current situation regardless of the variety of possible overall situation the optimal choice based on the optimal measurement. It uses a top-down, and makes successive iterative greedy choice to ensure access to local optima on each step to obtain approximate solutions of the overall optimal solution, thus greatly reducing the time required for the algorithm. 2.2. Analysis Existing algorithm for multi-node distributed deployment is covered under the premise Rc > 2Rs. There are two reasons: 1) When Rc > 2Rs, sensing disc the intersection between the two nodes can communicate with each other, a distributed algorithm for easy operation; 2) When Rc > 2Rs, the nodes in the network coverage reaches k, the nodes are bound to achieve k connectivity. This algorithm goal is to achieve a distributed multi-k connectivity deployment under the conditions of Rc > 2Rs. The consumption of node energy in sleep mode is only 1 % as it in active state. Sensor nodes deployed randomly in the monitoring area A are more densely. If all nodes are in the active state would undoubtedly have been wasting a lot of energy. Therefore, we set the algorithm based on rounds. Before the start of each round all nodes are in the listening state, then select the minimum cover set C = {s.,...S ,...} into active state, makes multi-network connectivity coverage reaches k, the remaining nodes into hibernation. The minimum cover set for solving the problem, which is an NP-hard problem. In this article we use the principle of solving their greedy approximate solution; the algorithm model can be expressed as follows: The input of the algorithm: Nodes are randomly deployed in A 5 = {.Sj, S2,..., Sn } . The output of the algorithm: C = {s.,.. .5\,...} . The basic assumptions: The collection of nodes S = are dense enough, which can guarantee the A at least k covered with. Boolean model is used in sensor nodes, and each all nodes have the same sensor radius R and s communication radius R , and R >2 R . c ' c s The same place only has one node; each sensor node knows its own location information. Each node has a clock, and each time can keep synchronization. Algorithm objectives: 1. CcS 2. Min ICl 3. Vpe A,covp >k 4. The nodes in C achieve multiple connectivity 5. Max (tend ~t0), tend Jo denote the start time and termination of the network respectively. 3. Covering Algorithm 3.1. The Main Process © All nodes in the listening state at the start of each round. Divided the region A into W*L square grids of ..., and then update residual energy of each node <?,. For all neighboring cells M and N, identify each node pair locate in neighboring cells within the communication range. ... (2) where M and N are two vertically or horizontally adjacent grids. d(SpS.) is Euclidean distance of (s.,S ), Rc communication radius of nodes. Calculates the corresponding communication priority P of the highest priority P becomes the active node of the node based on the distance and the residual energy of the node between SC^ ; ... (3) where e. and e are the remaining energy of S., S respectively, z is probability of occurrence in the same of 0-1 random number for reducing. © In this case, only one node is active state grid, and repeat the above steps wherein any one of the neighbors listening state the mesh node to ensure the completion of each grid © at least two nodes in the active state. © For each grid: if does not reach k covering, then calculate covering priority of each node according to the residual energy and the covering contribution c. Select the node with the highest priority becomes active; ... (4) where z is the random number of 0-1. © Updated coverage of the grid, if the grid reaches k cover then all the nodes in the grid in listening state go into hibernation; otherwise turn ©. 4. Performance Analysis 4.1. The Time Complexity Analysis Let the total number of initial node N, a region is divided into W*L square grid of ... there are average ... nodes within each grid. Algorithm step ©, choose between two communicating nodes adjacent mesh up with the time ..., there are (W-l) x (L-l) of neighboring cells, so the first step time is 0(N2). Connectivity priority is decided by the distance between the node and the residual energy. Dense grid node, non-boundary mesh grid has four neighbors. When the © ends, at least two nodes in the grid change into active state. So step © mainly spend time in the steps © and ©, which is 0(N2). In algorithm steps © and ©, each grid is a distributed execution, the main aspect is the coverage contribution to the calculation node, and the time complexity is 0(N). Therefore, the time complexity of the algorithm is 0(N2). 4.2. Connectivity Analysis Definition 5: Heavy connected graph. In graph G, if you delete the vertices v and v-related side, a connected component in graph G is divided into two or more connected components, and then the vertex v is called joint. A connected graph with no joints is called heavy connected graph. In heavy connected graph, there are at least two paths between any pair of vertices, nor undermine the connectivity graph by deleting a vertex and its associated each side. Theorem 1 : The formation of Figure G3 is still heavy connected graph plus side in two heavy connected graphs Gl and G2 between two different vertices. As shown in Figure 1, both Gl and G2 are heavy connected graphs. The formation of Figure G3 is still heavy connected graph plus side in two pairs of joins <3,5x4,8>. Proof: Both Gl = (V, E) and G2 = (V , E ) are heavy connected graphs. Add side between two pairs of vertices. Without loss of generality, assume that ax,a2 e V, bx,b2 e V . Add two sides < avb{ > and < a2,b2 > then form graph G3. Assume that G3 is heavy connected graph, so there must be a joint in G3 according to the definition of the heavy connected graph. Because Gl and G2 are heavy connected graphs, joints of G3 appear only in ava2,bvb2. If a vertex and its associated edges in ax, bx are removed, it can be connected by < a2,b2> between Gl and G2, and G3 is still a connected graph, So avbx is not the key point. Similarly, If a vertex and its associated edges in ct2-,b2 are removed, it can be connected by < ax, b{ > between Gl and G2, and G3 is still a connected graph, So a2,b2 is not the key point too. So there is no joint in G3, which is contradicting to the hypothesis. So G3 is heavy connected graph. In the algorithm of this paper, we take active state of the node as is the vertex. There is graph formed by one edge between the nodes communication range. For the same grid node can communicate with each other, so that each grid can be seen as a heavy connected graph. There exist at least two different sides in each grid mesh with neighbors. Therefore, the graphs made up by active nodes in the entire network are heavy connected graphs, that there are at least two paths between any two nodes. Therefore, the network reaches more than connectivity. 5. Simulations and Analysis In order to verify the performance of the algorithm, in this paper, we simulate the algorithm in MATLAB software, to compare with CCP algorithm based active node number under different coverage; Impact on the active node number under different sensor radius; Network lifetime under different coverage compared with CCP. The simulation environment is a square area of 400 m x 400 m, and throw 2000 node randomly in the regional. The sensor radius R =25 m * Fig. 2 shows this algorithm compared with CCP algorithm based active node number under different coverage. The sensor radius p = 25 mWith the improvement of the network coverage, the active nodes in network increased significantly. By contrast with the CCP protocol, you can see the number of active nodes in the network using this algorithm is significantly less than the number of active nodes in the network protocol of the CCP. When the coverage is 3, the active nodes number of two algorithms about the same. With the improvement of coverage, the number of active nodes between two algorithms increases. This shows that the algorithm in this paper take contribution of the nodes on the network coverage into consideration so that it reduces the number of nodes in the active state, while ensure the ensure coverage and connectivity requirements. Fig. 3 shows the impact on the active node number under different sensor radius. Perception of the same radius, the higher the coverage, the more active the status of nodes; the same cover, as the sensing radius increases, the number of active nodes reduce. This shows that, when the sensing radius becomes large, and in order to meet the perceived effect, the number of the active nodes becomes small; the lager of the coverage, the smaller the trend curve. Fig. 4 shows the impact on the active node number under different communication radius. Perception of the same radius, the higher the coverage, the more active the status of nodes; the same cover, as the sensing radius increases, the number of active nodes reduce. This shows that, when the sensing radius becomes large, and in order to meet the perceived effect, the number of the active nodes becomes small; the lager of the coverage, the smaller the trend curves. Fig. 5 is the comparison of network lifetime between this algorithm and CCP algorithm under different coverage. 6. Conclusion In this paper, we propose distributed k-covering multiple connectivity node deployment algorithm based on networks, for wireless sensor networks under random high-density deployment and communication radius of sensor nodes less than 2 times of sensor radius. The simulation results show that this algorithm can extend the life of networks while ensure network coverage and connectivity. The simulation results show that the distributed wireless sensor network node deployment algorithm can form a multiply connected wireless sensor network. References [1]. D. Wang, B. Xie, D. Agrawal, Coverage and lifetime optimization of wireless sensor networks with Gaussian distribution, IEEE Transactions on Mobile Computing, Vol. 7, Issue 12,2008, pp. 1444-1458. [2]. Z. Meng, Z. Wang, Research on the node deployment of large-scale wireless sensor networks, Journal of Chinese Computer Systems, Vol. 31, Issue 1, 2010, pp.13-16. [3]. Qin Tao, Guan Xiaohong, Li Wei, Dynamic features measurement and analysis for large-scale network, in Proceedings of International Conference on Communications, 2008, pp. 212-216. [4]. Q. Luo, Z. Pan, An algorithm of deployment in small-scale underwater wireless sensor networks, Chinese Journal of Sensors and Actuators, Vol. 24, Issue 7,2011,pp. 1043-1047 (in Chinese). [5]. Y. Zou, K. Chakraharty, Sensor deployment and target localization in distributed sensor networks, ACM Transactions on Embedded Computing System, Vol. 3, Issue 1,2004, pp. 61-91. [6]. M. Zhu, X. Zhang, Sensor scheduling algorithm for connected coverage in wireless sensor networks, Application Research of Computer, Vol. 29, Issue 8, 2012, pp. 3091-3095 (in Chinese). [7]. Wen-Hwa Liao, Yucheng Kao, Ying-Shan Li, A sensor deployment approach using glowworm swarm optimization algorithm in wireless sensor networks, Expert Systems with Applications, Vol. 38, 2011, pp. 12180-12188. [8]. Y. Wang, C. Tian, B. Huang, Localization algorithm for 3-D underwater wireless sensor networks with surface-deployed anchors, Microelectronics & Computer, Vol. 27, Issue 10,2010, pp. 65-68. [9]. X. Bai, Z. Yun, D. Xuan, et al., Pattem mutation in wireless sensor deployment, IEEE/ACM Transactions on Networking, Vol. 20, Issue 6, 2012, pp. 1964-1977. [10]. Y. Liu, Wireless sensor network deployment based on genetic algorithm and simulated annealing algorithm, Computer Simulation, Vol. 28, Issue 5, 2011, pp. 171-174. [11]. M. L. Yiu, N. Mamoulis, Aggregate nearest neighbor queries in road networks, IEEE Transactions on Knowledge and Data Engineering, Vol. 17, Issue 6, 2005, pp. 820-833. [12]. H. Zhang, Z. Zhou, C. Pan, et al, Particle swarm optimization approach of wireless sensor network node deployment for traffic information acquisition, Chinese Journal of Scientific Instrument, Vol. 31, Issue 9,2010, pp. 1991-1996. (in Chinese). Song Yuli, Zhang Hongdong Qingdao Vocational and Technical College of Hotel Management, Shandong, Qingdao, 266100 Tel: 18661892837 Received: 2 July 2014 /Accepted: 28 July 2014 /Published: 31 July 2014 (c) 2014 IFSA Publishing, S.L. |