# Lifetime-Maximized Strong Barrier Coverage of 3D Camera Sensor Networks

Authors: Yi Hong; Chuanwen Luo; Deying Li; Zhibo Chen; Xiyun Wang
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Camera sensor networks (CSNs) have advantages on providing the precise and multimedia information for plenty of applications. The high coverage quality of CSNs especially satisfies the monitoring requirements of barrier coverage. In three-dimensional (3D) application scenarios, the tracking of the potential intruder in the monitored irregular spaces brings more difficulties and challenges on strong barrier coverage for CSNs. In this paper, we consider the strong barrier coverage problem in 3D CSNs and focus on the objective of monitoring the intruder with high resolution and maximizing the network lifetime. We firstly introduce the definition and hardness proof for the problem based on the irregular space model and the network model, which adopts the Region of Interest (ROI) sensing model with high effective resolution. Secondly, we design two sleep-and-awake scheduling algorithms for the problem in homogeneous and heterogeneous networks, respectively, which are based on the auxiliary graph transformation and the disjoint flows construction. To evaluate these algorithms’ performance on the lifetime maximization, we conduct extensive simulation experiments and analyze their results on their advantages and applicable scenarios.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are being studied for a long time, which can be classified into sensor-based studies and data-based works. The most data-based works focused on the extracting kernel dataset and data query processing [1, 2]. The most sensor-based studies concentrated on the coverage and data transmission issues. With the high accuracy of monitoring information on coverage issue, camera sensor networks (CSNs) have been utilized for a wide range of applications which can be classified into indoor monitoring [3] and outdoor surveillance, e.g. military inspection and wild animal protection. For the military applications, CSNs can provide intrusion warning and action trend prediction for constructing the military boundaries to guarantee the quality of coverage service. For the wild animal protection, CSNs do not only prevent illegal personnel from entering the protection regions for illegal poaching but also avoid the protected animals from escaping from the regions. Thus barrier coverage has got a lot of attentions for research. To satisfy the coverage requirement of the practical applications, barrier coverage has the highest requirement on the sensed information in these coverage optimization problems.Among the related theoretical research of barrier coverage scheduling in CSNs, the most concerned issues are the particularity of the monitored space and the accuracy of the sensing model. For the particularity of the monitored space, the space may have an irregular terrain structure in the applications like mountainous regions as shown in the orange boundary in Figure1. The complex structure brings the difficulties and challenges for the sensor deployment and the sensing model construction, which should be considered in the sensor scheduling. For the accuracy of the sensing model, the most existing works adopted the full-view sensing model proposed in [4], which can guarantee the coverage for the target’s all facing directions. Besides the sensing omnidirectivity, high image resolution is also considered in the sensing model in [5].Figure 1
An instance of barrier coverage in forest region scenarios.In this paper, we study on the barrier coverage problem in 3D CSNs for the application with irregular geometrical characteristics and strong coverage requirements. The goal of the problem is maximizing the network lifetime under the premise in strong barrier coverage, called the Lifetime-Maximized Strong Barrier Coverage problem for 3D CSNs (LifMax-BC Problem). To solve the problem, the modelling of the irregular space is our first consideration. And we secondly consider the sensing model of the camera sensors in [5] which is being modeled based on the combination of the sensing region and the image resolution. Thirdly, we focus on the problem in different network conditions, homogeneous networks and heterogeneous networks. The list of our contributions is as follows.
(i)
We introduce LifMax-BC Problem for strong barrier coverage in 3D CSNs based on modelling the monitored space and the sensing region and give its hardness proof;(ii)
We propose two scheduling algorithms with the sleep-and-awake mode to solve the problem in the homogeneous networks and the heterogeneous networks, which are based on the auxiliary transformation and the disjoint maximum flow construction;(iii)
We conduct a large number of experiments and evaluate the performance of the proposed algorithms in terms of the constructed barrier number. Based on the simulation results, we analyze each scheduling algorithm’s applicable scenarios.The rest of the paper is organized as follows: Section2 presents the related works. Section 3 introduces the preliminaries, the definition of our problem and the NP-hardness proof. The two scheduling algorithms are, respectively, proposed in Section 4 and Section 5. Performance evaluations are given in Section 6.  concludes this paper and discusses the future work.


## 2. Related Works

The existing sensor-based research on wireless sensor networks (WSNs) can be classified into coverage problems and data transmission problems [6, 7], in which coverage includes target coverage, area coverage, and barrier coverage. Many mature sensing models of camera sensors have been formed from the contribution of the works on target and area coverage in WSNs.Based on the sensing model of different kinds of camera sensors, there are more studies on barrier coverage with different optimization goals. Based on the sensing model of directional sensors, Wang and Cao [8] studied the construction problem for strong barrier coverage and presented redundancy reduction techniques. The authors proposed the algorithms to solve the barrier coverage problems with the minimum coverage cost based on modeling the full-view-covered regions in [9]. And Mohammad et al. [10] proposed a centralized barrier constructing algorithms based on distributed learning automata for adjustable-orientation directional sensor networks.Among the optimization goals of barrier coverage, lifetime maximization and robustness guarantee have got attentions beside the coverage cost minimization. For lifetime maximization, Zhang et al. [11] designed a scheduling algorithm for maximizing the full-view coverage duration to solve the fairness-oriented coverage maximization problem, which is based on the full-view sensing model. For robustness guarantee, there exists lots of works to build k-barrier coverage. The k-barrier coverage algorithm for one-dimensional scenarios was proposed in [12], and the k-barrier coverage algorithm for one-dimensional scenarios was designed in [13]. For the sensors with the movement constraints, the strategy was presented for the maximum k-barrier coverage problem in [14]. There are some solutions for barrier coverage problem based on the classical theories: based on the divide and conquer theory, Wen et al. [15] proposed an efficient algorithm to construct k-barrier; based on the Dijkstra algorithm, Liu et al. [16] realized the minimum full-view coverage for mobile CSNs. And there are some algorithms for meeting special requirements in barrier coverage problem: the sensor interference issue was solved in the algorithm for k-barrier coverage in [17]; the one-way k-barrier algorithm was proposed in [18] to avoid one-way invasion; the strategy for filling barrier coverage holes was designed to realize the goal of minimizing the energy consumption [19].Considering the robustness guarantee, we focus on the strong barrier coverage problem with the goal of lifetime maximization and we will design two heuristics for CSNs with homogeneous networks and heterogeneous ones.


## 3. Preliminaries and Problem Formulations

### 3.1. Space Model

For the applications of CSNs in 3D scenarios, the monitored space can be modeled as a regular cube or cuboid in the most recent related works. The regular model of the space is beneficial to the deployment of the camera sensors and the construction of the sensing model of sensors. However, for the most applications with the rugged terrain or the mountain topography, the spaces are much different from those with the flat topography. The regular model of the space cannot provide precise position for the deployment of the sensors, which will affect the evaluation of the coverage quality.With the consideration of the topographic complexity of the monitored space in real scenarios, we model the monitored space into an irregular 3D curve stripST instead of a regular cube or cuboid. The 3D curve strip space ST has two terminal sections S, D and the ceiling and the ground planes T, B, which can be indicated as a quadruple ST=S,D,T,B as shown in Figure 2. Note that if the irregular 3D strip is a cyclic annular or a zigzag band, it can be decomposed into multiple curve strips which are similarly modeled in the paper.Figure 2
The 3D irregular space model for barrier coverage.


### 3.2. Sensing Model Based ROI and Network Model

