# Introduction he wireless sensor network (WSN) has emerged as a promising tool for monitoring the physical world. This kind of networks consists of sensors that can sense, process and communicate. Sensors can be deployed rapidly and cheaply, and thereby, enable large-scale and on-demands monitoring and tracking, over a wide range of applications, such as danger alerting, vehicle tracking, battlefield surveillance, habitat monitoring, etc [2]. Due to their portability and deployment, the sensor nodes are usually powered by batteries with limited capacities. And although the energy of sensor networks is slight, recharging their power sources is difficult or even impossible, usually. Thus, one of challenges in designing the sensor networks includes saving the limited energy resources to prolong the lifetime of WSN [3]. On the other hand, one of major problems in the sensor networks field is the coverage problem. This problem deals with the network ability to cover a certain area or some certain events. Various coverage formulations have been proposed in literature, among which the following three are most discussed [1]: ? Area coverage ? Point coverage ? Barrier coverage Monitoring the whole area of the network is the main objective of area coverage problem. The objective of point coverage problem includes covering a set of stationary or mobile points, using as little sensor nodes as possible. Also, what can be considered in Barrier coverage problem is minimizing the probability of inability for intrusion detection, through a barrier sensor network [1]. For solving each problem, some algorithms have been presented. But this paper has focused on barrier coverage problem. The algorithms presented to solving this problem can be categorized into local barrier coverage algorithms and centralized ones [10]. In the first one, each node makes attempt to participate in barrier coverage, locally. This local coverage is able to provide an appropriate k-barrier coverage, in most times. a centralized barrier coverage it is run on one or more nodes in a centralized location usually near the data sink The major problem with their approach is that it is completely centralized, all sensor nodes must be able to communicate directly with the base station. This limits the scope of the network severely [17]. In another view point, the algorithms can be classified into weak barrier coverage and strong barrier coverage. The first assumes that the intruder does not know the traverse path and it will be detected with high probability, by the network. Strong barrier coverage guarantees to detect intruders no matter what crossing paths [17]. In [9], the concept of Accumulation Point Model (APM) and also a local algorithm for k-barrier coverage have been presented. In this paper, we use this concept differently, to provide a fault tolerant protocol. In the other word, a k-barrier coverage protocol, here called APBC, will be proposed. In order to prolong the lifetime of the network, the proposed protocol maintains a good balance in using nodes energies. It presents a proper way to provide the k-barrier coverage at nodes fail times, without re-executing the algorithm. Totally, a new method will be presented that try to guarantee the providing a k-barrier coverage, while decreasing the energy consumption. For the purpose of this paper, it has been organized as follows: In Section II, we present some definitions, background, and related works. In Section III, we will present our Network Model and Section IV, has been dedicated to describing our Proposed Protocol. In Section V, we present the results of our simulations and finally, we will conclude the paper in Section VI. here. # II. # Preliminary and network model Your Some of local barrier coverage algorithms have been introduced in [5,6,9,10,13]. And [1,4,11] have introduced the centralized algorithms. One of algorithms for local barrier coverage, called RIS, has been presented in [13]. This algorithm is based on a power saving method, in which the sensor nodes are scheduled and switch between two modes, Active and Sleep. RIS provides a weak barrier coverage with the high probability of intrusion detection, in such a way that each sensor, in certain periods, selects Active or Sleep mode, with a predetermined probability rate, P. As mentioned earlier, the presented method will be based on the power saving method, used by RIS. However, the modes considered in sensor nodes have been changed to Active and Passive modes. It must be noticed that RIS does not guarantee the barrier coverage, deterministically. Also, if the deployment does not follow random uniform or Poisson distribution, and the lifetimes of the sensor nodes are not the same, there is no guidance on how to choose a value for P. Furthermore, a directed algorithm, called CoBRA has been introduced in [5] to provide the barrier coverage in wireless Camera Sensor Networks (WCSN).And the algorithm presented in [6] coordinates the nodes moves in mobile sensor networks, to provide the barrier coverage. A proper way has been introduced in [7,8] to providing a 3-dimentional barrier coverage, for under water 3-dimentional sensors. But the network model used in [9] has been considered in this paper. In this model, a barrier area is considered to be covered which is a physical long strip region in optional shape (see Fig. 1). In such a model, it is assumed that each node knows its own location in the network and has a disk-like sensing region, with radius R. Although radio radiuses of nodes are not same and are integrated in real world, it is possible to ignore the differences in sensing radiuses, while evaluating the coverage in wireless sensor networks, in large scale. The relationship between sensing radius of each node, RS, and its transition radius, R t , can be described with R t 2R S [16]. As a result, when two nodes can communicate with each other, also their sensing areas overlap, certainly. So these two nodes will be able to provide the strong coverage by keeping themselves active. Thus the coverage can imply the connectivity (see Fig. 2). So we will focus on the coverage problem, only. Figure 2: The transmission radius of sensor nodes is assumed to be at least twice the sensing range On the other hand, according to different energy consumption models, the energy consumed by an sensor node, while dealing with a sensing task, is proportional to RS2 or RS4, where RS is the sensing radius of the sensor node [3] [17]. When the sensor node is sleeping, the consumed power is considered as zero [3]. In this paper, we take the sensing energy consumption as u.RS2, where u is a positive constant. For analyzing the energy consumption, briefly, only the energy consumed by the sensing and transition functions (excluding the power consumption by calculations) has been considered here. Three consumption models, including APM, IBM and RPM have been introduced in [9] for nodes deployment (see Fig. 3). Sensor Networks Some of definitions required to explaining the presented method are as following: Coverage Graph: The coverage graph of a sensor network is denoted by G= (V, E), in which each node is supposed to be associated with a vertex in vertices set (V). Each two nodes located in transition areas of each other, are considered as Neighbors, and an edge in edges set (E) is assumed between their associated vertices. In Fig. 4 and Fig. 5, a sensor network and its coverage graph have been shown. The relationship between the vertices and the edges can be described by Eq. ( 1). (1) Figure 4: A Sensor network Accumulation Point: An accumulation point is a sub-graph, Ga= (Va, Ea ), of a sensor network barrier graph G= (V, E), given the following (Fig. 6). # The proposed protocol As mentioned earlier, the main problem to be solved includes providing a k-barrier graph which creates and describes a k-barrier coverage in a barrier area. As a result, all paths crossing through the barrier area are covered k-times, by the network sensors. The proposed method consists of three phases named startup phase, k-coverage creation phase and maintenance & recovery phase. each node introduces itself to its neighbors. After receiving this message, each node knows its neighbors and then by sending a special package (my-neighbors) presents its neighbors list to its all neighbors. So, after receiving the neighbors list from all neighbors, each node can find out whether it is a member of one or several accumulation points, G= (Va , Ea ). # b) K-coverage Creation Phase In this phase, a K-barrier graph, Gb=(Vb ,Eb ) is created. So, k barrier belts, G = (V , E ), should be created. For this purpose, one of the leftmost nodes that is the neighbor of virtual node, s, in the sensor network coverage graph, G= (V, E), is selected as the first node of barrier belt. Then the selected node selects the next node among its neighbors, to create the barrier belt. This process continues until the last virtual node, t, is reached. Thus, whenever the proposed method is performed, one node is selected to create barrier belt between two virtual nodes, t and s, in the network graph. This process is repeated k-times and finally, the set of these nodes forms k-barrier graph, Gb= (Vb , Eb ). In order to select the next node for barrier belt creation, each node (except active-none Accumulative ones) selects the next node among its neighbors, as following: ? If the node is not an Accumulation Point, it will select a next node among the neighbors being Accumulation Point members, such that the selected node has the least distance from the virtual node, t, too. But if there is no neighbor being Accumulation Point member, the node will select a neighbor with least distance from the virtual node, t, as the next node. ? If the node is an accumulation point member, it will select a neighbor with least distance from the virtual node, t, as the next node. Each node, after selecting its neighbor as the next node, will inform it about this selection, by sending elect-you message. This process continues until reaching the virtual node, t. # c) Maintenance & Recovery Phase In this phase, we try to maintain and recover the k-barrier graph coverage, G=(Vb, Eb), by using Accumulation Points created in k-barrier graph. This phase consists of two main works: first, the creation of new barrier belt and the second, recovering the fault barrier belt. Therefore, barrier belts change continuously during network lifetime, in such a way that all sensor network nodes are used equally. For this purpose, each Active-Accumulative node sends a findNextAP message to the next active node, in certain periods. The mentioned message includes node location and ID card. Each node, after receiving this message, sends it to the next active node, until the message reaches the next active-accumulative node. The second Active-Accumulative node, after receiving the message, begins to create a barrier belt between itself and the first Accumulation Point, by using an algorithm such as that in k-barrier coverage creation phase. The only difference between these algorithms, surely very important, is considering both accumulative nodes instead of virtual nodes, s and t. Finally, the first Active-Accumulative node sends the inactive message to the next node. Each node, after this message, first sends it to the next active node and then goes to sleep mode. This process continues until the message reaches the second Accumulation Point node and the previous barrier belt between these two Accumulation Points is removed. Fig. 7 shows the process. Considering this fact that the Active-Accumulation nodes perform as center and are active, always, their energy are consumed after a period of time. So, for this reason, each accumulation node, after a time period when the probability of node fail is high, replaces itself with one of the neighbor sleepaccumulation nodes, whenever it is informed about existence of such this neighbor. Each node, after receiving the message, changes into sleep mode and sends the message to the next node in barrier graph. ii. # Reparation Fault Barrier Belt # Simulation results In this section, the proposed protocol has been simulated using Matlab and compared with RIS algorithm. We set the barrier area length as 2km which is supposed to be covered with 1500 nodes. Then the nodes are deployed randomly along the area. The width of barrier area, in different configurations, has been considered as 120m, 90m, 60m and 30m, respectively. Therefore, the nodes deployment density parameter will be 0.00625, 0.00833, 0.0125 and 0.025 nodes per m . Notice that by more density, we don't mean using more sensor nodes and spending more different mode of nodes deployment. Considering that the nodes deployments are random, if thewidth of barrier region is considered less, the nodes deployment model will tend to APM model. We set transition and sensing radius of nodes as Rt=50m and RS=25m, respectively. The life time of nodes is assumed to be 60 days. # a) First Expriment In this experiment, we evaluate how the proposed protocol leads to prolong the network lifetime by selecting the proper nodes for performing k-barrier coverage. In simulations, the probability of each node to fail before ending its lifetime, is considered as =0.07. The simulation result has been presented in Fig. 9. Via the simulation, we evaluate the effect of nodes fails probabilities, before ending their lifetime, on the network lifetime, in whole. In various experiments, the probability of a node fail, before ending its lifetime, is considered as =0.07, =0.13 and =0.21. The simulation results have been presented in Fig. 10. As shown, the performance of the proposed protocol doesn't change so much, while increasing the parameter . The reason is that the proposed protocol, when a link fails, begins to recover the k-barrier graph and provide k-barrier coverage without re-executing the algorithm, completely. Therefore, there is no need to exchange the message and consume energy for re-executing the algorithm. Regarding the different slopes in diagrams, it is clear that more density in deployment, near to APM model, can yield to a more efficiency of protocol to maintain a balance in using nodes energies. Also, its efficiency for both recovering k-barrier coverage and fault tolerance will improve; because deploying a more density cause the proposed protocol to be more reliable in using the nodes energy, equally. Moreover, while failing nodes, it begins to recover k-barrier coverage, easily and with less massage overhead. V. # Conclusion In this paper we proposed a k-barrier coverage protocol, called APBC, for prolonging the network lifetime. The proposed protocol tries to prolong the network lifetime by establishing a balance in using nodes energies. Moreover, the proposed protocol presents a proper way in which the nodes fail without reexecuting the algorithm andconsuming much energy. According to simulation result, the proposed protocol, APBC, prolong the network lifetime in comparison with RIS method. 1![Figure 1: The reliability problems are very important for barrier coverage](image-2.png "Figure 1 :") ![Random Point Model (b) Independent Belt Model (c) Accumulation Point Model](image-3.png "") 3![Figure 3: Deployment Models in Barrier Coverage](image-4.png "Figure 3 :") 5![Figure 5: The coverage graph for the sensor network shown in Fig. 4Barrier Belt: A barrier belt, , is a sub-graph G = (V , E ) of the coverage graph, G = ( V , E ), and can be described by Eq. (2). t, s V j contains distinct vertex set V j = {s, v1, v2, v3,?, vi ,?, vnj ,t}](image-5.png "Figure 5 :") 46![Figure 6: k-barrier coverage and two Accumulative Point Node state: Each node, regarding whether it is the member of k-barrier graph, Gb=(Vb,Eb), and is the member of a Accumulation Point or not, has one of the modes mentioned bellow: ? Active-Accumulative ? Active-none Accumulative ? Sleep-Accumulative ? Sleep-none Accumulative. ? This template III.](image-6.png "( 4 )Figure 6") ![a) Starup Phase At startup phase, the nodes recognize their neighbors, and the coverage graph, G= (V, E) is created. For this purpose, by sending a "hello"message, Volume XII Issue XI Version I ? ? If d uv ? R ? e uv ? E ? G iff V?i ? V?j = {s,t} ? H , H?M ,?vi?H ? vi? M ? j = (V? i , E? i ) , G? j = (V? j , E? j ) ? 1? V? 2? V? 3? ? ? V? k If v? Va ? ?u? Va , euv?Ea](image-7.png "") ![Accumulative node creates a new barrier belt in certain periods until next Active-Accumulative node.](image-8.png "") 78![Figure 7: Creating new Barrier Belt](image-9.png "Figure 7 :Figure 8 :") 9![Figure 9: The proposed protocol leads to prolong the network life time by selecting the proper nodes for performing k-barrier coverage b) Secend Expriment](image-10.png "Figure 9 :") 10![Figure 10: The performance of the proposed protocol doesn't change so much while increasing parameter](image-11.png "Figure 10 :") © 2012 Global Journals Inc. (US) Global Journal of Computer Science and Technology This process continues until the message reaches the first Active-Accumulation node. Then, after receiving this package, the next Active-Accumulative node begins to create a barrier belt between itself and the previous Accumulation Point. This is done by using an algorithm such as that used in k-barrier coverage phase. The only difference in executing this algorithm is considering the coordinates of both Accumulation nodes instead of virtual nodes, s and t. This process is shown in Fig.8.(A) Find Next AP Package © 2012 Global Journals Inc. (US) Global Journal of Computer Science and Technology © 2012 Global Journals Inc. (US) * Handbook of Sensor Networks: Compact Wireless and Wired Sensing Systems MIlyas IMahgoub 2005 CRC Press London, Washington, DC * Energy efficient coverage control in wireless sensor networks based on multi-objective genetic algorithm JieJia JianChena GuiranChanga ZhenhuaTana Computers and Mathematics with Applications 57 2009 Elsevier * Multi-objective optimization for coverage control in wireless sensor network with adjustable sensing radius JieJia JianChena GuiranChanga YingyouWena Computers and Mathematics with Applications 57 2009 Elsevier Jingping Songa,c * Barrier coverage with wireless sensors SKumar THLai AArora Proc. ACM Mobicom ACM Mobicom 2005 * On Barrier Coverage in Wireless Camera Sensor Networks Kuei-PingShih Chien-MinChou I-HsinLiu Chun-ChihLi 1550-445X/10 $26.00 © 2010 IEEE * A Distributed Self-Deployment Algorithm for the Coverage Mobile Wireless Sensor Networks MTeddy AndreyVCheng Savkin IEEE COMMUNICATIONS LETTERS 13 11 NOVEMBER 2009 * Barrier Coverage For Underwater Sensor Networks StanleyBarr BenyuanLiu JieWang 978-1- 4244-2677-5/08/$25.00 2008 IEEE * Constructing Underwater Sensor Based Barriers Using Distributed Auctions StanleyBarr BenyuanLiu Wang 978-1-4244-5239- 2/09/$26.00 ©2009 IEEE * Accumulation Point Model for Barrier Coverage YongLin ZhengyiLe FilliaMakedon 978-1-4244-6314-5/09/$26.00 ©2009 IEEE * Local Barrier Coverage in Wireless Sensor Networks AiChen SantoshKumar 1536-1233/10/$26.00 _ IEEE 2010 * Strong Barrier Coverage with Directional Sensors LiZhang JianTang WeiyiZhang 978-1-4244- 4148-8/09/$25.00 IEEE ©2009 * Optimal sleep wakeup algorithms for barriers wireless sensors MEPosner SKumar THLai PSinha Fourth International Conference on Broadband Communications, Networks, and Systems Raleigh, NC 2007 * On k-Coverage in a Mostly Sleeping Sensor Network SantoshKumar HTen J´ozsefLai Balogh ACM 1-58113- 868-7/04/0009 Sept. 26-Oct. 1, 2004. 2004 Philadelphia, Pennsylvania, USA. Copyright * Maintaining sensing coverage and connectivity in large sensor networks HZhang JCHou Ad-hoc and Sensor Wireless Networks 1 2005 * Energy-efficient connected coverage of discrete targets in wireless sensor networks MLu JWu MCardei MLi Proc. of the International Conference on Computer Networks and Mobile Computing of the International Conference on Computer Networks and Mobile ComputingZhangjiajie, China 2005 * Strong Barrier Coverage of Wireless Sensor Networks BLiu ODousse JWang ASaipulla Proc. ACM MobiHoc ACM MobiHoc 2008 * Coverage in Wireless Sensor Networks: A Survey RaymondMulligan MHabib Ammari