Article Preview
TopIntroduction
A Wireless Sensor Network (WSN) consists of a network of tiny, low-powered and multi-functional devices, operated by lightweight batteries (Ammari & Das, 2012). WSNs can perform complex tasks through the collaborative efforts of a large number of sensors that are densely deployed within the sensing field. One of the primary applications of WSNs is to monitor environmental or physical changes in a field of interest using sensor nodes. The information from the sensor nodes are then sent to a base station (or sink node) for further processing and analysis.
WSNs are often used to track a specific change in condition, or a specific event by deploying sensor nodes within a given field of reference. Earlier research works (Ammari & Das, 2012), typically considered the use of static sensor nodes to monitor the sensing field. Many of these works focused on the sensor node placement problem, where the goal is to cover the sensing area with a minimum number of sensor nodes (Cheng, Du, Wang, & Xu, n.d.; Gupta, Das, & Gu, 2003; Pan, Hou, Cai, Shi, & Shen, 2003; Tang, Hao, & Sen, 2006) . However, this assumes that each sensor node can be placed individually and accurately in a specific location. Further, it assumes that these sensor nodes would not be moved inadvertently (e.g. due to high wind conditions), after deployment. Although such placement may be possible for some indoor applications, for many other applications it is not feasible.
Deployment of sensor nodes at precise locations becomes technologically and/or economically impractical for many applications. For example, if the nodes are to be deployed in a hostile environment for monitoring volcanic activity or in a sensitive military zone, it may not be possible to place them at exact locations. Such imprecise placement can lead to areas, within the sensing field, that are not being monitored by any sensor node. Such regions are referred to as coverage holes (Theofanis P. Lambrou & Panayiotou, 2009) and any events occurring in these regions will remain undetected. Additionally, even if exact placement is possible, nodes may become faulty or be accidentally moved after deployment, leading to the occurrence of coverage holes (Theofanis P. Lambrou & Panayiotou, 2009; Wang, Cao, Berman, & Porta, 2007).
In recent years, the introduction of a small number of mobile nodes into the WSN has been suggested as a way to handle the issue of coverage holes (Theofanis P. Lambrou, Panayiotou, Felici, & Beferull, 2010). The mobile node(s) can move to the locations not covered by any of the stationary sensor nodes and monitor those areas. Although the cost of mobile nodes is higher than the static nodes, typically only a few such nodes would have to be added to achieve the desired coverage. These mobile nodes will travel along pre-planned routes and visit the unmonitored regions to maximize area coverage (Vecchio & López-Valcarce, 2015).
Using the guided mobility of a set of mobile nodes allows periodic monitoring of coverage holes. Areas within the sensing radius of one or more static nodes are covered continuously. For the remaining areas, the goal is to achieve guaranteed periodic coverage. Any event whose duration is longer than the interval between successive visits of a mobile node can be detected successfully. Therefore, it is extremely important to plan to route the mobile nodes appropriately, such that all the coverage holes can be visited in a minimum amount of time (Liu, Dousse, Nain, & Towsley, 2013; Zhu, Fan, Wu, & Wen, 2016).
In this paper, we present a novel integer linear programming (ILP) formulation for optimally calculating the paths for a set of mobile nodes in a WSN. The goal is to find a route for each mobile node that allows all uncovered regions of the sensing area to be monitored as quickly as possible. To the best of our knowledge, this is the first optimal formulation for visiting coverage holes, using multiple nodes, in a WSN. The path planning requires coordination among the mobile nodes to avoid visiting the same areas and cover the entire region in a minimum amount of time. The proposed heuristic can be used for larger networks, where the ILP may become computationally intractable.