For the sensing model of camera sensors, the full-view coverage model has been widely applied for the most two-dimensional scenarios, which was introduced in [4]. The full-view coverage model can provide the omnidirectional coverage based on the facing directions of the targets, which can guarantee high coverage accuracy.In this paper, considering the accuracy of the capturing information and 3D application scenarios, we adopt the Region of Interest (ROI) sensing model with high effective resolution, which was proposed in the research [5] as the 3D sensing model of camera sensors. The ROI sensing model of camera sensors dose not only consider the monitored target’s facing direction and position height but also construction the relationship between the 3D coverage space and the 2D projection area for the camera sensor. The model can satisfy the coverage requirement of application and the strategy design of sensor scheduling.The ROI sensing model is applied in a 3D curve strip spaceST in our paper. Considering a pair of a camera sensor v and a target t in ST, we focus on three groups of parameters: (1) the heights of v and t, denoted as H and h, respectively; (2) the length of target t, denoted as L, which is decide by the target itself; and (3)the angle between the t’s facing direction and the v’s viewing direction in the vertical plane (Effective vertical angle), denoted by β. To guarantee the effective coverage, the parameter has a range with the minimum effective vertical angle βmin and the maximum effective vertical angle βmax, which is determined by the required resolution and can be predefined. Based on the conclusion in [5], the angle between the target’s facing direction and the sensor’s viewing direction in the horizontal plane is out of the consideration because of the instability of its value. The definition of ROI model for the camera sensor is given as follows:Definition 1 (The ROI Sensing Model of Camera Sensors).
Consider a 3D curve strip spaceST=S,D,T,B, a camera sensor v located at X,Y,H and a target t located at x,y,h in ST, the effective projection sensing area of v for t is a sector-shaped ring or an annular-sector domain SecRing=X,Y,r,R on B with the inside radius r=H−h+L/2/tanβmax and the external radius R=H−h+L/2/tanβmin as shown in Figure 3.Figure 3
The illustration of camera sensing model.Based on the ROI sensing model of the camera sensor, we consider the target or intruder in the barrier coverage with the known height and length, i.e.,h and L. For example, if the monitored intruder is a person, the person’s height and face length can be set as 1.7 meters and 0.5 meters, respectively.The camera sensor network considered in our paper is composed ofN randomly-deployed nodes, which are candidate for barrier coverage scheduling for a 3D curve strip space ST=S,D,T,B. These N nodes are collected in the set V. For each node vi in V, it has its own position Xi,Yi,Hi and the maximum working duration li. With the consideration of the complexity and irregularity of the monitored space, the heights of the sensors are different. And we will discuss the cases with the same working duration and the different working durations later.For the network, the camera sensors can be modeled as a node setV=v1,v2,⋯,vN. And we consider the connectivity between each pair of nodes based on their sensing ranges. Based on the ROI sensing model of nodes, there is an edge eij=vi,vj between vi and vj if their sector-shaped rings intersect, i.e., SecRingi∩SecRingj≠∅. All the connected edges are collected into the edge set E. Then the original network is modeled as G=V,E as shown in Figure 4. And it is assumed that the transmission radius is at least twice of the sensing radius for each camera sensor, then the network G=V,E is a connected graph.Figure 4
The illustration of network modeling.


### 3.3. Problem Definitions and Hardness

We focus on the strong barrier coverage in 3D CSNs, which can guarantee to detect intruders without any constraint on crossing paths in the boundary space. Based on the preliminaries, we propose the Lifetime-Maximized Strong Barrier Coverage problem for 3D CSNs (LifMax-BC Problem), whose formal definition is as follows.Definition 2 (LifMax-BC Problem) Given.
(i)
A 3D continuous curve strip spaceST=S,D,T,B where S, and D are ST’s two terminal sections and T and B are the ceiling and the ground planes of ST(ii)
The camera sensor setV deployed in the space ST, v1,v2,⋯,vN, in which each node vi has its position Xi,Yi,Hi and maximum working duration li(iii)
A potential target or intruder crossing the spaceST with the predefined height h and face length L(iv)
LifMax-BC Problem is to find a collection of subsets ofVB=barrier1,barrier2,barrier3,⋯ in which each barrier guarantees the strong barrier coverage of the potential target, and schedule these barriers in sleep-and-awake mode with the barrier lifetimes lifetime1,lifetime2,lifetime3,⋯(v)
The constraint is that each camera sensor cannot be scheduled to exceed its maximum working durationli, i.e., ∑barrierk∈Blifetimek·xik≤li1≤i≤N, where xik is a binary variable to denote whether vi is scheduled in barrierk (if vi∈barrierk, xik=1; otherwise xik=0)(vi)
The goal is maximizing the network lifetime∑barrierk∈BlifetimekTo analyze the hardness of our problem, we review a classical NP-hard problem in graph theory, Minimum Weighted Set Cover (MWSC) Problem, which mathematical formulation is as follows:Given a setA composed of n elements, a collection C of m subsets of AC=A1,A2,⋯,Am where each Aj∈C1≤j≤m with a weight wAj, the problem is to find the minimum weighted subcollection C0⊆C such that ⋃Aj∈C0Aj=A and ∑Aj∈C0wAj is minimized.Based on the definition of MWSC Problem, the hardness proof of our problem is given as follows.Theorem 3.
The LifMax-BC Problem is NP-hard.Proof 1.
In order to prove the hardness of LifMax-BC Problem, we consider the special case of the problem: each node only contributes to only one barrier, i.e., its working duration overall contributes to the barrier it belongs to and∑kxik=1. Based on the ROI sensing model, we can construct candidate node-disjoint barriers barrier1,barrier2,⋯,barrierk′ on the structural parameters of the space ST and the known height and face length of the potential target. With the predefined maximum working duration li of each sensor, we can calculate the lifetime of each barrier, i.e., lifetimek=minvi∈barrierkli. If we assign the inverse of the lifetime as a weight to each barrier, i.e., weightbarrierk=1/lifetimek, we can rewrite the problem in the case with different lis as follows:
Given a sensor setV=v1,v2,⋯,vN and a barrier set C=barrier1,barrier2,⋯,barrierK′ in which each barrier is a subset of V and can guarantee the barrier coverage for the space ST, the problem is to find a subset of C, e.g. C0=barrier1,barrier2,⋯,barrierk, such that ∑k=1Kweightbarrierk is minimized and ∪barrierk∈C0barrierk=V.
Since the special version of LifMax-BC Problem is equivalent to MWSC Problem which is proven to be NP-hard [20]. Therefore, LifMax-BC Problem is NP-hard in general.To solve LifMax-BC Problem, we firstly consider the problem in homogeneous networks (denoted as Homo-LifMax-BC Problem), i.e., the camera sensors have the uniform working durationl0. We design a barrier coverage scheduling algorithm with disjoint barriers, Robust Barrier Coverage Algorithm. Secondly, we propose the scheduling algorithm with intersecting barriers for the problem in heterogeneous networks (denoted as Hetero-LifMax-BC Problem), i.e., the camera sensors have different maximum working duration lis, which is called as Enhancing Barrier Coverage Algorithm. The descriptions and analysis of these two algorithms are presented in the next two sections.


## 3.1. Space Model

For the applications of CSNs in 3D scenarios, the monitored space can be modeled as a regular cube or cuboid in the most recent related works. The regular model of the space is beneficial to the deployment of the camera sensors and the construction of the sensing model of sensors. However, for the most applications with the rugged terrain or the mountain topography, the spaces are much different from those with the flat topography. The regular model of the space cannot provide precise position for the deployment of the sensors, which will affect the evaluation of the coverage quality.With the consideration of the topographic complexity of the monitored space in real scenarios, we model the monitored space into an irregular 3D curve stripST instead of a regular cube or cuboid. The 3D curve strip space ST has two terminal sections S, D and the ceiling and the ground planes T, B, which can be indicated as a quadruple ST=S,D,T,B as shown in Figure 2. Note that if the irregular 3D strip is a cyclic annular or a zigzag band, it can be decomposed into multiple curve strips which are similarly modeled in the paper.Figure 2
The 3D irregular space model for barrier coverage.


## 3.2. Sensing Model Based ROI and Network Model

For the sensing model of camera sensors, the full-view coverage model has been widely applied for the most two-dimensional scenarios, which was introduced in [4]. The full-view coverage model can provide the omnidirectional coverage based on the facing directions of the targets, which can guarantee high coverage accuracy.In this paper, considering the accuracy of the capturing information and 3D application scenarios, we adopt the Region of Interest (ROI) sensing model with high effective resolution, which was proposed in the research [5] as the 3D sensing model of camera sensors. The ROI sensing model of camera sensors dose not only consider the monitored target’s facing direction and position height but also construction the relationship between the 3D coverage space and the 2D projection area for the camera sensor. The model can satisfy the coverage requirement of application and the strategy design of sensor scheduling.The ROI sensing model is applied in a 3D curve strip spaceST in our paper. Considering a pair of a camera sensor v and a target t in ST, we focus on three groups of parameters: (1) the heights of v and t, denoted as H and h, respectively; (2) the length of target t, denoted as L, which is decide by the target itself; and (3)the angle between the t’s facing direction and the v’s viewing direction in the vertical plane (Effective vertical angle), denoted by β. To guarantee the effective coverage, the parameter has a range with the minimum effective vertical angle βmin and the maximum effective vertical angle βmax, which is determined by the required resolution and can be predefined. Based on the conclusion in [5], the angle between the target’s facing direction and the sensor’s viewing direction in the horizontal plane is out of the consideration because of the instability of its value. The definition of ROI model for the camera sensor is given as follows:Definition 1 (The ROI Sensing Model of Camera Sensors).
Consider a 3D curve strip spaceST=S,D,T,B, a camera sensor v located at X,Y,H and a target t located at x,y,h in ST, the effective projection sensing area of v for t is a sector-shaped ring or an annular-sector domain SecRing=X,Y,r,R on B with the inside radius r=H−h+L/2/tanβmax and the external radius R=H−h+L/2/tanβmin as shown in Figure 3.Figure 3
The illustration of camera sensing model.Based on the ROI sensing model of the camera sensor, we consider the target or intruder in the barrier coverage with the known height and length, i.e.,h and L. For example, if the monitored intruder is a person, the person’s height and face length can be set as 1.7 meters and 0.5 meters, respectively.The camera sensor network considered in our paper is composed ofN randomly-deployed nodes, which are candidate for barrier coverage scheduling for a 3D curve strip space ST=S,D,T,B. These N nodes are collected in the set V. For each node vi in V, it has its own position Xi,Yi,Hi and the maximum working duration li. With the consideration of the complexity and irregularity of the monitored space, the heights of the sensors are different. And we will discuss the cases with the same working duration and the different working durations later.For the network, the camera sensors can be modeled as a node setV=v1,v2,⋯,vN. And we consider the connectivity between each pair of nodes based on their sensing ranges. Based on the ROI sensing model of nodes, there is an edge eij=vi,vj between vi and vj if their sector-shaped rings intersect, i.e., SecRingi∩SecRingj≠∅. All the connected edges are collected into the edge set E. Then the original network is modeled as G=V,E as shown in Figure 4. And it is assumed that the transmission radius is at least twice of the sensing radius for each camera sensor, then the network G=V,E is a connected graph.Figure 4
The illustration of network modeling.


