Download to read offline
![ACEEE International Journal on Network Security, Vol 1, No. 2, July 2010 A Fuzzy Based Priority Approach in Mobile Sensor Network Coverage Bahareh J. Farahani, Hossein Ghaffarian ,Mahmood Fathy Computer Engineering School, Iran University of Science and Technology, Tehran, Iran Farahani.ict@gmail.com, Ghaffarian@iust.ac.ir, MahFathy@iust.ac.ir Abstract— In this paper a new fuzzy based approach for effectiveness of this algorithm, our algorithm is improving network coverage in wireless mobile sensor compared with FOA [1], TRI [2] and VEC [3] networks is proposed. In the proposed approach firstly algorithms. Comparison will show that our algorithm each mobile sensor node determines its neighbors and its exhibit better performance. distance from borders and obstacles. According to these values, fuzzy inference engine calculates the priority of This paper is organized as follows: In section II, an node for movement. Then according to the priority, in overview on related approaches is presented. Section turn, nodes move away from each other to increase III consists of problem setup and an overview and coverage area in the target field. Simulation results show analysis of effective parameters on the position of that our fuzzy approach can reach higher degree of mobile sensors. How to fuzzy reasoning and proposed coverage against other common approaches like FOA, method have been describe in section IV and the results VEC and TRI algorithms. of performance evaluation of our method, FOA, VEC and TRI algorithms have been presented in section V. Index Terms— Mobile Sensor Network, Coverage, Fuzzy Finally the paper has been concluded in section VI. Priority, Movement II. RELATED APPROACHES I. INTRODUCTION Dealing with coverage problem, researchers have Advances in Micro Electro Mechanical Systems proposed numerous solutions. Some algorithms are (MEMS), embedded processors and wireless based on the notion of potential field [4], [5], [6] and communications have enabled the expansion of multi- virtual forces[7],[8] after an initial random deployment. functional, low-cost and tiny sensor nodes which can The next three distributed self deployment sense the environment, perform data processing and algorithms proposed in [3] known as the VEC, VOR, communicate with each other over short distances. and Minimax are based on the structure of Voronoi Wireless sensor networks (WSNs) are playing an diagram in which nodes are relocated to fill up increasingly significant role in a wide range of coverage holes. applications such as environmental conditions The vector-based algorithm, VEC, pushes nodes monitoring, wildlife monitoring, security surveillance away from densely covered areas to sparsely covered in military and battle-fields, nuclear, smart homes and areas. Two nodes exert a repulsive force when they are offices, improved medical treatment, industrial too close to each other. VOR is a greedy strategy that diagnosis, etc. The concept of area coverage can be pulls nodes towards the locations of their local considered as a measure of the quality of service (QoS) maximum coverage holes. The MiniMax algorithm is in a wireless sensor network. Random deployment of very similar to VOR; it moves a node inside its nodes often does not guarantee full coverage, resulting Voronoi polygon, such that, the distance from its in accumulation of nodes at certain parts of the sensing farthest Voronoi vertex is minimized. In [9] and [10], field while leaving other parts deprived of nodes. Some an incremental and greedy self-deployment algorithm is of the deployment strategies take advantage of mobility presented for mobile sensor networks in which nodes to relocate nodes to sparsely covered regions after an are deployed one at a time into an unknown initial random deployment to improve coverage. Thus environment. Each node makes use of the information as a solution, mobile sensor networks (MSNs) can be gathered by previously deployed nodes to determine its used for network coverage improvements. optimal deployment location. Conceptually, it is similar In this paper, a novel algorithm for placement of to the frontier-based approach [11]; however, in this mobile sensors is designed. The main result of this case, occupancy maps are built from live sensory data paper is as follows: and are analyzed to find frontiers between the free A Fuzzy logic method is described to find the space and the unknown space. movement priority for mobile sensors and a distributed The TRI algorithm is proposed in [2]. The basic idea fault tolerant, self deployment and iterative algorithm of TRI algorithm is to adjust the distance between two to cover an area. Mobile sensors only need to have knowledge of their location and with the assistance of Delaunay neighbors to . After several rounds local communication they will act in a completely of such adjustments, the layout of the network will be distributed fashion. To demonstrate the generality and 45 © 2010 ACEEE DOI: 01.ijns.01.02.09](https://image.slidesharecdn.com/09-120925225604-phpapp02/75/A-Fuzzy-Based-Priority-Approach-in-Mobile-Sensor-Network-Coverage-1-2048.jpg)
![ACEEE International Journal on Network Security, Vol 1, No. 2, July 2010 close to the ideal equilateral triangle layout. As a result, Sensor equipment: Each mobile sensor is equipped with the coverage area of the network will be maximized. a battery that provides sufficient power to move and The ATRI algorithm [2] is offered in order to reduce exchange information with other sensors. There is also the back-and-forth movement of nodes. a memory in each sensor which used to preserve The algorithms described in previous apply to require information of network elements. networks where all the nodes are capable of moving B. Effect of Adjacent Nodes around. However, there is a high cost associated to make each node mobile; a balance can be achieved by Cellular networks are a good example of an using a combination of static and mobile nodes, usually engineering task for supporting and presenting good referred to as hybrid sensor networks, while still quality of coverage in network. Due to easier ensuring sufficient coverage. In [12], such a protocol is calculations, in these networks, engineers have used described, called the bidding protocol, where the hexagonal shapes for each cell. It has been proven [2] problem is reduced to the well-known NP-hard set- that in ideal layout, the sensors are located in vertices covering problem.In [1] a Fuzzy Optimization of equilateral Delaunay triangles [16] with edge length Algorithm (FOA) is proposed to deploy sensors of . By this layout, the coverage area of efficiently. Authors use the number of neighbors and nodes will be maximized with the minimum coverage average Euclidean distance between sensors as inputs overlap. of the proposed Fuzzy reasoning engine algorithm and Using this value as a standard distance between get a distance measure as output. In proposed algorithm neighbor nodes, if the distance between two nodes each sensor calculates the forces imposed by the other becomes shorter than this distance, the virtual force sensors within its communication range. Then by between them will push them to move away from each applying Coulomb’s law and accumulating the vectors other. of all the forces, the sensor can calculate the magnitude C. Effect of Borders and Obstacles and the angle of its next movement vector in order to move toward the new next location. Coverage in the presence of obstacles is a challenging problem. In order to make the deployment III. PROBLEM SETUP AND EFFECTIVE COMPONENTS algorithm more practical, the sensors must be able to avoid obstacles and boundaries. Because an accurate Before describing proposed method, it is necessary map of the sensing area may not always be available to describe some related concepts and effective before the deployment, it is assumed that each sensor is components on the position of a mobile sensor in a equipped with an ultrasonic obstacle-detecting module, target field. In proposed method, effects of these which makes it possible to detect obstacles when it components have been collected. moves close enough to the obstacles. In order to avoid A. Preliminaries the coverage gap or overlap between nodes and boundaries, intuitively, the optimum distance between Two-dimensional deployment: It is assumed that all adjacent nodes and boundaries should be shorter than devices are located in two dimensions plan. . Location awareness: Knowing the location of sensor nodes is important for our algorithm. Many techniques have been proposed to supply this information for mobile sensors [13],[14]. Boundary and Obstacle detecting: It is assumed that each sensor node is equipped with an ultrasonic obstacle detecting module which makes it possible to detect boundaries when it moves close enough to it. Figure 1. The effect of adjacent nodes causes a distance Sensing model: Each sensor node in our algorithm is between them. associated with a sensing area which is represented by In Fig. 1, if the dashed line between two cells is a circle with the same Sensing Radius. This Circular considered as a boundary, the distance between the area is called Sensing Range and depends on several factors in the network [15]. A sensor node can detect node and the boundary should be set , but all the events in its Sensing Range. The areas which are using this approach will make some uncovered not covered by these circles are called coverage holes. triangular holes beside the boundary. In order to avoid Radio range: Apart from Sensing Range, each sensor the coverage gap, as shown in Fig. 2, the point P must has a Communication Range which is much longer than touch the boundary. By preliminary mathematics in Sensing Range. When a node broadcasts a message, all geometry, an effective distance between boundaries or the sensor nodes in its Communication obstacles and mobile sensor nodes can be calculated. Range will receive this message. As mentioned in section B, the distance of two adjacent mobile sensor nodes has to be adjusted to . Thus, the distance between a node and a boundary must 46 © 2010 ACEEE DOI: 01.ijns.01.02.09](https://image.slidesharecdn.com/09-120925225604-phpapp02/75/A-Fuzzy-Based-Priority-Approach-in-Mobile-Sensor-Network-Coverage-2-2048.jpg)
![ACEEE International Journal on Network Security, Vol 1, No. 2, July 2010 to be adjusted to instead of as the communication range of that node will get this shown in below calculation. message and will wait for a specific time (T wait) to receive all possible HELLO messages from the network. In this interval time, nodes will start to update -1 their Neighboring Matrix that is consists of gathered information from other mobile nodes around it. The mobile nodes which have some changes in their neighboring matrix will broadcast their information as a new HELLO message and will set a counter ( ). If within no P new HELLO message is received, the node starts to use Figure 2. The effect of a border or obstacle on a node causes a fuzzy controller to define its priority for movement. distance between them. The proposed fuzzy controller has two inputs: • Number of mobile nodes in the sensing range of D. Effect of Corners the node • Length of Sensing Shadow on boundaries or A corner is the junction of at least two different obstacles. boundaries. Thereby the proposed effective distance that has been calculated in section C, is not efficient Definition 1. In a two-dimensional mode, sensing here. For achieving a full coverage at corners, sensor shadow is the length of boundary which is inside the must become close enough to the furthest point at the sensing range of the sensor node. corner. Therefore mobile sensor node must stand at distance from the furthest point of corner. This value does not affected by different angels of corners. In the case of multiple corners, sensor will move toward the farthest vertex of corners and stop when the Distance from farthest corner vertex can be seen within the sensing border/obst acle radius of mobile node. Sensing Shadow Figure 4. A schematic of sensing shadow. Sensing shadow can be calculated in the same way of equation (1) and its value is between . If the distance between mobile node and boundary or obstacle is greater than or equal to , the sensing Figure 3. The effect of a corner on a node causes a distance shadow will be zero and if mobile node sticks to the from farthest vertex of corner. boundary or obstacle, the sensing shadow will be . This parameter is used to define the priority of IV. PROPOSED FUZZY BASED APPROACH standing in place for mobile sensor nodes. The nodes with minimum distance from borders or obstacles have Fuzzy reasoning tries to continue the way of natural highest priority for standing and should move after reasoning of human. It can present more smooth results their adjacent nodes. than common proposed methods in reasoning. How to The maximum number of hexagonal neighbor cells use fuzzy reasoning in a manner to make decision is six; therefore in the proposed algorithm it is assumed procedures for deployment of mobile sensor nodes in a that more than six neighbors is the worst case for initial target field is described in this section. deployment. So the number of neighbors is limited to A. Fuzzy Based Priority Coverage Algorithm (FBPC) ten as an upper bound for our controller so the controller will omit other extra neighbors Proposed method consists of two phases: First automatically. In order to normalizing the value of gathering information of neighbors and determining the sensing shadow into [0-1], it is divided by . priority of mobile sensor node to move and second The linguistic variables to represent the number of calculating movement vector. At the first phase, the mobile nodes in the sensing range of the node are nodes try to find other mobile sensor nodes within their divided into three levels: high, average and low; and communication range and also detect boundaries and those to represent the Length of Sensing Shadow are obstacles and the distance from them. also divided into three levels: high, average and low. After being activated, each node waits for a random The consequent is divided into five levels: very high, time and then broadcasts a HELLO message including its position in the target area. The sensors which are in 47 © 2010 ACEEE DOI: 01.ijns.01.02.09](https://image.slidesharecdn.com/09-120925225604-phpapp02/75/A-Fuzzy-Based-Priority-Approach-in-Mobile-Sensor-Network-Coverage-3-2048.jpg)
![ACEEE International Journal on Network Security, Vol 1, No. 2, July 2010 simulation round: total coverage, average moving TABLE 2. TYPES OF FORCES EACH NODE ENCOUNTERS distance and average number of rounds. Fig. 6 shows the total coverage of three algorithms as the number of sensors increases. Related Force Standard Distance Fij=Standard Distance between nodes -d(si,sj) FiB=Standard Distance from boundary -d(si,boundary) FiC=Standard Distance from corner- d(si,boundary) Figure 6. Total coverage A Robust Algorithm From the figure, it can be seen that the FBPC In some situations, a sensor may calculate a new algorithm prepares the best total coverage. The primary position; but when it wants to move, because of some reason is that unlike other algorithms, FBPC environmental conditions like holes, dead-end paths, paysattention to obstacles and boundaries and keeps etc; it could not reach destination target position. In distance from them in order not to waste its sensing such conditions FBPC algorithm is robust; because if range. one of the nodes cannot move to its final position, in Also, it can be seen that in sparse conditions, VEC the next round of algorithm, it can contribute in new algorithm stands in the second place, but in dense making decision routine according to the information conditions, VEC is replaced by FOA. of its new position, not previous announced Another dimension of evaluation is the average moving information. Therefore, FBPC is a fault tolerant distance. As depicted in Fig.7, TRI algorithm performs algorithm that can tolerate probable mistakes and can the worst in average moving distance a mong FBPC, correct its behavior in further rounds. Even if there are FOA, and VEC, Because in TRI mobile nodes are some errors in collecting local messages via network, located in a unique point in target field and after FBPC can recover its action in consequent rounds. calculating their accurate positions, they will move. Thus they must move more. V. PERFORMANCE EVALUATION After TRI, FBPC algorithm has the bigger average moving distance. This happens because it tries to do a A. Objectives and Metrics fast deployment and reach to a high level of coverage. Our deployment protocols have been implemented in Also in FBPC, nodes move away from borders and Matlab (version R2008a). Our objective in conducting obstacles. Results of VEC and FOA can be compared this evaluation study is: by comparing FOA, TRI, VEC with their coverage values. More coverage needs more and our algorithm giving some insight on choosing moving distance. suitable algorithm in different situations. The simulations are run under different sensor densities, which determines the sensor coverage that can be reached and the difficulty to reach it. In a 100 m ×100 m target field, five different numbers of sensors have been distributed, ranging from 60 to 140 in increment of 20 sensors. The initial deployment of proposed algorithm, FOA and also VEC algorithm follow the random distribution, however in TRI, Figure 7. Average moving distance according to [2], at the beginning of the experiment, sensors are randomly placed within a 1m × 1m The number of rounds in FOA algorithm is high. compact square, which is centered at point (50m, 50m). Although some of the authors disregard the effect of Then the nodes explode to a large evenly deployed message complexity in increasing energy consumption, layout. To evaluate each metric under different this cannot be ignored by increase in number of rounds. parameter setting, 5 experiments based on different Calculated from Robomote [17],[3], approximately, to initial distribution are run and the average results are move a sensor one meter consumes a similar amount of beening calculated. The Sensing Range is set to be 6 energy as transmitting 300 messages . Assume that in meters and 20 meters as the Communication Range. each round each sensor transmits one packet for a network with 100 sensors, by running the FOA B. Simulation Results algorithm after each 3 rounds and 30 rounds, the In order to evaluate the performance and cost of the movement distance of nodes will be increased 1m and three algorithms, three metrics are measured for each 49 © 2010 ACEEE DOI: 01.ijns.01.02.09](https://image.slidesharecdn.com/09-120925225604-phpapp02/75/A-Fuzzy-Based-Priority-Approach-in-Mobile-Sensor-Network-Coverage-5-2048.jpg)
![ACEEE International Journal on Network Security, Vol 1, No. 2, July 2010 10m, respectively. Moreover it is assumed that all Communications and Networking Conference, Vol. packets can be transmitted without any error. 3, pp.1903 – 1908, 13-17 March 2005. Random distribution of sensors occurs in urgent [2] Ma, M. and Yang, Y., “Adaptive Triangular Deployment cases or for some special application. In such an urgent Algorithm for Unattended Mobile Sensor Networks”, IEEE Transactions on Computers, Vol. 56, NO. 7, pp. situation, the fast deployment of the sensors is in the 946 – 847, JULY 2007. first priority. In this case the performance of the FOA [3] Wang, G., Cao, G. and La Porta, T. ,“Movement- algorithm is not applicable at all, whereas FBPC Assisted Sensor Deployment”, IEEE Transaction on algorithm presents better coverage with fast reaction. Mobile Computing, Vol.5, no.6, pp. 640–652, June 2006. Fig. 8 shows the result of average number of rounds [4] O. Khatib, “Real-time obstacle avoidance for in algorithms. manipulators and mobile robots”, International Journal of Robotics Research, pp. 90–98, 1986. [5] A. Howard, M. Mataric and G. Sukhatme, “Mobile sensor network deployment using potential fields: A distributed scalable solution to the area coverage problem”, Proceedings of the 6th International Symposium on Distributed Autonomous Robotic Systems, Fukuoka, Japan, pp. 299–308,June 2002. [6] S. Poduri, G.S. Sukhatme, “Constrained coverage in mobile sensor networks”, Proceedings of IEEE International Conference on Robotics and Automation, Figure 8. Average number of rounds New Orleans, LA, pp. 40–50, April–May 2004. [7] Y. Zou, K. Chakrabarty, “Sensor deployment and target As it can be seen, FBPC and VEC achieve quite localization in distributed sensor networks”, Transactions on IEEE Embedded Computing Systems, similar number of rounds and they can deploy very pp. 61–91, 2004. fast. As this figure shows, FOA algorithm has the worst [8] Y. Zou, K. Chakrabarty, “Sensor deployment and target performance. localization based on virtual forces”, Proceedings of Selecting the random intervals for waiting in FBPC IEEE Infocom, INFOCOM’03, San Francisco, CA, pp. algorithm in order to decrease the number of collision 1293–1303, April 2003. during the packet transformation, not only decreases [9] A. Howard, M. Mataric, “Cover me! a self-deployment the effect of not arriving a packet to the destination but algorithm for mobile sensor networks”, Proceedings of also the next following packets can cover the effect of IEEE International Conference on Robotics and this error. While other existence algorithms act poorly Automation, ICRA’02, Washington, DC, pp. 80–91, May 2002. and don’t pay much attention in sending the messages [10] A. Howard, M. Mataric, G. Sukhatme, “An incremental and exchanging information. self-deployment algorithm for mobile sensor networks”, Autonomous Robots Special Issue on Intelligent VI. CONCLUSION AND FEATURE WORKS Embedded Systems, pp.113–126, 2002. [11] B. Yamauchi, “A frontier-based approach for In this paper, a new fault tolerant deployment fuzzy autonomous exploration”, IEEE International based algorithm is proposed for unattended mobile Symposium on Computational Intelligence in Robotics sensor networks, called, the Fuzzy Based Priority and Automation, CIRA’97, Montere, CA, , pp. 146–156, Coverage (FBPC) algorithm. Algorithm is run in a June 1997. completely distributed fashion by each node based only [12] G. Wang, G. Cao, T. LaPorta, “A bidding protocol for on local communications. Proposed method uses deploying mobile sensors”, Proceedings of the 11th number of neighbors and distance from borders and IEEE International Conference on Network Protocols, obstacles as inputs of a fuzzy inference engine. The ICNP’03, Atlanta, GA, pp. 80–91, November 2003. [13] Datta, S., Klinowski, C., Rudafshani, M., Khaleque, S., output is the actual priority of movement for sensor “Distributed localization in static and mobile sensor node. Nodes move away according to their priorities. networks”, IEEE International Conference on Wireless Simulation results show that proposed method received and Mobile Computing, Networking and a very good coverage comparing other common Communications, p.p. 69 – 76, 19-21 June 2006. approaches, especially in the sparse networks. [14] Li, X. and Santoro, N., “A ZONE-based Sensor For future works, we consider to improve the ability Relocation Protocol for Mobile Sensor Networks”, of our algorithm in sparse networks. Improving Proceedings of 31st IEEE Conference on Local network coverage in sparse conditions will result in Computer Networks, p.p. 923 – 930, Nov. 2006. reducing overall cost of network. [15] Zhao, F. and Guibas, L., “Wireless sensor networks: an information processing approach”, Boston: Elsevier- Morgan Kaufmann, 2004. REFERENCES [16] Kwok, A. and Martinez, S., “Deployment algorithms for [1] Hainin Shu, Qilian Liang, “Fuzzy optimization for a power-constrained mobile sensor network”, IEEE distributed sensor deployment”, IEEE Wireless International Conference on Robotics and Automation, ICRA, p.p. 140 – 145, 19-23 May 2008. 50 © 2010 ACEEE DOI: 01.ijns.01.02.09](https://image.slidesharecdn.com/09-120925225604-phpapp02/75/A-Fuzzy-Based-Priority-Approach-in-Mobile-Sensor-Network-Coverage-6-2048.jpg)
A Fuzzy Based Priority Approach in Mobile Sensor Network Coverage
- 1. ACEEE International Journalon Network Security, Vol 1, No. 2, July 2010 A Fuzzy Based Priority Approach in Mobile Sensor Network Coverage Bahareh J. Farahani, Hossein Ghaffarian ,Mahmood Fathy Computer Engineering School, Iran University of Science and Technology, Tehran, Iran Farahani.ict@gmail.com, Ghaffarian@iust.ac.ir, MahFathy@iust.ac.ir Abstract— In this paper a new fuzzy based approach for effectiveness of this algorithm, our algorithm is improving network coverage in wireless mobile sensor compared with FOA [1], TRI [2] and VEC [3] networks is proposed. In the proposed approach firstly algorithms. Comparison will show that our algorithm each mobile sensor node determines its neighbors and its exhibit better performance. distance from borders and obstacles. According to these values, fuzzy inference engine calculates the priority of This paper is organized as follows: In section II, an node for movement. Then according to the priority, in overview on related approaches is presented. Section turn, nodes move away from each other to increase III consists of problem setup and an overview and coverage area in the target field. Simulation results show analysis of effective parameters on the position of that our fuzzy approach can reach higher degree of mobile sensors. How to fuzzy reasoning and proposed coverage against other common approaches like FOA, method have been describe in section IV and the results VEC and TRI algorithms. of performance evaluation of our method, FOA, VEC and TRI algorithms have been presented in section V. Index Terms— Mobile Sensor Network, Coverage, Fuzzy Finally the paper has been concluded in section VI. Priority, Movement II. RELATED APPROACHES I. INTRODUCTION Dealing with coverage problem, researchers have Advances in Micro Electro Mechanical Systems proposed numerous solutions. Some algorithms are (MEMS), embedded processors and wireless based on the notion of potential field [4], [5], [6] and communications have enabled the expansion of multi- virtual forces[7],[8] after an initial random deployment. functional, low-cost and tiny sensor nodes which can The next three distributed self deployment sense the environment, perform data processing and algorithms proposed in [3] known as the VEC, VOR, communicate with each other over short distances. and Minimax are based on the structure of Voronoi Wireless sensor networks (WSNs) are playing an diagram in which nodes are relocated to fill up increasingly significant role in a wide range of coverage holes. applications such as environmental conditions The vector-based algorithm, VEC, pushes nodes monitoring, wildlife monitoring, security surveillance away from densely covered areas to sparsely covered in military and battle-fields, nuclear, smart homes and areas. Two nodes exert a repulsive force when they are offices, improved medical treatment, industrial too close to each other. VOR is a greedy strategy that diagnosis, etc. The concept of area coverage can be pulls nodes towards the locations of their local considered as a measure of the quality of service (QoS) maximum coverage holes. The MiniMax algorithm is in a wireless sensor network. Random deployment of very similar to VOR; it moves a node inside its nodes often does not guarantee full coverage, resulting Voronoi polygon, such that, the distance from its in accumulation of nodes at certain parts of the sensing farthest Voronoi vertex is minimized. In [9] and [10], field while leaving other parts deprived of nodes. Some an incremental and greedy self-deployment algorithm is of the deployment strategies take advantage of mobility presented for mobile sensor networks in which nodes to relocate nodes to sparsely covered regions after an are deployed one at a time into an unknown initial random deployment to improve coverage. Thus environment. Each node makes use of the information as a solution, mobile sensor networks (MSNs) can be gathered by previously deployed nodes to determine its used for network coverage improvements. optimal deployment location. Conceptually, it is similar In this paper, a novel algorithm for placement of to the frontier-based approach [11]; however, in this mobile sensors is designed. The main result of this case, occupancy maps are built from live sensory data paper is as follows: and are analyzed to find frontiers between the free A Fuzzy logic method is described to find the space and the unknown space. movement priority for mobile sensors and a distributed The TRI algorithm is proposed in [2]. The basic idea fault tolerant, self deployment and iterative algorithm of TRI algorithm is to adjust the distance between two to cover an area. Mobile sensors only need to have knowledge of their location and with the assistance of Delaunay neighbors to . After several rounds local communication they will act in a completely of such adjustments, the layout of the network will be distributed fashion. To demonstrate the generality and 45 © 2010 ACEEE DOI: 01.ijns.01.02.09
- 2. ACEEE International Journalon Network Security, Vol 1, No. 2, July 2010 close to the ideal equilateral triangle layout. As a result, Sensor equipment: Each mobile sensor is equipped with the coverage area of the network will be maximized. a battery that provides sufficient power to move and The ATRI algorithm [2] is offered in order to reduce exchange information with other sensors. There is also the back-and-forth movement of nodes. a memory in each sensor which used to preserve The algorithms described in previous apply to require information of network elements. networks where all the nodes are capable of moving B. Effect of Adjacent Nodes around. However, there is a high cost associated to make each node mobile; a balance can be achieved by Cellular networks are a good example of an using a combination of static and mobile nodes, usually engineering task for supporting and presenting good referred to as hybrid sensor networks, while still quality of coverage in network. Due to easier ensuring sufficient coverage. In [12], such a protocol is calculations, in these networks, engineers have used described, called the bidding protocol, where the hexagonal shapes for each cell. It has been proven [2] problem is reduced to the well-known NP-hard set- that in ideal layout, the sensors are located in vertices covering problem.In [1] a Fuzzy Optimization of equilateral Delaunay triangles [16] with edge length Algorithm (FOA) is proposed to deploy sensors of . By this layout, the coverage area of efficiently. Authors use the number of neighbors and nodes will be maximized with the minimum coverage average Euclidean distance between sensors as inputs overlap. of the proposed Fuzzy reasoning engine algorithm and Using this value as a standard distance between get a distance measure as output. In proposed algorithm neighbor nodes, if the distance between two nodes each sensor calculates the forces imposed by the other becomes shorter than this distance, the virtual force sensors within its communication range. Then by between them will push them to move away from each applying Coulomb’s law and accumulating the vectors other. of all the forces, the sensor can calculate the magnitude C. Effect of Borders and Obstacles and the angle of its next movement vector in order to move toward the new next location. Coverage in the presence of obstacles is a challenging problem. In order to make the deployment III. PROBLEM SETUP AND EFFECTIVE COMPONENTS algorithm more practical, the sensors must be able to avoid obstacles and boundaries. Because an accurate Before describing proposed method, it is necessary map of the sensing area may not always be available to describe some related concepts and effective before the deployment, it is assumed that each sensor is components on the position of a mobile sensor in a equipped with an ultrasonic obstacle-detecting module, target field. In proposed method, effects of these which makes it possible to detect obstacles when it components have been collected. moves close enough to the obstacles. In order to avoid A. Preliminaries the coverage gap or overlap between nodes and boundaries, intuitively, the optimum distance between Two-dimensional deployment: It is assumed that all adjacent nodes and boundaries should be shorter than devices are located in two dimensions plan. . Location awareness: Knowing the location of sensor nodes is important for our algorithm. Many techniques have been proposed to supply this information for mobile sensors [13],[14]. Boundary and Obstacle detecting: It is assumed that each sensor node is equipped with an ultrasonic obstacle detecting module which makes it possible to detect boundaries when it moves close enough to it. Figure 1. The effect of adjacent nodes causes a distance Sensing model: Each sensor node in our algorithm is between them. associated with a sensing area which is represented by In Fig. 1, if the dashed line between two cells is a circle with the same Sensing Radius. This Circular considered as a boundary, the distance between the area is called Sensing Range and depends on several factors in the network [15]. A sensor node can detect node and the boundary should be set , but all the events in its Sensing Range. The areas which are using this approach will make some uncovered not covered by these circles are called coverage holes. triangular holes beside the boundary. In order to avoid Radio range: Apart from Sensing Range, each sensor the coverage gap, as shown in Fig. 2, the point P must has a Communication Range which is much longer than touch the boundary. By preliminary mathematics in Sensing Range. When a node broadcasts a message, all geometry, an effective distance between boundaries or the sensor nodes in its Communication obstacles and mobile sensor nodes can be calculated. Range will receive this message. As mentioned in section B, the distance of two adjacent mobile sensor nodes has to be adjusted to . Thus, the distance between a node and a boundary must 46 © 2010 ACEEE DOI: 01.ijns.01.02.09
- 3. ACEEE International Journalon Network Security, Vol 1, No. 2, July 2010 to be adjusted to instead of as the communication range of that node will get this shown in below calculation. message and will wait for a specific time (T wait) to receive all possible HELLO messages from the network. In this interval time, nodes will start to update -1 their Neighboring Matrix that is consists of gathered information from other mobile nodes around it. The mobile nodes which have some changes in their neighboring matrix will broadcast their information as a new HELLO message and will set a counter ( ). If within no P new HELLO message is received, the node starts to use Figure 2. The effect of a border or obstacle on a node causes a fuzzy controller to define its priority for movement. distance between them. The proposed fuzzy controller has two inputs: • Number of mobile nodes in the sensing range of D. Effect of Corners the node • Length of Sensing Shadow on boundaries or A corner is the junction of at least two different obstacles. boundaries. Thereby the proposed effective distance that has been calculated in section C, is not efficient Definition 1. In a two-dimensional mode, sensing here. For achieving a full coverage at corners, sensor shadow is the length of boundary which is inside the must become close enough to the furthest point at the sensing range of the sensor node. corner. Therefore mobile sensor node must stand at distance from the furthest point of corner. This value does not affected by different angels of corners. In the case of multiple corners, sensor will move toward the farthest vertex of corners and stop when the Distance from farthest corner vertex can be seen within the sensing border/obst acle radius of mobile node. Sensing Shadow Figure 4. A schematic of sensing shadow. Sensing shadow can be calculated in the same way of equation (1) and its value is between . If the distance between mobile node and boundary or obstacle is greater than or equal to , the sensing Figure 3. The effect of a corner on a node causes a distance shadow will be zero and if mobile node sticks to the from farthest vertex of corner. boundary or obstacle, the sensing shadow will be . This parameter is used to define the priority of IV. PROPOSED FUZZY BASED APPROACH standing in place for mobile sensor nodes. The nodes with minimum distance from borders or obstacles have Fuzzy reasoning tries to continue the way of natural highest priority for standing and should move after reasoning of human. It can present more smooth results their adjacent nodes. than common proposed methods in reasoning. How to The maximum number of hexagonal neighbor cells use fuzzy reasoning in a manner to make decision is six; therefore in the proposed algorithm it is assumed procedures for deployment of mobile sensor nodes in a that more than six neighbors is the worst case for initial target field is described in this section. deployment. So the number of neighbors is limited to A. Fuzzy Based Priority Coverage Algorithm (FBPC) ten as an upper bound for our controller so the controller will omit other extra neighbors Proposed method consists of two phases: First automatically. In order to normalizing the value of gathering information of neighbors and determining the sensing shadow into [0-1], it is divided by . priority of mobile sensor node to move and second The linguistic variables to represent the number of calculating movement vector. At the first phase, the mobile nodes in the sensing range of the node are nodes try to find other mobile sensor nodes within their divided into three levels: high, average and low; and communication range and also detect boundaries and those to represent the Length of Sensing Shadow are obstacles and the distance from them. also divided into three levels: high, average and low. After being activated, each node waits for a random The consequent is divided into five levels: very high, time and then broadcasts a HELLO message including its position in the target area. The sensors which are in 47 © 2010 ACEEE DOI: 01.ijns.01.02.09
- 4. ACEEE International Journalon Network Security, Vol 1, No. 2, July 2010 high, average, very low and low. Table 1 summaries the of its neighbor nodes, boundaries, obstacles and rules and consequents. corners. In our model, each node s i is subjected to three One example of rules is as follows: kinds of forces: (1) an attractive or repulsive force F i j , IF the number of mobile nodes in the sensing range by another node sj depending on its distance and of sensor i is high and length of Sensing Shadow of orientation from si, (2) a repulsive force F i B, exerted by sensor i on boundaries or obstacles is low, THEN the obstacles or boundaries, and (3) a repulsive force F i C, standing priority result of sensor i will be very high. exerted by corners. The net force on a sensor s i is the vector sum of all the above forces. Table 2 summaries TABLE 1. these three types of forces. RULE BASE OF THE PROPOSED FUZZY STANDING PRIORITY After calculating movement vector and defining CONTROLLER destination, the node will send a GOODBYE packet that consists of the new calculated position of mobile Priority Neighbor Number node. Then lowest priority mobile node runs into the Controller Rules Low Average High new position. Other nodes will update their neighboring matrix information after receiving GOODBYE packet Very and use this updated version in their calculation to find Low High Very High Sensi High their final position. ng Averag Shad e Low Average High After moving all nodes, this algorithm will be ow Very repeated again until nodes have not any changes in High Low High Low their positions. Algorithm 1 shows a pseudo code of the proposed Fuzzy Based Priority Coverage (FBPC) Fig. 5 shows input and output membership functions algorithm. of our proposed fuzzy controller. The nodes with 1: FBPC () lowest standing priority must move first in a group of 2: { adjacent mobile sensor networks. 3: while () 4: { 5: Stand for a random time t 6: Broadcast a HELLO packet 7: Stand for T wait to receive all possible HELLO 8: packets 9: Update Neighboring matrix 10: If there are some changes in Neighboring matrix 11: { a. Neighbor Number membership function 12: Broadcast a HELLO packet. 13: Stand for Tthreshold 14: If within T threshold some new HELLO message 15: is received 16: go to line 8 17: } 18: If there are not any changes in the position of 19: node and its adjacent nodes 20: break; b. Sensing shadow membership function 21: Calculate Sensing Shadow 22: Determine movement turning according to the 23: standing priority of node using Fuzzy priority 24: controller 25: Stand until receiving movement turning of the 26: nodes and update the Neighboring matrix 27: according to the 28: information of the receiving GOODBYE packets c. Priority membership function 29: Calculate MOVEMENT VECTOR according to 30: the Neighboring matrix Figure 5. Membership functions of the proposed Fuzzy Priority 31: Broadcast GOODBYE packet and travel to the controller. 32: new position in target field } } At this stage, there is no need for nodes to rebroadcast information of their priorities, because each mobile sensor can easily calculate the priority of its neighbors. At the second phase, each node with minimum standing priority can move before other nodes. So sensor will calculate its MOVEMENT VECTOR based on forces 48 © 2010 ACEEE DOI: 01.ijns.01.02.09
- 5. ACEEE International Journalon Network Security, Vol 1, No. 2, July 2010 simulation round: total coverage, average moving TABLE 2. TYPES OF FORCES EACH NODE ENCOUNTERS distance and average number of rounds. Fig. 6 shows the total coverage of three algorithms as the number of sensors increases. Related Force Standard Distance Fij=Standard Distance between nodes -d(si,sj) FiB=Standard Distance from boundary -d(si,boundary) FiC=Standard Distance from corner- d(si,boundary) Figure 6. Total coverage A Robust Algorithm From the figure, it can be seen that the FBPC In some situations, a sensor may calculate a new algorithm prepares the best total coverage. The primary position; but when it wants to move, because of some reason is that unlike other algorithms, FBPC environmental conditions like holes, dead-end paths, paysattention to obstacles and boundaries and keeps etc; it could not reach destination target position. In distance from them in order not to waste its sensing such conditions FBPC algorithm is robust; because if range. one of the nodes cannot move to its final position, in Also, it can be seen that in sparse conditions, VEC the next round of algorithm, it can contribute in new algorithm stands in the second place, but in dense making decision routine according to the information conditions, VEC is replaced by FOA. of its new position, not previous announced Another dimension of evaluation is the average moving information. Therefore, FBPC is a fault tolerant distance. As depicted in Fig.7, TRI algorithm performs algorithm that can tolerate probable mistakes and can the worst in average moving distance a mong FBPC, correct its behavior in further rounds. Even if there are FOA, and VEC, Because in TRI mobile nodes are some errors in collecting local messages via network, located in a unique point in target field and after FBPC can recover its action in consequent rounds. calculating their accurate positions, they will move. Thus they must move more. V. PERFORMANCE EVALUATION After TRI, FBPC algorithm has the bigger average moving distance. This happens because it tries to do a A. Objectives and Metrics fast deployment and reach to a high level of coverage. Our deployment protocols have been implemented in Also in FBPC, nodes move away from borders and Matlab (version R2008a). Our objective in conducting obstacles. Results of VEC and FOA can be compared this evaluation study is: by comparing FOA, TRI, VEC with their coverage values. More coverage needs more and our algorithm giving some insight on choosing moving distance. suitable algorithm in different situations. The simulations are run under different sensor densities, which determines the sensor coverage that can be reached and the difficulty to reach it. In a 100 m ×100 m target field, five different numbers of sensors have been distributed, ranging from 60 to 140 in increment of 20 sensors. The initial deployment of proposed algorithm, FOA and also VEC algorithm follow the random distribution, however in TRI, Figure 7. Average moving distance according to [2], at the beginning of the experiment, sensors are randomly placed within a 1m × 1m The number of rounds in FOA algorithm is high. compact square, which is centered at point (50m, 50m). Although some of the authors disregard the effect of Then the nodes explode to a large evenly deployed message complexity in increasing energy consumption, layout. To evaluate each metric under different this cannot be ignored by increase in number of rounds. parameter setting, 5 experiments based on different Calculated from Robomote [17],[3], approximately, to initial distribution are run and the average results are move a sensor one meter consumes a similar amount of beening calculated. The Sensing Range is set to be 6 energy as transmitting 300 messages . Assume that in meters and 20 meters as the Communication Range. each round each sensor transmits one packet for a network with 100 sensors, by running the FOA B. Simulation Results algorithm after each 3 rounds and 30 rounds, the In order to evaluate the performance and cost of the movement distance of nodes will be increased 1m and three algorithms, three metrics are measured for each 49 © 2010 ACEEE DOI: 01.ijns.01.02.09
- 6. ACEEE International Journalon Network Security, Vol 1, No. 2, July 2010 10m, respectively. Moreover it is assumed that all Communications and Networking Conference, Vol. packets can be transmitted without any error. 3, pp.1903 – 1908, 13-17 March 2005. Random distribution of sensors occurs in urgent [2] Ma, M. and Yang, Y., “Adaptive Triangular Deployment cases or for some special application. In such an urgent Algorithm for Unattended Mobile Sensor Networks”, IEEE Transactions on Computers, Vol. 56, NO. 7, pp. situation, the fast deployment of the sensors is in the 946 – 847, JULY 2007. first priority. In this case the performance of the FOA [3] Wang, G., Cao, G. and La Porta, T. ,“Movement- algorithm is not applicable at all, whereas FBPC Assisted Sensor Deployment”, IEEE Transaction on algorithm presents better coverage with fast reaction. Mobile Computing, Vol.5, no.6, pp. 640–652, June 2006. Fig. 8 shows the result of average number of rounds [4] O. Khatib, “Real-time obstacle avoidance for in algorithms. manipulators and mobile robots”, International Journal of Robotics Research, pp. 90–98, 1986. [5] A. Howard, M. Mataric and G. Sukhatme, “Mobile sensor network deployment using potential fields: A distributed scalable solution to the area coverage problem”, Proceedings of the 6th International Symposium on Distributed Autonomous Robotic Systems, Fukuoka, Japan, pp. 299–308,June 2002. [6] S. Poduri, G.S. Sukhatme, “Constrained coverage in mobile sensor networks”, Proceedings of IEEE International Conference on Robotics and Automation, Figure 8. Average number of rounds New Orleans, LA, pp. 40–50, April–May 2004. [7] Y. Zou, K. Chakrabarty, “Sensor deployment and target As it can be seen, FBPC and VEC achieve quite localization in distributed sensor networks”, Transactions on IEEE Embedded Computing Systems, similar number of rounds and they can deploy very pp. 61–91, 2004. fast. As this figure shows, FOA algorithm has the worst [8] Y. Zou, K. Chakrabarty, “Sensor deployment and target performance. localization based on virtual forces”, Proceedings of Selecting the random intervals for waiting in FBPC IEEE Infocom, INFOCOM’03, San Francisco, CA, pp. algorithm in order to decrease the number of collision 1293–1303, April 2003. during the packet transformation, not only decreases [9] A. Howard, M. Mataric, “Cover me! a self-deployment the effect of not arriving a packet to the destination but algorithm for mobile sensor networks”, Proceedings of also the next following packets can cover the effect of IEEE International Conference on Robotics and this error. While other existence algorithms act poorly Automation, ICRA’02, Washington, DC, pp. 80–91, May 2002. and don’t pay much attention in sending the messages [10] A. Howard, M. Mataric, G. Sukhatme, “An incremental and exchanging information. self-deployment algorithm for mobile sensor networks”, Autonomous Robots Special Issue on Intelligent VI. CONCLUSION AND FEATURE WORKS Embedded Systems, pp.113–126, 2002. [11] B. Yamauchi, “A frontier-based approach for In this paper, a new fault tolerant deployment fuzzy autonomous exploration”, IEEE International based algorithm is proposed for unattended mobile Symposium on Computational Intelligence in Robotics sensor networks, called, the Fuzzy Based Priority and Automation, CIRA’97, Montere, CA, , pp. 146–156, Coverage (FBPC) algorithm. Algorithm is run in a June 1997. completely distributed fashion by each node based only [12] G. Wang, G. Cao, T. LaPorta, “A bidding protocol for on local communications. Proposed method uses deploying mobile sensors”, Proceedings of the 11th number of neighbors and distance from borders and IEEE International Conference on Network Protocols, obstacles as inputs of a fuzzy inference engine. The ICNP’03, Atlanta, GA, pp. 80–91, November 2003. [13] Datta, S., Klinowski, C., Rudafshani, M., Khaleque, S., output is the actual priority of movement for sensor “Distributed localization in static and mobile sensor node. Nodes move away according to their priorities. networks”, IEEE International Conference on Wireless Simulation results show that proposed method received and Mobile Computing, Networking and a very good coverage comparing other common Communications, p.p. 69 – 76, 19-21 June 2006. approaches, especially in the sparse networks. [14] Li, X. and Santoro, N., “A ZONE-based Sensor For future works, we consider to improve the ability Relocation Protocol for Mobile Sensor Networks”, of our algorithm in sparse networks. Improving Proceedings of 31st IEEE Conference on Local network coverage in sparse conditions will result in Computer Networks, p.p. 923 – 930, Nov. 2006. reducing overall cost of network. [15] Zhao, F. and Guibas, L., “Wireless sensor networks: an information processing approach”, Boston: Elsevier- Morgan Kaufmann, 2004. REFERENCES [16] Kwok, A. and Martinez, S., “Deployment algorithms for [1] Hainin Shu, Qilian Liang, “Fuzzy optimization for a power-constrained mobile sensor network”, IEEE distributed sensor deployment”, IEEE Wireless International Conference on Robotics and Automation, ICRA, p.p. 140 – 145, 19-23 May 2008. 50 © 2010 ACEEE DOI: 01.ijns.01.02.09