Maximizing lifetime of heterogeneous wireless turnable camera sensor networks ensuring strong barrier coverage

Nội dung text: Maximizing lifetime of heterogeneous wireless turnable camera sensor networks ensuring strong barrier coverage

1. Journal of Computer Science and Cybernetics, V.37, N.1 (2021), 57–70 DOI 10.15625/1813-9663/37/1/15858 MAXIMIZING LIFETIME OF HETEROGENEOUS WIRELESS TURNABLE CAMERA SENSOR NETWORKS ENSURING STRONG BARRIER COVERAGE NGUYEN THI MY BINH1, HUYNH THI THANH BINH2,∗, NGUYEN HONG NGOC2, MAI DANG QUAN ANH2, NGUYEN KHANH PHUONG2 1Hanoi University of Industry 2Hanoi University of Science and Technology; Abstract. Barrier coverage in wireless camera sensor networks (WCSNs) has drawn the attention of research community since it promises an extremely large potential in applications involve movement detection and surveillance. As the battery resources are limited, improving the efficiency of energy is one of the key drivers for prolonging the lifetime of barrier coverage. However, most prior studies on this problem only worked on the networks with homogeneous sensors as well as omni-directional sensing coverage. This paper thus investigates the problem of maximizing the network lifetime to ensure strong barrier coverage for heterogeneous case (MLBC-HWCSN), that has not been taken into account in WCSNs research. We formulate the problem, and then propose a Modified Maximum Flow Algorithm (MMFA) consisting of three stages: constructing the flow-network, finding the maximum flow and refining the solution to solve this problem. Experimental results on extensive instances show that the proposed methodology is suitable for the studied problem and more efficient than existing algorithms. Keywords. Maximizing the network lifetime; Barrier coverage; Wireless sensor networks; Het- erogeneous wireless turnable camera sensor networks; Max flow; Edmond-Karp algorithm; Dinitz Algorithm. 1. INTRODUCTION Wireless camera sensor networks (WCSNs) have drawn the attention of research com- munity, because WCSNs can gather much richer information of environment in the forms of audio, image, video than conventional scalar sensor (e.g. temperature, humidity) [1, 2, 3]. WCSNs promise an extremely potential in applications involve movement detection, such as surveillance battlefield and intrusion detection which are tightly related to barrier coverage problem. Most prior researches for the problem aimed at finding as many barrier sets as possible to enhance coverage for the region of interest, which did not consider the power conservation and energy-efficiency. Conserving energy and prolonging battery lifetime of WSNs become important, because battery resources are limited. Mechanisms to conserve energy resources are highly desirable, as they have a direct impact on network lifetime. Network lifetime can be defined as the continuous interval time from the network setup time to the time that the deployed network *Corresponding author. E-mail address: binhdungminhkhue@gmail.com (NTM Binh); binhht@soict.hust.edu.vn (HTT Binh) ; ngocnguyen.nd97@gmail.com (NH Ngoc); anhmdq@gmail.com (MDQ Anh); phuongnk@soict.hust.edu.vn (NK Phuong) © 2021 Vietnam Academy of Science & Technology
2. 58 NGUYEN THI MY BINH et.al cannot provide adequate coverage, e.g. the coverage degree is less than a predefined thresh- old. It is no sense in discussing the network lifetime if the coverage degree is not feasible. For the barrier coverage, in case one barrier is formed, the network lifetime is determined by the sensor with the least energy belonging to the barrier. If no barrier can be constructed, the network lifetime is zero even though each node has available energy. Therefore, an excess of sensors are often deployed to obtain a high coverage probability and extend prolong the network lifetime. Since each sensor node is usually energy-limited and is hard to recharge or replace batteries with hostile or inaccessible environments in many scenarios, how to maxi- mize the network lifetime through efficient algorithms becomes vital and is highly desirable. Therefore, in this paper, we investigate the problem of maximizing the network lifetime en- suring barrier coverage by heterogeneous wireless camera sensor networks (HWCSNs) with turnable orientations under the random deployment strategy, called MLBC-HWCSN. A HWCSN includes two or more various types of camera sensor nodes with different functionalities and battery energy levels. Camera sensor nodes are always directional sensing coverage models. The WCSN is also called the wireless directional sensor network (WDSN), which possesses some unique characteristics, such as limited sensing angle, directional sens- ing, communicating range, and line of sight. These features cause the majority of existing coverage control theories and methods of traditional omni-directional wireless sensor net- works can not be directly applied to WDSNs [4]. Furthermore, the motivation in real life behind the HWCSN is the need of extra battery energy and more complex hardware is nec- essary to be embedded in some cluster heads, hence reducing the overall cost of hardware for the remaining sensor network. This paper focuses on HWCSN regarding different lifetime and types of sensors in which some camera sensors can rotate around their central (Figure 2 demonstrates a turnable sensor) while other can not. The maximizing barrier coverage lifetime problem in WSNs has been examined by the academy community. However, to our best knowledge, most these studies had assumed that sensor nodes were homogeneous and/or omni-directional sensing coverage. We are the first to study the optimizing lifetime strong barrier coverage in heterogeneous wireless turnable camera sensor networks. We make the following contributions: ˆ We formally define and present the mathematical formulation for the maximizing the network lifetime problem of heterogeneous wireless turnable camera sensor networks ensuring barrier coverage (MLBC-HWCSN problem). ˆ To address MLBC-HWCSN problem, we propose an efficient method called MMFA and show that it is better than existing method in term of computational time by experiments. The rest of the paper is organized as follows. Related works are presented in Section 2. Preliminaries and formulation for the optimizing lifetime of strong barrier coverage in het- erogeneous wireless camera sensor networks are discussed in Section 3. Section 4 introduces proposed algorithm. Section 5 describes our experiments along with computational and comparative results as well as conclusion in Section 6.
3. MAXIMIZING LIFETIME OF HETEROGENEOUS WIRELESS 59 2. RELATED WORKS Barrier coverage in WSNs has received extensive attentions by academy community in recent years, because of its advantage for security applications. The barrier coverage problem can be classified into two sub-problems [5, 6] as find penetration paths and build intrusion barriers, which have been explored and examined in different aspects. For finding penetration path, the researchers have been attracted to the minimal exposure path (MEP) problem [7, 8, 9]. The objective of the MEP problem is to find a penetration path having minimal exposure value from a source point to a destination point in the sensing field. The knowledge of MEP in the sensor field is very useful, because the MEP is a good performance metric, which can be used to measure the quality of surveillance system or coverage quality of the sensor network [10]. Furthermore, the MEP can be used in optimizing, managing and maintaining quality of coverage of the deployed WSNs. For building intrusion barriers, a series of front research results have been published [11, 12, 13, 14, 15, 16, 17, 18]. Kumar et. al. [11] introduced the notion of k-barrier coverage of a belt region using wireless sensors. The authors also proposed efficient algorithms for quickly determining, after deploying the sensors, whether a region is k-barrier covered. In [12], the authors presented an efficient distributed algorithm to construct strong sensor barriers on long strip areas of irregular shape without any constraint on crossing paths. In [15], the authors established a tight lower-bound for the existence of barrier coverage under line-based deployments. They then considered sensor deployment along multiple lines and shown how barrier coverage is affected by the distance between adjacent lines and the random offsets of sensors. These results illustrated that sensor deployment strategies had directly impacted on the barrier coverage of WSNs. Distinctive deployment strategies may result in significantly different barrier coverage. Therefore, in the deploying and planning of WSNs, the coverage goal and possible sensor deployment strategies must be carefully and jointly considered. In [13], the barrier coverage model was proposed for applications in which sensors are deployed for intrusion detection. This paper focused on a strong barrier coverage problem in wireless directional sensors networks (WDSNs). They then proposed efficient centralized algorithms and a distributed algorithm to solve the problem. Simulation results extrapolated that the provided algorithms can be obtained close-to-optimal solutions and consistently outperform a simple greedy algorithm. In [14], the concept of local barrier coverage (LBC) was provided. Chen et. al. showed that LBC guarantees the detection of all movements whose trajectory was confined to a slice of the belt region of deployment. They then demonstrated that LBC can be used to design localized algorithms by developing a novel sleep-wakeup algorithms for maximizing the network lifetime. Regarding maximized network lifetime ensuring strong barrier coverage in WSNs [19, 20, 21, 22, 23, 24], have delved into an optimizing lifetime of strong barrier coverage with various assumptions. In [19], the sleep-wakeup problem is to determine a sleeping schedule for sensors such that the lifetime of the network is maximized while maintaining the desired quality of monitoring. Although the maximizing lifetime problem is proven to be NP-hard in full coverage model, Kumar et al. were the first proposing a polynomial time algorithm which utilized the concept of multi-route network flows and proved its optimality to solve the sleep-wakeup problem for a specific class of applications, where a senor nodes were de- ployed as a smart barrier for detecting moving objects as in intrusion detection. In [20], the authors focused on the problem: how sleep-wakeup schedule can be used for omni-directional
4. 60 NGUYEN THI MY BINH et.al individual sensor nodes so that the redundancy is appropriately exploited to maximize the network lifetime? They then proposed algorithms can obtained an optimal solution on both homogeneous and heterogeneous sensor lifetime. Experimental results showed that when an optimal number of sensor nodes had been deployed randomly, statistical redundancy can be exploited to expire the network lifetime by up to seven times, and the assumption of homo- geneous lifetime can result in severe loss of the network lifetime. In [23], the authors studied the problem of maximizing the coverage lifetime of a barrier by mobile sensors with limited battery powers, where the coverage lifetime is the time until there is a breakdown in coverage due to the death of a sensor. They investigated two variants which are the fixed radii problem and the variable radii problem. They then designed parametric search algorithms for both problems for the case where the final order of the sensors was predetermined and for the case where sensors were initially located at barrier endpoints. In [24], Han et. al. introduced the problem of maximizing WSNs lifetime with heterogeneous turnable directional sensors, which is the most relevant to our work. The authors showed that the maximum lifetime problem is equivalent to an Integer Programming Problem (ILP), which is a NP-hard. Thus, a heuristic algorithm was proposed to achieve a preferable solution, called Two-round max- imum flow algorithm (TMFA). Although the algorithm was then proved experimentally to offer near-optimal solutions of the maximum lifetime problem in experimental circumstances, it still consumes large amount of time. Besides, the algorithm has not taken into account barriers that contain backward sensors sequence (Z -shape-like-barriers, Figure 1) that may reduce the accuracy of the solution, thus, there are rooms for improvement. Taking this issue into account, in this paper, we propose an efficient method for solving the maximize the network lifetime of HWCSNs with ensuring barrier coverage. Figure 1. Illustration of a heterogeneous wireless turnable camera sensor network. The sequence of sensors [S1,S2,S3,S4] with their corresponding sensing directions (blue circular sectors) forms a Z -shape-like-barrier which detects vertical penetrations. 3. PRELIMINARIES AND PROBLEM FORMULATION 3.1. Preliminaries To better formulate the MLBC-HWCSN problem, first, the following definitions are pro- posed.
5. MAXIMIZING LIFETIME OF HETEROGENEOUS WIRELESS 61 Definition 1. (Turnable camera sensor) The sensing region of a turnable camera sensor S is a sector represented by a tuple (P, R, α, W~ d), where P is the location of the camera sensor, R is the sensing radius of the sensor, α is the sensing angle, and W~ d is the working direction or also called the sensing orientation. The turnable camera sensor is also capable of changing the sensing orientation among a set of m fixed directions. Figure 2 depicts an instance of a turnable camera sensor S with sensing radius r, sensing angle α, and three possible sensing orientations {W~ d1, W~ d2, W~ d3}. Figure 2. Illustration of the turnable camera sensor Definition 2. (Lifetime of the HWCSN) The lifetime of the HWCSN is the amount of time the network can provide continuous strong barrier coverage status with the ability to rotate as well as to turn on and off of each individual camera sensor. In which, strong barrier coverage (mentioned in [12, 13]) is a condition of a WSN, often used to evaluate the quality of the network in term of barrier coverage. A general WSN is said to be achieving strong barrier coverage if on every penetration path through the sensor field from a boundary to the opposite one, the intruder is crossed and being sensed by at least one sensor of the WSN. To achieve the longest lifetime network, it is necessary to set up a schedule for the camera to turn on, off and rotate to a certain orientation at a certain time so that the HWCSN can maintain the strong barrier coverage status for the longest amount of time. It is the task to our MLBC-HWCSN problem. Definition 3. (Barrier-set) A Barrier-set B is a set of turnable camera sensors Sk, together ~ with their orientations W dk (k = 1 K), that form a strong barrier coverage for the whole HWCSN. The sensors must satisfy the following condition that form a strong barrier coverage for the whole HWCSN if only if none of its K sensors is lacked ~ B = {(Sk, W dk) | k = 1, , K}. Since a Barrier-set is also a type of HWCSN as it is a set of turnable camera sensors, the lifetime of the Barrier-set can also be defined as the amount of time it can provide continuous strong barrier coverage status. From Definition 4, one can see the lifetime L of a Barrier-set B could not be higher than the shortest lifetime of all the sensors in the Barrier-set B. In a HWCSN, different Barrier-sets could be found, but there is only one need to be active at a time so that the network can provide strong barrier coverage status continuously. As a result, the lifetime of the HWCSN is the total lifetime of several Barier-sets in which each Barrier-set operates individually and in turn. We thus could restate the task of problem as to find a list of Barrier-sets L = {Bj|j = 1, , M} such that:
6. 62 NGUYEN THI MY BINH et.al ˆ The total lifetime of the Barrier-sets in the list is maximal; ˆ If a sensor is included in multiple Barrier-sets, the total lifetime of these Barrier-sets is not greater than the lifetime of the sensor. 3.2. Problem formulation The MLBC-HWCSN problem consists of N heterogeneous turnable camera sensors CS = {S1,S2, ,SN } deployed uniformly randomly inside a belt region of length H and width W . Each sensor i (i = 1, , N) is defined by the following characteristics: ˆ Pi = (xi, yi): its position; ˆ Ri: its sensing radius; ˆ αi: half of its sensing angle; ˆ mi: the number of its possible orientations; ˆ Vi: the set of mi its possible orientations; ˆ li: its lifetime. The MLBC-HWCSN can be seen as the problem of determining an ordered list of Barrier- sets L = {Bj|j = 1, , M} in which each Barrier set is activated in turn, one after another. In other words, once the activating time of Barrier set Bj has been reached its lifetime Lj, it then be deactived so that the Barrier set Bj+1 could be active immediately. The objective is to maximize the total lifetime of the Barrier-sets M X Ltotal = Lj is maximal, j=1 while the following capacity constraint is satisfied. If a sensor Si ∈ CS is included in multiple Barrier-sets, the total lifetime of these Barrier- sets is not greater than the lifetime of the sensor M P tij ≤ li, ∀i = 1, , N, where tij = Lj if Si ∈ Bj, and 0 otherwise, ∀j = 1, , M. j=1 4. PROPOSED ALGORITHM To solve the MLBC-HWCSN problem, an approach based on ILP has been proposed to find the exact solution. Since ILP is NP-hard, it is not always possible to solve instances to opti- mality within limited computation time. Its complexity therefore calls for heuristic solution methodology when multiple constraints or realistically-sized instances are considered. We thus follow this track, propose an approximation algorithm called Modified Maximum Flow (MMFA), consisting of three stages: ˆ Transform the problem into a flow network problem. ˆ Find the maximum flow on the Flow-Network. ˆ Normalize the solution to meet extra constraints of the problem.
7. MAXIMIZING LIFETIME OF HETEROGENEOUS WIRELESS 63 4.1. Transforming the flow network problem The related work [24] also tried to transform the problem into a flow problem by using the EDBG graph and solved with TMFA algorithm. However, the method meets some critical issues that it does not take into account Z -shape-like-barriers as well as the algorithm consumes much time. To overcome these issues, a directed network graph generated from a HWCSN called Flow-Network is proposed. Using the WSN provided as input, assuming that the intruder is trying to cross the region from the bottom boundary to the top boundary, a Flow-Network is constructed by the following four steps: 1. A source vertex s and a sink vertex t are added to the Flow-Network. The source vertex corresponds to the left boundary while the sink vertex corresponds to the right boundary. 2. For each sector a of a sensor Si ∈ CS, two corresponding vertices ain and aout are added to the Flow-Network. A directed edge from ain to aout that has capacity equal to the lifetime l of sensor Si is added to the Flow-Network. For the sake of simplicity, we use the term the corresponding edge of sector a to specify this edge (ain, aout). The existence of this edge aims to ensure the flow going through a sector is not greater than the value of the lifetime l. 3. For every two overlapped sectors a and b that belong to two different sensors, a directed edge from vertex aout to vertex bin and a directed edge from vertex bout to vertex ain are added to the Flow-Network. Both edges have capacity of positive infinity. 4. For each sector a that overlaps the left boundary, a directed edge from s to ain with capacity of positive infinity is added to the Flow-Network. Similarly, if a overlaps the right boundary, a directed edge from aout to t with capacity of positive infinity is added to the Flow-Network. Due to the definition of capacity constraints based on the limited lifetimes of sensors, the problem is modeled into a capacity-on-vertices maximum flow problem instead of the capacity-on-edges. In order to do so, we generate an inner vertex and an outer vertex for each sector of a sensor. Edges toward the sector are connected to the inner vertex while edges direct from the sector are coming out of the outer vertex. An edge with capacity equal the lifetime of the sensor directs from the inner vertex to the outer vertex will ensure the constraint that the flow goes through a sector is not greater than the lifetime of it. Fur- thermore, different from EDBG, in Flow-Network, we added two edges of both directions between two sectors. This modification would help to create backward sequences of sensors in Z -shape-like-barriers, which thus improves the quality of the solutions for some data sets. It could be seen that a path from s to t on the obtained Flow-Network can represent a Barrier-set as the covered areas of sensors are overlapped and connected from the left boundary to the right boundary. Furthermore, a flow through a path from s to t is equivalent to the amount of time that the corresponding Barrier-set can operate, once the capacity constraints have been satisfied. Therefore, the total amount of lifetime of all the Barrier-sets can be easily computed as the total flow of the Flow-Network. To illustrate this step, we consider a HWCSN consisting of two sensors S1 and S2 as shown in Figure 3 (a). Sensor S1 has lifetime t1 and its two sensing orientations correspond to two
8. 64 NGUYEN THI MY BINH et.al (a) The deployed WSN (b) The corresponding Flow-Network constructed Figure 3. Illustration of constructing the Flow-Network from a WSN sectors a and b; sensor S2 has lifetime t2 and its only one sensing orientation corresponds to the sector c. Figure 3 (b) displays the corresponding Flow-Network constructed by using four steps described above. Each of three sectors a, b and c has a directed edge from its own inner vertex to outer vertex with capacity equal to the lifetime of the corresponding sensor. Other edges are added with capacity of positive infinity. 4.2. Finding the maximum flow Once the Flow-Network has been constructed from the original deployed network, we then find the maximal flow on the Flow-Network by using the Ford-Fulkerson method. The Edmond-Karp algorithm, a famous implementation of Ford-Fulkerson method, was used in [24] to find the maximal flow on EDBG. This algorithm is based on choosing shorter path on the number of edges as the residual path, thus it has the complexity of O(VE2). However, in this problem, the number of edges is often much higher than the number of vertices, we thus instead apply Dinitz algorithm to solve the maximum flow problem. Since the complexity of Dinitz algorithm is O(V 2E), it expects to significantly reduce of the computational time if compared to Edmond-Karp approach. 4.3. Normalizing the solution One could see that the maximum flow on the Flow-Network corresponds to the maximum lifetime of an alternate HWCSN where each sector acts as an independent sensor with independent lifetime. Since each sector has its independent lifetime that equals to the lifetime of its container sensor, the total lifetime of all the sectors of a sensor combine is higher than the actual lifetime of the sensor. In this case, an additional constraint must be satisfied that: the total flow going through all sectors of a sensor must not be higher than the lifetime of the sensor, given that the flow going through a sector equals to the flow going through corresponding edge of the sector as specified in Step 2 of Section 4.1. It turns out that finding satisfied list of ordered barrier sets to provide given optimal lifetime is not an easy task. We thus propose this stage to find the one that could provide lifetime to the HWCSN close to the optimal value as much as possible. It consists of two following steps:
9. MAXIMIZING LIFETIME OF HETEROGENEOUS WIRELESS 65 1. Step 1: For each sensor Si, check if the total flow goes through its sectors is higher than its lifetime. If and only if it is, apply step 2 for the sectors. 2. Step 2: Consider the sectors of Si in random order and reduce the flow goes through the sectors until the constraint is satisfied. Reducing flow through a sector can be done by finding a path that goes through the corresponding edge of the sector and then reduce the flow along the path. As an income, the output flow after this operator satisfies the additional constraint, thus, can be accepted as a valid solution. 5. EXPERIMENTAL RESULTS 5.1. Data setting In this section, various topologies are generated for experiment of the proposed algorithm. To prove the effectiveness of MMFA under different environment setting, we construct a dataset including of four different scenarios: ˆ Changing the number of sensors: The number of sensing orientations is 4, the sensing radius is 40m, the sensing angle is 45 degree and the number of sensors is changed from 50 to 400 with an increment of 50. ˆ Changing the number of sensing orientations: The number of sensors is 200, the sensing radius is 40m, the sensing angle is 45 degree and the number of sensing orientations is changed from 1 to 8 with an increment of 1. ˆ Changing the sensing radius: The number of sensors is 200, the number of sensing orientations is 4, the sensing angle is 45 degree and the sensing radius is changed from 20m to 80m with an increment of 5m. ˆ Changing the sensing angle: The number of sensors is 200, the number of sensing orientations is 4, the sensing radius is 40m and the sensing angle is changed from 10 degree to 80 degree with an increment of 10 degree. The size of the region is fixed at W = 300m and H = 150m. The lifetime of sensor is randomly generated in range 1, 2, 3. For each topology, the coordinates of sensors are uniformly distributed in the region. The sensing orientations are also randomly generated in the range of [0, 2π]. With all of the critical parameters being changed variously, this dataset guarantees to cover most of the cases of different environment settings with different types of networks. All the experiments are conducted with Java language (Java 8), under the same condition and on the same machine (Windows 10, Intel Core i7 4700HQ, 8Gb RAM). As a result, this will ensure the generality and make the experiment as well as the comparison fair to analyze. 5.2. Computational results In this subsection, we simulate MMFA and TMFA [24] on the scenarios generated above and analyze the output. Figures 4, 5, 6 and 7 illustrate the result of simulation on each scenario.
10. 66 NGUYEN THI MY BINH et.al Figure 4. Maximum lifetime and computational time by MMFA and TMFA when changing the number of sensors. Figure 5. Maximum lifetime value and computational time by MMFA and TMFA when changing the number of sensing orientations. From overall observation, for both methods, the maximum lifetime value tends to increase as the number of sensors, the number of sensing orientations, the sensing radius and the sensing angle increase. This is an expected outcome as the sensors and their sensing area are becoming more dense and overlapped when these parameters increase, thus, leads to better chance of forming more Barrier-sets. For the solution on maximum lifetime value, MMFA gives slightly better value compared to TMFA in some topologies. The reason behind this
11. MAXIMIZING LIFETIME OF HETEROGENEOUS WIRELESS 67 Figure 6. Maximum lifetime value and computational time by MMFA and TMFA when changing the sensing radius. Figure 7. Maximum lifetime value and computational time by MMFA and TMFA when changing the sensing angle. is that the Flow-Network is more accurate than EDBG since it calculates both directions of the edge instead of just one direction in EDBG. Therefore, in some particular cases, MMFA can find more valid barriers than TMFA can. Regarding computational time, MMFA has much shorter computation time compared to TMFA. This result is expected since the maximal flow calculation on MMFA with Dinitz algorithm is much faster than that on TMFA using Edmond-Karp algorithm. Statistics on topologies show that the number of vertices is thousands while the number of edges can easily
12. 68 NGUYEN THI MY BINH et.al reach millions regardless of experiment settings. As mentioned earlier, Dinitz algorithm has complexity of O(V 2E) while Edmond-Karp algorithm is O(VE2). Therefore, MMFA easily outperforms TMFA when considering computational time. If looking further in the process of each algorithm, the average number of steps it takes to gain residual flow on Dinitz algorithm until finding the maximal flow is only around 2 to 5. While on the other hand, the Edmond- Karp algorithm often takes up to 50 steps of gaining residual flow until it finally reaches the optima. The reason is because Dinitz algorithm gains flow by finding a blocking flow on the whole network while Edmond-Karp algorithm gains flow by finding only a residual path, which makes the algorithm take many steps to finish. As a result, MMFA has significantly smaller computational time compared to TMFA and the difference even gets more significant when the scale of the network or the complexity of the problem increases. Analyzing on each scenario, it can be seen that, as the number of sensors increases, the number of sensing orientations increases, the sensing radius increases and the sensing angle increases, the maximum lifetime value tends to increase as well. As these parameters increase, the chance of forming Barrier-sets from camera sensors is also increased as well. This changing on value of the maximal lifetime of HWCSN is expected, thus, the performance of our algorithm on various cases of critical parameters is matching the theory. Overall, the experimental results show that the proposed MMFA gives slightly better maximal lifetime solutions on much shorter computational time compared to TMFA. 6. CONCLUSION This paper investigates the maximizing the network lifetime of heterogeneous wireless turn- able camera networks ensuring strong barrier coverage problem named MLBC-HWCSN. This problem plays an important role to maintain energy-efficiency of wireless sensor networks. The MLBC-HWCSN is an optimization problem and transformed into ILP which is a NP- Hard. We thus devise an approximate algorithm called modified maximum flow (MMFA) for solving the MLBC-HWCSN problem. The MMFA can provide an acceptable solution in a short amount of time and includes three stages: constructing the flow-network, finding the maximum flow and refining the solution. We conduct extensive instances to analyze, evaluate and compare. Experimental results show that the proposed algorithm is suitable for the MLBC-HWCSN problem and surpasses the prior algorithm. ACKNOWLEDGMENT This research is funded by Vietnam National Foundation for Science and Technology Devel- opment (NAFOSTED) under grant number 102.01-2019.304 REFERENCES [1] I. F. Akyildiz, T. Melodia, and K. R. Chowdhury, “A survey on wireless multimedia sensor networks,” Computer Networks, vol. 51, no. 4, pp. 921–960, 2007. [2] D. Costal and L. A. Guedes, “The coverage problem in video-based wireless sensor networks: A survey,” Sensors, vol. 10, no. 9, pp. 8215–8247, 2010.
13. MAXIMIZING LIFETIME OF HETEROGENEOUS WIRELESS 69 [3] D. Tao and T.-Y. Wu, “A survey on barrier coverage problem in directional sensor networks,” IEEE Sensors Journal, vol. 15, no. 2, pp. 876–885, 2014. [4] M. Guvensan and A. G. Yavuz., “On coverage issues in directional sensor networks: A survey,” Ad Hoc Networks, vol. 9, no. 7, pp. 1238–1255, 2011. [5] B. Wang, “Coverage problems in sensor networks: A survey,” ACM Computing Surveys (CSUR), vol. 43, no. 4, pp. 1–53, 2011. [6] A. Sangwan and R. P. Singh, “Survey on coverage problems in wireless sensor networks,” Wireless Personal Communications, vol. 80, no. 4, pp. 1475–1500, 2015. [7] Y. Song, L. Liu, H. Ma, and A. V. Vasilakos, “A biology-based algorithm to minimal exposure problem of wireless sensor networks,” IEEE Transactions on Network and Service Management, vol. 11, no. 3, pp. 417–430, 2014. [8] N. T. M. Binh, C. M. Thang, N. D. Nghia, and H. T. T. Binh., “Genetic algorithm for solving minimal exposure path in mobile sensor networks,” IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1–8, 2017. [9] H. T. T. Binh, N. T. M. Binh, N. H. Ngoc, D. T. H. Ly, and N. D. Nghia, “Efficient approximation approaches to minimal exposure path problem in probabilistic coverage model for wireless sensor networks,” Applied Soft Computing, vol. 76, pp. 726–743, 2019. [10] T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan, and K. K. Saluja, “Sensor deployment strategy for detection of targets traversing a region,” Mobile Networks and Applications, vol. 8, no. 4, pp. 453–461, 2003. [11] S. Kumar, T. H. Lai, and A. Arora, “Barrier coverage with wireless sensors,” Proceedings of The 11th Annual International Conference On Mobile Computing And Networking, pp. 284–298, 2005. [12] B. Liu, O. Dousse, J. Wang, and A. Saipulla, “Strong barrier coverage of wireless sensor net- works,” in Proceedings of The 9th ACM International Symposium On Mobile Ad Hoc Networking And Computing. ACM, 2008, pp. 411–420. [13] L. Zhang, J. Tang, and W. Zhang, “Strong barrier coverage with directional sensors,” in GLOBE- COM 2009-2009 IEEE Global Telecommunications Conference. IEEE, 2009, pp. 1–6. [14] A. Chen, S. Kumar, and T. H. Lai, “Local barrier coverage in wireless sensor networks,” IEEE Transactions on Mobile Computing, vol. 9, no. 4, pp. 491–504, 2009. [15] A. Saipulla, C. Westphal, B. Liu, and J. Wang, “Barrier coverage of line-based deployed wireless sensor networks,” in IEEE INFOCOM 2009. IEEE, 2009, pp. 127–135. [16] J. He and H. Shi., “A distributed algorithm for finding maximum barrier coverage in wireless sensor networks,” IEEE Global Telecommunications Conference GLOBECOM 2010, pp. 1–5, 2010. [17] A. Saipulla, B. Liu, and J. Wang., “Barrier coverage with airdropped wireless sensors,” MILCOM -IEEE Military Communications Conference, pp. 1–7, 2008. [18] N. T. M. Binh, H. T. T. Binh, V. Le Loi, V. T. Nghia, D. L. San, and C. M. Thang, “An efficient approximate algorithm for achieving (k-!) barrier coverage in camera wireless sensor networks,” in Artificial Intelligence and Machine Learning for Multi-Domain Operations Applications, vol. 11006. International Society for Optics and Photonics, 2019, p. 1100613.
14. 70 NGUYEN THI MY BINH et.al [19] S. Kumar, T. H. Lai, M. E. Posner, and P. Sinha, “Optimal sleep-wakeup algorithms for barriers of wireless sensors,” in 2007 Fourth International Conference on Broadband Communications, Networks and Systems (BROADNETS’07). IEEE, 2007, pp. 327–336. [20] S. Kumar, T. H. Lai, and et. al., “Maximizing the lifetime of a barrier of wireless sensors,” IEEE Transactions on Mobile Computing, vol. 9, no. 8, pp. 1161–1172, 2010. [21] D. Kim, J. Kim, D. Li, S.-S. Kwon, and A. O. Tokuta, “On sleep-wakeup scheduling of non- penetrable barrier-coverage of wireless sensors,” in 2012 IEEE Global Communications Confer- ence (GLOBECOM). IEEE, 2012, pp. 321–327. [22] J. Du, K. Wang, H. Liu, and D. Guo, “Maximizing the lifetime of k-discrete barrier coverage using mobile sensors,” IEEE Sensors Journal, vol. 13, no. 12, pp. 4690–4701, 2013. [23] A. Bar-Noy, D. Rawitz, and P. Terlecky, “Maximizing barrier coverage lifetime with mobile sensors,” in European Symposium on Algorithms. Springer, 2013, pp. 97–108. [24] R. Han, L. Zhang, and W. Yang, “Maximizing strong barriers in lifetime-heterogeneous direc- tional sensor network,” in 2016 International Symposium on Wireless Communication Systems (ISWCS). IEEE, 2016, pp. 80–85. Received 22 January 2021 Accepted 21 March 2021