## 3.3. Problem Definitions and Hardness

We focus on the strong barrier coverage in 3D CSNs, which can guarantee to detect intruders without any constraint on crossing paths in the boundary space. Based on the preliminaries, we propose the Lifetime-Maximized Strong Barrier Coverage problem for 3D CSNs (LifMax-BC Problem), whose formal definition is as follows.Definition 2 (LifMax-BC Problem) Given.
(i)
A 3D continuous curve strip spaceST=S,D,T,B where S, and D are ST’s two terminal sections and T and B are the ceiling and the ground planes of ST(ii)
The camera sensor setV deployed in the space ST, v1,v2,⋯,vN, in which each node vi has its position Xi,Yi,Hi and maximum working duration li(iii)
A potential target or intruder crossing the spaceST with the predefined height h and face length L(iv)
LifMax-BC Problem is to find a collection of subsets ofVB=barrier1,barrier2,barrier3,⋯ in which each barrier guarantees the strong barrier coverage of the potential target, and schedule these barriers in sleep-and-awake mode with the barrier lifetimes lifetime1,lifetime2,lifetime3,⋯(v)
The constraint is that each camera sensor cannot be scheduled to exceed its maximum working durationli, i.e., ∑barrierk∈Blifetimek·xik≤li1≤i≤N, where xik is a binary variable to denote whether vi is scheduled in barrierk (if vi∈barrierk, xik=1; otherwise xik=0)(vi)
The goal is maximizing the network lifetime∑barrierk∈BlifetimekTo analyze the hardness of our problem, we review a classical NP-hard problem in graph theory, Minimum Weighted Set Cover (MWSC) Problem, which mathematical formulation is as follows:Given a setA composed of n elements, a collection C of m subsets of AC=A1,A2,⋯,Am where each Aj∈C1≤j≤m with a weight wAj, the problem is to find the minimum weighted subcollection C0⊆C such that ⋃Aj∈C0Aj=A and ∑Aj∈C0wAj is minimized.Based on the definition of MWSC Problem, the hardness proof of our problem is given as follows.Theorem 3.
The LifMax-BC Problem is NP-hard.Proof 1.
In order to prove the hardness of LifMax-BC Problem, we consider the special case of the problem: each node only contributes to only one barrier, i.e., its working duration overall contributes to the barrier it belongs to and∑kxik=1. Based on the ROI sensing model, we can construct candidate node-disjoint barriers barrier1,barrier2,⋯,barrierk′ on the structural parameters of the space ST and the known height and face length of the potential target. With the predefined maximum working duration li of each sensor, we can calculate the lifetime of each barrier, i.e., lifetimek=minvi∈barrierkli. If we assign the inverse of the lifetime as a weight to each barrier, i.e., weightbarrierk=1/lifetimek, we can rewrite the problem in the case with different lis as follows:
Given a sensor setV=v1,v2,⋯,vN and a barrier set C=barrier1,barrier2,⋯,barrierK′ in which each barrier is a subset of V and can guarantee the barrier coverage for the space ST, the problem is to find a subset of C, e.g. C0=barrier1,barrier2,⋯,barrierk, such that ∑k=1Kweightbarrierk is minimized and ∪barrierk∈C0barrierk=V.
Since the special version of LifMax-BC Problem is equivalent to MWSC Problem which is proven to be NP-hard [20]. Therefore, LifMax-BC Problem is NP-hard in general.To solve LifMax-BC Problem, we firstly consider the problem in homogeneous networks (denoted as Homo-LifMax-BC Problem), i.e., the camera sensors have the uniform working durationl0. We design a barrier coverage scheduling algorithm with disjoint barriers, Robust Barrier Coverage Algorithm. Secondly, we propose the scheduling algorithm with intersecting barriers for the problem in heterogeneous networks (denoted as Hetero-LifMax-BC Problem), i.e., the camera sensors have different maximum working duration lis, which is called as Enhancing Barrier Coverage Algorithm. The descriptions and analysis of these two algorithms are presented in the next two sections.


## 4. Robust Barrier Coverage Algorithm for Homo-LifMax-BC Problem

Consider the case of homogeneous camera sensors with the same maximum working durationl0, the robustness of the network is important. And the pivotal key is avoiding the exhausted situation of some sensor, which will lead to the failure of the barriers that the sensor works for. Thus the scheduling should balance each sensor’s function in the coverage barriers. With the goal of maximizing the network lifetime, we adopt the sleep-and-awake mode for scheduling, i.e., there is one barrier working and the other barriers are in sleep mode for each round. The sleep-and-awake mode can transform the original goal into maximizing the number of batches of the constructed coverage barriers. For Homo-LifMax-BC Problem, we design Robust Barrier Coverage Algorithm which is composed of two phases, Auxiliary Graph Transformation and Barrier Coverage Scheduling.


### 4.1. Auxiliary Graph Transformation in Robust Barrier Coverage

To design a sleep-and-awake scheduling for barrier coverage, the first phase is to give an equivalent transformation for the network modelG=V,E illustrated in subsection 3.2. The 3D graph has the node set of camera sensors V=v1,v2,⋯,vN and is connected by the intersection of the sensing ranges among the sensors, i.e., SecRingi∩SecRingj≠∅1≤i,j≤N. For each node in V, we define its neighbor set and degree as Neighbvi=vjvj∈V∧vi,vj∈E and degvi=Neighbvi, respectively. Then, we transform the undirected and unweighted graph G into a directed and edge-weighted graph G∗ according to the following steps:Step 1. Virtual source and destination introducing. To guarantee the strong barrier coverage of any potential target in the spaceST=S,D,T,B, it is important to construct a consecutive barrier without interval. To the end, we introduce two virtual nodes on the terminal sections S and D, respectively, i.e., V⟵V∪s,t, as shown in Figure 5. For the additional source s on S, we add new edges to connect s and the nodes with the sensing range intersecting with the terminal section S, i.e., E⟵E∪s,vivi∈V∧SecRingi∩S≠∅. For example, v1’s sensing range intersects with S in G, and then the edge s,v1 can be added into E, as shown in Figure 5. In a similar way, for the additional destination d on D, the new edges are added to connect d and the nodes with the sensing range intersecting with the terminal section D, i.e., E⟵E∪vj,dvj∈V∧SecRingj∩D≠∅. Then, we update the network graph as G=V,E by introducing s and t and we construct the auxiliary graph G∗ in the next steps.Figure 5
An instance of auxiliary graph transformation.Step 2. Node-to-directed-edge converting. Based on the updated graphG=V,E, we give an equivalent transformation for each node vi in V (with the exception of s and d): vi is converted into a directed edge vi,v′i with the weight weightvi,v′i=degvi. For example, v1 with the degree 3 in the original G corresponds to the directed edge <v1,v′1> with weightv1,v′1=3 in G∗ as shown in Figure 5.Note that there is a clear division of each pairviandv′i on the function of connecting directed edges in Step 3. vi will be the destination of all the ingoing edges to vi and v′i will be the source of all the outgoing edges from vi in the original G which will give the detailed examples in Step 3. Then for the auxiliary graph G∗, the node set V∗=V∪vi′vi∈V, the edge set E∗=<vi,vi′>vi∈V, and the edge-weight set W∗=weightvi,vi′<vi,vi′>∈E∗.Step 3: Undirected-edge-to-directed-edge duplexing. For the auxiliary graphG∗, we will transform the edges in the original G and assign the weights for them, which are considered into the following three cases:
(i)
The outgoing edges froms: For each edge s,vi in E, it is converted into a directed edge s,vi with the weight weights,vi=1. Then E∗=E∗∪s,vis,vi∈E and W∗=W∗∪weights,vis,vi∈E. For example, the edge s,v1 in G has a corresponding edge s,vi with weights,vi=1 in G∗ as shown in Figure 5.(ii)
The bidirectional edges betweenvi,vjs: For each edge vi,vj in E, it is transformed into two directed edges v′i,vj and v′j,vi which both have the weight 1. Then E∗=E∗∪vi′,vj,vj′,vivi,vj∈E and W∗=W∗∪weightvi′,vj,weightvj′,vivi,vj∈E. For example, if there is an edge v5,v7 in G, the directed edges v′5,v7 and v′7,v5 are connected in G∗ as shown in Figure 5.(iii)
The ingoing edges tod: For each edge vj,d in E, it is converted into a directed edge <v′j,d> with the weight weightvj′,d=1. Then E∗=E∗∪vj′,dvj,d∈E and W∗=W∗∪weightvj′,dvj,d∈E. For example, the edge v6,t in G has a corresponding edge v6′,t with weightv6′,t=1 in G∗ as shown in Figure 5.After the above three steps, we construct an equivalent auxiliary graphG∗=V∗,E∗,W∗ for the next barrier constructing in subsection 4.2.


### 4.2. Barrier Coverage Scheduling in Robust Barrier Coverage

Based onG∗=V∗,E∗,W∗, we construct the feasible barriers with the maximum number based on the maximum flow algorithm as follows.Firstly, by takingG∗, s and t as the source and destination as the input of the Stint Algorithm in [21], K node-disjoint flows can be obtained which can be restored into a path set P=path1,path2,⋯,pathK. The paths in P are node-disjoint which can satisfy the requirement of LifMax-BC Problem in homogeneous network, i.e., it can avoid the situation that some sensor’s expiration causes the failure of the barriers which this sensor works for.Secondly, since the path set is constructed in the auxiliary graphG∗, we need to reduce these paths in G∗ back into the barriers in G. Here we take one path as an example to explain the reduction process and the reduction of other paths are in the same way. For each pathk=s,v1,v1′,v2,v2′,⋯,vp,vp′,d in P1≤k≤K, it can be reduced back to a coverage barrier barrierk according to the following process: for the edge s,vi, it is restored into the source vi of barrierk in G; for the edge v′i,vj, it is reduced into the undirected edge vi,vj of barrierk in G; for the edge v′j,d, it is restored into the destination vj of barrierk in G. As shown in Figure 6, two node-disjoint paths in the auxiliary graph are reduced into two barriers v1,v3,v6 and v2,v5,v7. And the lifetime of each barrier is l0 in the homogeneous network, thus the network lifetime is K·l0.Figure 6
An instance of barrier reduction.The detailed description of Robust Barrier Coverage Algorithm for Homo-LifMax-BC Problem is given in Algorithm1.Algorithm 1: Robust Barrier Coverage Algorithm for Homo-LifMax-BC Problem ST=S,D,T,B,G=V,E
1: SetV∗,E∗,W∗⟵∅, Lifetime=02:for each sensor vi in Vdo3:Neighbvi=vjvj∈V∧vi,vj∈E, degvi=Neighbvi4: //Phase 1: Auxiliary Graph Transformation5: //Step 1: Virtual source and destination introducing6:V⟵V∪s,t7:E⟵E∪s,vi,vj,dvi,vj∈V∧SecRingi∩S≠∅∧SecRingj∩D≠∅8: //Step 2: Node-to-directed-edge converting9:V∗=V∪vi′vi∈V10:E∗=vi,vi′vi∈V11:W∗=weightvi,vi′=degvivi,vi′∈E∗12: //Step 3: Undirected-edge-to-directed-edge duplexing13:for each edge s,vi in Edo14:E∗=E∗∪s,vi, W∗=W∗∪weights,vi=115:for each edge vi,vj in Edo16:E∗=E∗∪vi′,vj,vj′,vi, W∗=W∗∪weightvi′,vj=1,weightvj′,vi=117:for each edge vj,d in Edo18:E∗=E∗∪vj′,d, W∗=W∗∪weightvj′,d=119:G∗=V∗,E∗,W∗20: //Phase 2: Barrier Coverage Scheduling21: Apply Stint Algorithm in [21] to (G∗, s, t) and obtain K node-disjointpaths collected inP=path1,path2,⋯,pathK21:for each path pathk in Pdo23:for each directed edge on pathkdo24:   Case 1: fors,vi, it is restored into the source vi of barrierk.25:   Case 2: for eachvi′,vj, it is reduced into the undirected edgevi,vj of barrierk.26:   Case 3: forvi′,d, it is restored into the destination vj ofbarrierk.27:Lifetime=K·l028:barrier1,barrier2,⋯,barrierK, Lifetime.To analyze the time complexity of Algorithm1, we review the two phases of the algorithm: for auxiliary graph transformation, the virtual nodes introducing, node converting, and edge duplexing take the time of O1, OV and OE, respectively. Thus the time complexity of Phase 1 is OV under the assumption that V>E in barrier coverge; for barrier coverage scheduling, it adopts the Stint Algorithm for constructing the node-disjoint flows with the maximum number, which has the time complexity of OV·E2. And the reduction process takes the time of OV·E. To sum up, the time complexity of Algorithm 1 is OV·E2.


## 4.1. Auxiliary Graph Transformation in Robust Barrier Coverage

To design a sleep-and-awake scheduling for barrier coverage, the first phase is to give an equivalent transformation for the network modelG=V,E illustrated in subsection 3.2. The 3D graph has the node set of camera sensors V=v1,v2,⋯,vN and is connected by the intersection of the sensing ranges among the sensors, i.e., SecRingi∩SecRingj≠∅1≤i,j≤N. For each node in V, we define its neighbor set and degree as Neighbvi=vjvj∈V∧vi,vj∈E and degvi=Neighbvi, respectively. Then, we transform the undirected and unweighted graph G into a directed and edge-weighted graph G∗ according to the following steps:Step 1. Virtual source and destination introducing. To guarantee the strong barrier coverage of any potential target in the spaceST=S,D,T,B, it is important to construct a consecutive barrier without interval. To the end, we introduce two virtual nodes on the terminal sections S and D, respectively, i.e., V⟵V∪s,t, as shown in Figure 5. For the additional source s on S, we add new edges to connect s and the nodes with the sensing range intersecting with the terminal section S, i.e., E⟵E∪s,vivi∈V∧SecRingi∩S≠∅. For example, v1’s sensing range intersects with S in G, and then the edge s,v1 can be added into E, as shown in Figure 5. In a similar way, for the additional destination d on D, the new edges are added to connect d and the nodes with the sensing range intersecting with the terminal section D, i.e., E⟵E∪vj,dvj∈V∧SecRingj∩D≠∅. Then, we update the network graph as G=V,E by introducing s and t and we construct the auxiliary graph G∗ in the next steps.Figure 5
An instance of auxiliary graph transformation.Step 2. Node-to-directed-edge converting. Based on the updated graphG=V,E, we give an equivalent transformation for each node vi in V (with the exception of s and d): vi is converted into a directed edge vi,v′i with the weight weightvi,v′i=degvi. For example, v1 with the degree 3 in the original G corresponds to the directed edge <v1,v′1> with weightv1,v′1=3 in G∗ as shown in Figure 5.Note that there is a clear division of each pairviandv′i on the function of connecting directed edges in Step 3. vi will be the destination of all the ingoing edges to vi and v′i will be the source of all the outgoing edges from vi in the original G which will give the detailed examples in Step 3. Then for the auxiliary graph G∗, the node set V∗=V∪vi′vi∈V, the edge set E∗=<vi,vi′>vi∈V, and the edge-weight set W∗=weightvi,vi′<vi,vi′>∈E∗.Step 3: Undirected-edge-to-directed-edge duplexing. For the auxiliary graphG∗, we will transform the edges in the original G and assign the weights for them, which are considered into the following three cases:
(i)
The outgoing edges froms: For each edge s,vi in E, it is converted into a directed edge s,vi with the weight weights,vi=1. Then E∗=E∗∪s,vis,vi∈E and W∗=W∗∪weights,vis,vi∈E. For example, the edge s,v1 in G has a corresponding edge s,vi with weights,vi=1 in G∗ as shown in Figure 5.(ii)
The bidirectional edges betweenvi,vjs: For each edge vi,vj in E, it is transformed into two directed edges v′i,vj and v′j,vi which both have the weight 1. Then E∗=E∗∪vi′,vj,vj′,vivi,vj∈E and W∗=W∗∪weightvi′,vj,weightvj′,vivi,vj∈E. For example, if there is an edge v5,v7 in G, the directed edges v′5,v7 and v′7,v5 are connected in G∗ as shown in Figure 5.(iii)
The ingoing edges tod: For each edge vj,d in E, it is converted into a directed edge <v′j,d> with the weight weightvj′,d=1. Then E∗=E∗∪vj′,dvj,d∈E and W∗=W∗∪weightvj′,dvj,d∈E. For example, the edge v6,t in G has a corresponding edge v6′,t with weightv6′,t=1 in G∗ as shown in Figure 5.After the above three steps, we construct an equivalent auxiliary graphG∗=V∗,E∗,W∗ for the next barrier constructing in subsection 4.2.


## 4.2. Barrier Coverage Scheduling in Robust Barrier Coverage

Based onG∗=V∗,E∗,W∗, we construct the feasible barriers with the maximum number based on the maximum flow algorithm as follows.Firstly, by takingG∗, s and t as the source and destination as the input of the Stint Algorithm in [21], K node-disjoint flows can be obtained which can be restored into a path set P=path1,path2,⋯,pathK. The paths in P are node-disjoint which can satisfy the requirement of LifMax-BC Problem in homogeneous network, i.e., it can avoid the situation that some sensor’s expiration causes the failure of the barriers which this sensor works for.Secondly, since the path set is constructed in the auxiliary graphG∗, we need to reduce these paths in G∗ back into the barriers in G. Here we take one path as an example to explain the reduction process and the reduction of other paths are in the same way. For each pathk=s,v1,v1′,v2,v2′,⋯,vp,vp′,d in P1≤k≤K, it can be reduced back to a coverage barrier barrierk according to the following process: for the edge s,vi, it is restored into the source vi of barrierk in G; for the edge v′i,vj, it is reduced into the undirected edge vi,vj of barrierk in G; for the edge v′j,d, it is restored into the destination vj of barrierk in G. As shown in Figure 6, two node-disjoint paths in the auxiliary graph are reduced into two barriers v1,v3,v6 and v2,v5,v7. And the lifetime of each barrier is l0 in the homogeneous network, thus the network lifetime is K·l0.Figure 6
An instance of barrier reduction.The detailed description of Robust Barrier Coverage Algorithm for Homo-LifMax-BC Problem is given in Algorithm1.Algorithm 1: Robust Barrier Coverage Algorithm for Homo-LifMax-BC Problem ST=S,D,T,B,G=V,E
1: SetV∗,E∗,W∗⟵∅, Lifetime=02:for each sensor vi in Vdo3:Neighbvi=vjvj∈V∧vi,vj∈E, degvi=Neighbvi4: //Phase 1: Auxiliary Graph Transformation5: //Step 1: Virtual source and destination introducing6:V⟵V∪s,t7:E⟵E∪s,vi,vj,dvi,vj∈V∧SecRingi∩S≠∅∧SecRingj∩D≠∅8: //Step 2: Node-to-directed-edge converting9:V∗=V∪vi′vi∈V10:E∗=vi,vi′vi∈V11:W∗=weightvi,vi′=degvivi,vi′∈E∗12: //Step 3: Undirected-edge-to-directed-edge duplexing13:for each edge s,vi in Edo14:E∗=E∗∪s,vi, W∗=W∗∪weights,vi=115:for each edge vi,vj in Edo16:E∗=E∗∪vi′,vj,vj′,vi, W∗=W∗∪weightvi′,vj=1,weightvj′,vi=117:for each edge vj,d in Edo18:E∗=E∗∪vj′,d, W∗=W∗∪weightvj′,d=119:G∗=V∗,E∗,W∗20: //Phase 2: Barrier Coverage Scheduling21: Apply Stint Algorithm in [21] to (G∗, s, t) and obtain K node-disjointpaths collected inP=path1,path2,⋯,pathK21:for each path pathk in Pdo23:for each directed edge on pathkdo24:   Case 1: fors,vi, it is restored into the source vi of barrierk.25:   Case 2: for eachvi′,vj, it is reduced into the undirected edgevi,vj of barrierk.26:   Case 3: forvi′,d, it is restored into the destination vj ofbarrierk.27:Lifetime=K·l028:barrier1,barrier2,⋯,barrierK, Lifetime.To analyze the time complexity of Algorithm1, we review the two phases of the algorithm: for auxiliary graph transformation, the virtual nodes introducing, node converting, and edge duplexing take the time of O1, OV and OE, respectively. Thus the time complexity of Phase 1 is OV under the assumption that V>E in barrier coverge; for barrier coverage scheduling, it adopts the Stint Algorithm for constructing the node-disjoint flows with the maximum number, which has the time complexity of OV·E2. And the reduction process takes the time of OV·E. To sum up, the time complexity of Algorithm 1 is OV·E2.


## 5. Enhancing Barrier Coverage Algorithm for Hetero-LifMax-BC Problem

Consider the heterogeneous camera sensors with the different maximum working durationlis, increasing the coverage efficiency of the sensors with high lis is beneficial to maximize the network lifetime. If applying Algorithm 1 to solve Hetero-LifMax-BC Problem, disjoint barriers will lead to the situation that there is plenty of extended sleep time for the sensors with high lis, which goes against the problem goal of maximizing network lifetime. Thus it is necessary to design another algorithm to efficiently schedule the sensors with high durations from the perspective of making contribution to as many barriers as possible. Then, we design Enhancing Barrier Coverage Algorithm for Hetero-LifMax-BC Problem, whose main idea is to schedule the sensors with longer working durations and higher degrees in more barriers to maximize the network lifetime. There are also two phases in this algorithm, Auxiliary Graph Transformation and Barrier Coverage Scheduling.


### 5.1. Auxiliary Graph Transformation in Enhancing Barrier Coverage

This phase is composed of three steps, and we adopt the same Step 1. Virtual source and destination introducing as that in Section4 and obtain the updated graph G=V,E.To construct an auxiliary graph for barrier scheduling in the heterogeneous network, it is necessary to balance two important parameters for each node: the maximum working durationli and the neighborhood scale degvi. To this end, we introduce a new measure for each node as lifdegvi=li/degvi, which represents the node’s possible average working duration for each neighbor. Furthermore, to analyze each node’s contribution for barrier coverage, we need to give the criterion for parameters li and degvi. (1) For the node degree, vi’s degree is identified as high-degree if degvi>1; otherwise, it is regarded as low-degree. (2) For the maximum working duration, li is identified as high-lifetime if li≥AvgL, where AvgL=∑1≤i≤Nli/N; otherwise, it is regarded as low-lifetime. Based on the above preliminaries, we explain the process for Step 2 as follows.Step 2. Node-to-directed-edge converting. Based on the graphG=V,E added with s and t, the transformation for the nodes in V (with the exception of s and d) is divided into the following three cases:
(i)
V1=viviislow−degree. Since degvi=1 which stands for that vi has only one neighbor, vi will contribute on only one barrier if vi is scheduled in Phase 2, which is regardless of whether vi is high-lifetime or low-lifetime. In this case, vi is converted into 1 directed edge <vi,v′i> with the weight weight<vi,v′i>=li(ii)
V2=viviishigh−degreeandlow−lifetime. In this case, vi will give high contribution for several barriers and we divide its working duration equally to each connectivity relationship. In details, vi is converted into degvi directed edges vid,v′ids 1≤d≤degvi with the uniform weight weightvid,v′id=lifdegvi(iii)
V3=viviishigh−degreeandlow−lifetime. This case is the most complicated because of its possible unbalanced contributions to several barriers in scheduling. To avoid the unbalance, we propose a trade-off approach to guarantee the reasonably efficient scheduling for such nodes.Firstly, we sortvi’s neighbors in nonincreasing order on the values of lifdegvj, where vj∈Neighbvi. Secondly, we calculate the maximum value of the sum of the first sumvi neighbors’ lifdegvjs, which is no more than li. In other words, we maximize the contribution of vi on a part of neighbors (the first sumvi neighbors) rather than all the neighbors Neighbvi. Then we update Neighbvi as neighbi1,neighbi2,⋯,neighbisumvi by only retaining the first sumvi neighbors and eliminating other neighbors. Then, degvi=sumvi. Thirdly, we perform the transformation of vi: vi is converted into sumvi directed edges viu,v′iu with the different weights weightviu,v′iu=lifdegneighbiu1≤u≤sumvi.To conclude the above three cases, there is also a clear division of each pairvi and v′i on the function of connecting directed edges in Step 3. vi is in charge of all the ingoing edges to vi and v′i is responsible for all the outgoing edges from vi in the original G. And the construction of the auxiliary graph G∗ in Step 2 is as follows:
(a)
The node setV∗=⋃vi∈V1vi,vi′∪⋃vi∈V2vid,v′id1≤d≤degvi∪⋃vi∈V3viu,v′iu1≤u≤sumvi(b)
The edge setE∗=⋃vi∈V1<vi,vi′>∪⋃vi∈V2<vid,v′id>1≤d≤degvi∪⋃vi∈V3<viu,v′iu>1≤u≤sumvi(c)
The edge-weight setW∗=weightvi,vi′<vi,vi′>∈E∗Step 3. Undirected-edge-to-directed-edge duplexing. Based on the partial ofG∗ constructed in Step 2, we will add new directed edges by transforming the undirected edges in the original G as follows:
(i)
The outgoing edges froms are as follows: for each edge s,vi in E, it is converted into a directed edge s,vi with weights,vi=0, if vi∈V1; it is converted into degvi directed edges s,vid with weights,vid=0, if vi∈V2; it is converted into sumvi directed edges s,viu with weights,viu=0, if vi∈V3. Then E∗=E∗∪⋃vi∈V1∧s,vi∈E<s,vi>∪⋃vi∈V2∧s,vi∈E<s,vid>1≤d≤degvi∪⋃vi∈V3∧s,vi∈E<s,viu>1≤u≤sumvi and W∗=W∗∪weights,vi<s,vi>∈E∗(ii)
The bidirectional edges betweenvi,vjs: For each edge vi,vj in E, it is transformed into degvi·degvj pairs of directed edges v′idi,vjdj and v′jdj,vidi1≤di≤degviand1≤dj≤degvj which all have the weight 0. Then E∗=E∗∪⋃vi,vj∈Ev′idi,vjdj,v′jdj,vidi1≤di≤degviand1≤dj≤degvj and W∗=W∗∪weightvi′,vj,weightvj′,vivi′,vj,vj′,vi∈E∗.(iii)
The ingoing edges tod are as follows: For each edge vj,d in E, the transformation is similar with that of (i), i.e., E∗=E∗∪⋃vj∈V1∧vj,d∈Evj′,d∪⋃vj∈V2∧vj,d∈Ev′jd,d1≤d≤degvj∪⋃vj∈V3∧vj,d∈Ev′ju,d1≤u≤sumvj and W∗=W∗∪weightvj′,d=0<vj′,d>∈E∗


### 5.2. Barrier Coverage Scheduling in Enhancing Barrier Coverage

For this phase, we input the constructed auxiliary graphG∗,s,t to Stint Algorithm [21] and generate K node-disjoint flows which are collected in P=path1,path2,⋯,pathK. Note that since we divide the nodes with high possible contributions into several independent directed edges in Step 2 of Phase 2, we can also apply the node-disjoint flows algorithm, which can realize the scheduling of such nodes in different barriers.These node-disjoint paths inP are constructed in the auxiliary graph G∗ which are needed to be reduced back into the barriers in G. Since the nodes in V2 or V3 may be scheduled in multiply flows in P, the reduction process is different from that of Algorithm 1. For each path pathk in P1≤k≤K, it can be reduced back to a coverage barrier barrierk based on three kinds of edges: for the edge s,vi or s,vid, it is restored into the source vi of barrierk in G; for the edge v′i,vj or v′idi,vjdj, it is reduced into the undirected edge vi,vj of barrierk in G; and for the edge v′j,d or v′jd,d, it is restored into the destination vj of barrierk in G. Finally, the minimum nonzero weight on the corresponding path is the lifetime of each barrier in the heterogeneous network, i.e., lifetimek=min<vi,vi′>∈pathkweightvi,vi′.The whole description of Enhancing Barrier Coverage Algorithm for LifMax-BC Problem is given in Algorithm2.Algorithm 2: Enhancing Barrier Coverage Algorithm for Hetero-LifMax-BC Problem ST=S,D,T,B,G=V,E
1: SetV∗,E∗,W∗⟵∅, Lifetime=0, AvgL=∑1≤i≤Nli/N2:for each sensor vi in Vdo3:Neighbvi=vjvj∈V∧vi,vj∈E, degvi=Neighbvi4:lifdegvi=li/degvi5: //Phase 1: Auxiliary Graph Transformation6: SetV1,V2,V3⟵∅7:for each sensor vi in Vdo8:  Case 1: ifdegvi=1, V1⟵V1∪vi9:  Case 2: ifdegvi>1 and li≥AvgL, V2⟵V2∪vi10:  Case 3: ifdegvi>1 and li<AvgL, V3⟵V3∪vi11: //Step 1: Virtual source and destination introducing12:V⟵V∪s,t13:E⟵E∪s,vi,vj,dvi,vj∈V∧SecRingi∩S≠∅∧SecRingj∩D≠∅14: //Step 2: Node-to-directed-edge converting15:for each sensor vi in V1do16:V∗=V∗∪vi,vi′, E∗=E∗∪vi,vi′, W∗=W∗∪weightvi,vi′=li17:for each sensor vi in V2do18:V∗=V∗∪vid,v′id1≤d≤degvi, E∗=E∗∪<vid,v′id>1≤d≤degvi, W∗=W∗∪weight<vid,v′id>=lifdegvi1≤d≤degvi19:for each sensor vi in V3do20:   Calculate the maximum value of the sum of the firstsumvi neigh-bors’ lifdegvjs, which is no more than li.21:Neighbvi=neighbi1,neighbi2,⋯,neighbisumvi, degvi=Neighbvi22:V∗=V∗∪viu,v′iu1≤u≤sumvi, E∗=E∗∪<viu,v′iu>1≤u≤sumvi, W∗=W∗∪weight<viu,v′iu>=lifdegneighbiu1≤u≤sumvi23: //Step 3: Undirected-edge-to-directed-edge duplexing24:for each edge s,vi in Edo25:E∗=E∗∪⋃vi∈V1∧s,vi∈E<s,vi>∪⋃vi∈V2∪V3∧s,vi∈Es,vid1≤d≤degvi, W∗=W∗∪weights,vi=0<s,vi>∈E∗26:for each edge vi,vj in Edo27:E∗=E∗∪⋃vi,vj∈Ev′idi,vjdj,v′jdj,vidi1≤di≤degviand1≤dj≤degvj, W∗=W∗∪weightvi′,vj=0,weightvj′,vi=0<vi′,vj>,<vj′,vi>∈E∗28:for each edge vj,d in Edo29:E∗=E∗∪⋃vj∈V1∧vj,d∈Evj′,d∪⋃vj∈V2∪V3∧vj,d∈Ev′jd,d1≤d≤degvj, W∗=W∗∪weightvj′,d=0<vj′,d>∈E∗30:G∗=V∗,E∗,W∗31: //Phase 2: Barrier Coverage Scheduling32: Apply the maximum flow algorithm in [21] to (G∗, s, t) and obtain K node-disjoint paths collected in P=path1,path2,⋯,pathK33:for each path pathk in Pdo34:for each directed edge on pathkdo35:    Case 1: fors,vi or s,vid, it is restored into the source vi of barrierk.36:    Case 2: For eachv′i,vj or v′idi,vjdj, It Is reduced into the undirected edge vi,vj of barrierk.37:    Case 3: Forv′j,d or v′jd,d, It Is Restored into the Destination vj of barrierk.38:lifetimek=min<vi,vi′>∈pathkweightvi,vi′39:Lifetime=∑1≤k≤Klifetimek40: Returnbarrier1,barrier2,⋯,barrierK, Lifetime.Similarly with the analysis of Algorithm1, Algorithm 2 also has the time complexity of OV·E2. Thus the running times of our strategies are both polynomial. They are the feasible solutions of LifMax-BC Problem for homogeneous networks and heterogeneous networks.


## 5.1. Auxiliary Graph Transformation in Enhancing Barrier Coverage

This phase is composed of three steps, and we adopt the same Step 1. Virtual source and destination introducing as that in Section4 and obtain the updated graph G=V,E.To construct an auxiliary graph for barrier scheduling in the heterogeneous network, it is necessary to balance two important parameters for each node: the maximum working durationli and the neighborhood scale degvi. To this end, we introduce a new measure for each node as lifdegvi=li/degvi, which represents the node’s possible average working duration for each neighbor. Furthermore, to analyze each node’s contribution for barrier coverage, we need to give the criterion for parameters li and degvi. (1) For the node degree, vi’s degree is identified as high-degree if degvi>1; otherwise, it is regarded as low-degree. (2) For the maximum working duration, li is identified as high-lifetime if li≥AvgL, where AvgL=∑1≤i≤Nli/N; otherwise, it is regarded as low-lifetime. Based on the above preliminaries, we explain the process for Step 2 as follows.Step 2. Node-to-directed-edge converting. Based on the graphG=V,E added with s and t, the transformation for the nodes in V (with the exception of s and d) is divided into the following three cases:
(i)
V1=viviislow−degree. Since degvi=1 which stands for that vi has only one neighbor, vi will contribute on only one barrier if vi is scheduled in Phase 2, which is regardless of whether vi is high-lifetime or low-lifetime. In this case, vi is converted into 1 directed edge <vi,v′i> with the weight weight<vi,v′i>=li(ii)
V2=viviishigh−degreeandlow−lifetime. In this case, vi will give high contribution for several barriers and we divide its working duration equally to each connectivity relationship. In details, vi is converted into degvi directed edges vid,v′ids 1≤d≤degvi with the uniform weight weightvid,v′id=lifdegvi(iii)
V3=viviishigh−degreeandlow−lifetime. This case is the most complicated because of its possible unbalanced contributions to several barriers in scheduling. To avoid the unbalance, we propose a trade-off approach to guarantee the reasonably efficient scheduling for such nodes.Firstly, we sortvi’s neighbors in nonincreasing order on the values of lifdegvj, where vj∈Neighbvi. Secondly, we calculate the maximum value of the sum of the first sumvi neighbors’ lifdegvjs, which is no more than li. In other words, we maximize the contribution of vi on a part of neighbors (the first sumvi neighbors) rather than all the neighbors Neighbvi. Then we update Neighbvi as neighbi1,neighbi2,⋯,neighbisumvi by only retaining the first sumvi neighbors and eliminating other neighbors. Then, degvi=sumvi. Thirdly, we perform the transformation of vi: vi is converted into sumvi directed edges viu,v′iu with the different weights weightviu,v′iu=lifdegneighbiu1≤u≤sumvi.To conclude the above three cases, there is also a clear division of each pairvi and v′i on the function of connecting directed edges in Step 3. vi is in charge of all the ingoing edges to vi and v′i is responsible for all the outgoing edges from vi in the original G. And the construction of the auxiliary graph G∗ in Step 2 is as follows:
(a)
The node setV∗=⋃vi∈V1vi,vi′∪⋃vi∈V2vid,v′id1≤d≤degvi∪⋃vi∈V3viu,v′iu1≤u≤sumvi(b)
The edge setE∗=⋃vi∈V1<vi,vi′>∪⋃vi∈V2<vid,v′id>1≤d≤degvi∪⋃vi∈V3<viu,v′iu>1≤u≤sumvi(c)
The edge-weight setW∗=weightvi,vi′<vi,vi′>∈E∗Step 3. Undirected-edge-to-directed-edge duplexing. Based on the partial ofG∗ constructed in Step 2, we will add new directed edges by transforming the undirected edges in the original G as follows:
(i)
The outgoing edges froms are as follows: for each edge s,vi in E, it is converted into a directed edge s,vi with weights,vi=0, if vi∈V1; it is converted into degvi directed edges s,vid with weights,vid=0, if vi∈V2; it is converted into sumvi directed edges s,viu with weights,viu=0, if vi∈V3. Then E∗=E∗∪⋃vi∈V1∧s,vi∈E<s,vi>∪⋃vi∈V2∧s,vi∈E<s,vid>1≤d≤degvi∪⋃vi∈V3∧s,vi∈E<s,viu>1≤u≤sumvi and W∗=W∗∪weights,vi<s,vi>∈E∗(ii)
The bidirectional edges betweenvi,vjs: For each edge vi,vj in E, it is transformed into degvi·degvj pairs of directed edges v′idi,vjdj and v′jdj,vidi1≤di≤degviand1≤dj≤degvj which all have the weight 0. Then E∗=E∗∪⋃vi,vj∈Ev′idi,vjdj,v′jdj,vidi1≤di≤degviand1≤dj≤degvj and W∗=W∗∪weightvi′,vj,weightvj′,vivi′,vj,vj′,vi∈E∗.(iii)
The ingoing edges tod are as follows: For each edge vj,d in E, the transformation is similar with that of (i), i.e., E∗=E∗∪⋃vj∈V1∧vj,d∈Evj′,d∪⋃vj∈V2∧vj,d∈Ev′jd,d1≤d≤degvj∪⋃vj∈V3∧vj,d∈Ev′ju,d1≤u≤sumvj and W∗=W∗∪weightvj′,d=0<vj′,d>∈E∗


## 5.2. Barrier Coverage Scheduling in Enhancing Barrier Coverage

For this phase, we input the constructed auxiliary graphG∗,s,t to Stint Algorithm [21] and generate K node-disjoint flows which are collected in P=path1,path2,⋯,pathK. Note that since we divide the nodes with high possible contributions into several independent directed edges in Step 2 of Phase 2, we can also apply the node-disjoint flows algorithm, which can realize the scheduling of such nodes in different barriers.These node-disjoint paths inP are constructed in the auxiliary graph G∗ which are needed to be reduced back into the barriers in G. Since the nodes in V2 or V3 may be scheduled in multiply flows in P, the reduction process is different from that of Algorithm 1. For each path pathk in P1≤k≤K, it can be reduced back to a coverage barrier barrierk based on three kinds of edges: for the edge s,vi or s,vid, it is restored into the source vi of barrierk in G; for the edge v′i,vj or v′idi,vjdj, it is reduced into the undirected edge vi,vj of barrierk in G; and for the edge v′j,d or v′jd,d, it is restored into the destination vj of barrierk in G. Finally, the minimum nonzero weight on the corresponding path is the lifetime of each barrier in the heterogeneous network, i.e., lifetimek=min<vi,vi′>∈pathkweightvi,vi′.The whole description of Enhancing Barrier Coverage Algorithm for LifMax-BC Problem is given in Algorithm2.Algorithm 2: Enhancing Barrier Coverage Algorithm for Hetero-LifMax-BC Problem ST=S,D,T,B,G=V,E
1: SetV∗,E∗,W∗⟵∅, Lifetime=0, AvgL=∑1≤i≤Nli/N2:for each sensor vi in Vdo3:Neighbvi=vjvj∈V∧vi,vj∈E, degvi=Neighbvi4:lifdegvi=li/degvi5: //Phase 1: Auxiliary Graph Transformation6: SetV1,V2,V3⟵∅7:for each sensor vi in Vdo8:  Case 1: ifdegvi=1, V1⟵V1∪vi9:  Case 2: ifdegvi>1 and li≥AvgL, V2⟵V2∪vi10:  Case 3: ifdegvi>1 and li<AvgL, V3⟵V3∪vi11: //Step 1: Virtual source and destination introducing12:V⟵V∪s,t13:E⟵E∪s,vi,vj,dvi,vj∈V∧SecRingi∩S≠∅∧SecRingj∩D≠∅14: //Step 2: Node-to-directed-edge converting15:for each sensor vi in V1do16:V∗=V∗∪vi,vi′, E∗=E∗∪vi,vi′, W∗=W∗∪weightvi,vi′=li17:for each sensor vi in V2do18:V∗=V∗∪vid,v′id1≤d≤degvi, E∗=E∗∪<vid,v′id>1≤d≤degvi, W∗=W∗∪weight<vid,v′id>=lifdegvi1≤d≤degvi19:for each sensor vi in V3do20:   Calculate the maximum value of the sum of the firstsumvi neigh-bors’ lifdegvjs, which is no more than li.21:Neighbvi=neighbi1,neighbi2,⋯,neighbisumvi, degvi=Neighbvi22:V∗=V∗∪viu,v′iu1≤u≤sumvi, E∗=E∗∪<viu,v′iu>1≤u≤sumvi, W∗=W∗∪weight<viu,v′iu>=lifdegneighbiu1≤u≤sumvi23: //Step 3: Undirected-edge-to-directed-edge duplexing24:for each edge s,vi in Edo25:E∗=E∗∪⋃vi∈V1∧s,vi∈E<s,vi>∪⋃vi∈V2∪V3∧s,vi∈Es,vid1≤d≤degvi, W∗=W∗∪weights,vi=0<s,vi>∈E∗26:for each edge vi,vj in Edo27:E∗=E∗∪⋃vi,vj∈Ev′idi,vjdj,v′jdj,vidi1≤di≤degviand1≤dj≤degvj, W∗=W∗∪weightvi′,vj=0,weightvj′,vi=0<vi′,vj>,<vj′,vi>∈E∗28:for each edge vj,d in Edo29:E∗=E∗∪⋃vj∈V1∧vj,d∈Evj′,d∪⋃vj∈V2∪V3∧vj,d∈Ev′jd,d1≤d≤degvj, W∗=W∗∪weightvj′,d=0<vj′,d>∈E∗30:G∗=V∗,E∗,W∗31: //Phase 2: Barrier Coverage Scheduling32: Apply the maximum flow algorithm in [21] to (G∗, s, t) and obtain K node-disjoint paths collected in P=path1,path2,⋯,pathK33:for each path pathk in Pdo34:for each directed edge on pathkdo35:    Case 1: fors,vi or s,vid, it is restored into the source vi of barrierk.36:    Case 2: For eachv′i,vj or v′idi,vjdj, It Is reduced into the undirected edge vi,vj of barrierk.37:    Case 3: Forv′j,d or v′jd,d, It Is Restored into the Destination vj of barrierk.38:lifetimek=min<vi,vi′>∈pathkweightvi,vi′39:Lifetime=∑1≤k≤Klifetimek40: Returnbarrier1,barrier2,⋯,barrierK, Lifetime.Similarly with the analysis of Algorithm1, Algorithm 2 also has the time complexity of OV·E2. Thus the running times of our strategies are both polynomial. They are the feasible solutions of LifMax-BC Problem for homogeneous networks and heterogeneous networks.


## 6. Performance Evaluation

### 6.1. Experiment Plan

To evaluate the performance of the proposed algorithms for LifMax-BC Problem, we perform a series of experiments to compare their performance by JAVA. The optimization goal of LifMax-BC Problem is maximizing the network lifetime and we solve it for two cases (the same working duration and the different ones). Instead of the network lifetime, we choose the number of barriersK as the evaluation criterion. It is because that the number of constructed barriers stands for the number of scheduling rounds, which is more objective and fairer than the length of network lifetime, especially in the case that there is a big difference in the sensors’ working duration. Here, we denote the two algorithms as Robust Algorithm and Enhancing Algorithm for short.The experiments are performed in an irregular 3D space which is a 3D curve strip space with the length of500 units, the width of 300 units, and the height in the range of 50,80 units, i.e., the ceiling plane of the space is an irregular curved surface. And the boundary located in the space has the length of L. For the camera sensor network, n camera sensors are randomly deployed on the ceiling plane of the space, i.e., their positions Xi,Yi,Hi are randomly valued in the scope of the space. And the process of deployment is successfully finished when the network graph is connected. For each camera sensor, it has the sensing radius of 100 units, the Field-of-Vision 60∘ and the effective vertical angle β. And the maximum working duration li of each sensor is uniformed as 10 for Robust Algorithm and valued in the range of 5,30 for Enhancing Algorithm. Based on the ROI sensing model, each sensor has the minimum effective vertical angle βmin=0∘ and the maximum effective vertical angle βmax=β; for the potential target/intruder, we set the height as 17 units and the face length as 2 units for general situations.In the experiments, we will investigate the performance of the scheduling algorithms from two important parameters: the number of camera sensorsn and the effective vertical angle β, which are corresponding to two groups of settings: Group 1—n varies from 100 to 450 by the step of 50 (a) L=500, β=40∘; (b) L=500, β=60∘; and (c) L=500, θ=80∘. Group 2—β varies from 20∘ to 90∘ by the step of 10∘ (a) L=500, n=200; (b) L=500, n=300; and (c) L=500n=400. For each parameter setting, we run 100 instances and compute their average for evaluation.


### 6.2. Experiment Result Analysis

As the results in Figure7 shown, it can be observed that the number of constructed barriers from the proposed algorithms present rising trend with the enlargement of the networks n. Between the two algorithms, Enhancing Algorithm is more influenced by n, i.e., K obtained by the algorithm grows faster with the increasing of n; Robust Algorithm is less effected by n, and the gap between the results from the two algorithms becomes larger with the growth of n. The increasing of the network scale can satisfy more requirements of strong barrier coverage and Enhancing Algorithm utilizes some sensor for multiple barriers, which increases the number of barriers. Furthermore, from Figures 7(a) and 7(c), the better performance of Enhancing Algorithm becomes more significant when the effective vertical angle β=80∘. It can be explained that the enlargement of the effective vertical angle improves sensors’ coverage range which increases the probability of barrier coverage.Figure 7
The number of BarriersK vs. number of nodes n.
(a)
L=500, β=40∘(b)
L=500, β=60∘(c)
L=500, β=80∘Investigating the effect of the effective vertical angles on scheduling algorithms in Figure8, we can find that β’s change has less significant influence when network scale is relatively small and the number of barriers increases slowly in Figures 8(a) and 8(b), while β has more influence on the algorithms’ performance from Figure 8(c). Furthermore, the gap between the results from the two algorithms presents smaller than that obtained by varying the number of sensors. Seen from these three subfigures, Robust Algorithm’s results presents the rising trend with the increasing of β, which is less than that presented by Enhancing Algorithm. It can be concluded that the sensing conditions have less influence on the coverage quality when the network is homogeneous, and the difference on the coverage range is more beneficial for enhancing the coverage efficiency in the heterogeneous network.Figure 8
The number of barriersK vs. effective vertical angle β.
(a)
L=500, n=200(b)
L=500, n=300(c)
L=500, n=400From the above two groups of experiment results, we can conclude that the proposed algorithms are both efficient on maximizing the network lifetime and can be utilized into the solution for LifMax-BC Problem in the homogeneous and heterogeneous networks.


## 6.1. Experiment Plan

To evaluate the performance of the proposed algorithms for LifMax-BC Problem, we perform a series of experiments to compare their performance by JAVA. The optimization goal of LifMax-BC Problem is maximizing the network lifetime and we solve it for two cases (the same working duration and the different ones). Instead of the network lifetime, we choose the number of barriersK as the evaluation criterion. It is because that the number of constructed barriers stands for the number of scheduling rounds, which is more objective and fairer than the length of network lifetime, especially in the case that there is a big difference in the sensors’ working duration. Here, we denote the two algorithms as Robust Algorithm and Enhancing Algorithm for short.The experiments are performed in an irregular 3D space which is a 3D curve strip space with the length of500 units, the width of 300 units, and the height in the range of 50,80 units, i.e., the ceiling plane of the space is an irregular curved surface. And the boundary located in the space has the length of L. For the camera sensor network, n camera sensors are randomly deployed on the ceiling plane of the space, i.e., their positions Xi,Yi,Hi are randomly valued in the scope of the space. And the process of deployment is successfully finished when the network graph is connected. For each camera sensor, it has the sensing radius of 100 units, the Field-of-Vision 60∘ and the effective vertical angle β. And the maximum working duration li of each sensor is uniformed as 10 for Robust Algorithm and valued in the range of 5,30 for Enhancing Algorithm. Based on the ROI sensing model, each sensor has the minimum effective vertical angle βmin=0∘ and the maximum effective vertical angle βmax=β; for the potential target/intruder, we set the height as 17 units and the face length as 2 units for general situations.In the experiments, we will investigate the performance of the scheduling algorithms from two important parameters: the number of camera sensorsn and the effective vertical angle β, which are corresponding to two groups of settings: Group 1—n varies from 100 to 450 by the step of 50 (a) L=500, β=40∘; (b) L=500, β=60∘; and (c) L=500, θ=80∘. Group 2—β varies from 20∘ to 90∘ by the step of 10∘ (a) L=500, n=200; (b) L=500, n=300; and (c) L=500n=400. For each parameter setting, we run 100 instances and compute their average for evaluation.


## 6.2. Experiment Result Analysis

As the results in Figure7 shown, it can be observed that the number of constructed barriers from the proposed algorithms present rising trend with the enlargement of the networks n. Between the two algorithms, Enhancing Algorithm is more influenced by n, i.e., K obtained by the algorithm grows faster with the increasing of n; Robust Algorithm is less effected by n, and the gap between the results from the two algorithms becomes larger with the growth of n. The increasing of the network scale can satisfy more requirements of strong barrier coverage and Enhancing Algorithm utilizes some sensor for multiple barriers, which increases the number of barriers. Furthermore, from Figures 7(a) and 7(c), the better performance of Enhancing Algorithm becomes more significant when the effective vertical angle β=80∘. It can be explained that the enlargement of the effective vertical angle improves sensors’ coverage range which increases the probability of barrier coverage.Figure 7
The number of BarriersK vs. number of nodes n.
(a)
L=500, β=40∘(b)
L=500, β=60∘(c)
L=500, β=80∘Investigating the effect of the effective vertical angles on scheduling algorithms in Figure8, we can find that β’s change has less significant influence when network scale is relatively small and the number of barriers increases slowly in Figures 8(a) and 8(b), while β has more influence on the algorithms’ performance from Figure 8(c). Furthermore, the gap between the results from the two algorithms presents smaller than that obtained by varying the number of sensors. Seen from these three subfigures, Robust Algorithm’s results presents the rising trend with the increasing of β, which is less than that presented by Enhancing Algorithm. It can be concluded that the sensing conditions have less influence on the coverage quality when the network is homogeneous, and the difference on the coverage range is more beneficial for enhancing the coverage efficiency in the heterogeneous network.Figure 8
The number of barriersK vs. effective vertical angle β.
(a)
L=500, n=200(b)
L=500, n=300(c)
L=500, n=400From the above two groups of experiment results, we can conclude that the proposed algorithms are both efficient on maximizing the network lifetime and can be utilized into the solution for LifMax-BC Problem in the homogeneous and heterogeneous networks.


## 7. Conclusions

In this paper, we investigated the camera sensor scheduling problem for strong barrier coverage in 3D CSNs with the goal of maximizing the network lifetime, LifMax-BC Problem. The problem has been considered and analyzed for homogeneous networks (all the sensors have the uniform working duration) and heterogeneous networks (the sensors have different working durations). Based on the ROI sensing model, we, respectively, proposed two heuristic algorithms via the auxiliary graph construction and the maximum flow algorithm. The algorithm for homogeneous networks aims to increase the network robustness by constructing the disjoint barriers; and the algorithm for heterogeneous networks realizes the lifetime maximization via enhancing the utilization of the sensors with high working duration. By evaluating the performance of the proposed algorithms, the simulation results were analyzed in terms of the number of the scheduled barriers, which show that the algorithms have high efficiency on maximizing the network lifetime and can adapt to different network types. We will design the distributed strategies for the related optimization problems in the future.



---

*Source: 2659901-2022-09-19.xml*