Mountainous terrain coverage in mobile sensor networks
2015; Institution of Engineering and Technology; Volume: 9; Issue: 5 Linguagem: Inglês
10.1049/iet-com.2014.0443
ISSN1751-8636
Autores Tópico(s)Opportunistic and Delay-Tolerant Networks
ResumoIET CommunicationsVolume 9, Issue 5 p. 613-620 ArticleFree Access Mountainous terrain coverage in mobile sensor networks Kyungjun Kim, Corresponding Author Kyungjun Kim [email protected] POSTECH Information Research Laboratories, Pohang University of Science and Technology, Pohang, 790-784 KoreaSearch for more papers by this author Kyungjun Kim, Corresponding Author Kyungjun Kim [email protected] POSTECH Information Research Laboratories, Pohang University of Science and Technology, Pohang, 790-784 KoreaSearch for more papers by this author First published: 01 March 2015 https://doi.org/10.1049/iet-com.2014.0443Citations: 4AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Abstract The sensing field on three-dimensional (3D) terrains that is supposed to be fully covered by deployed nodes may not be covered because of random aerial deployment. Non-uniform coverage has a negative impact upon that their lifetime and performance get short and worse, respectively. Mobile sensor networks (MSNs) are introduced to improve a coverage problem from sensor malfunction by an obstacle or the terrestrial environment. Providing coverage in a mountainous terrain has become critical issues in MSNs. This work proposes a 3D coverage method that can consider a physical feature, such as slope, in a mountainous terrain, that is, a 3D spiral model that allows mobile sensors to move freely in spiral lines devised using the height and radius of a concaved terrain. In the proposed model, the reasonable number of sensors to be deployed and the designated sensing points achieve full coverage. This paper focuses on full coverage for which the spiral model challenges the reasonability in the number of sensors. The experimental results show that the proposed method provides improved performance in terms of coverage ratios and expected coverage time; in addition, this has higher accuracy in lower power cost and better expansibility. 1 Introduction Wireless sensor networks (WSNs) are a challenging area for industrial and military applications that are able to monitor physical phenomena around their locations [1]. The number of sensor nodes in the field of interest is difficult to decide. This is usually interpreted as k-coverage problem [2], such as genetic algorithm [3, 4], particle swarm [5] etc. To monitor a sensory field of interest, such as node movement and temperature changes, coverage is a very important research issue. The coverage is measured as a measure of quality of service (QoS), that is, how sensor nodes need to monitor a field of interest. Thus, the number of sensor nodes can be pointed out as an optimisation problem since this is related to the accuracy of coverage and deployment cost of sensors [6]. Similarly, the connectivity as the optimisation problem in a WSN has been studied in [7]. In the recent past, the solution based on estimations made by fire-fighting experts for measuring automatic forest fire is also presented in [8, 9]. Most of existing researches are mainly considered as platforms for environmental sensing and monitoring. However, for example, when injured people in mountainous and military applications have very limited mobility, the coverage of a mountainous region and sensor deployment using mobile sensors can be considered as one of the many problems [10]. There are considerable research efforts on providing better coverage in mobile sensor networks (MSNs). Coverage ratio in MSNs can be improved by increasing the number of mobile sensor nodes deployed [11]; accordingly, in order to improve coverage, how many sensors must be deployed in a sensing field and the lifetime of the expected coverage time are important issues in terms of communication performance. These issues in [12] have primarily focused on covering the sphere space within a sensor's sensing range; however, coverage on three-dimensional (3D) surfaces is not taken into consideration. Similarly, a solution that requires a reliable data transmission on active volcanoes have discussed in [13], but the solution has deployment cost problems and energy consumption. Full coverage on 3D space is difficult to resolve because sensors can be deployed freely on different elevation and terrain types. Therefore coverage is also related to the physical positions of sensors in the deployment region. This work is motivated by these problems to deploy sensors and achieve full coverage in 3D MSNs with different heights and terrain types. This study for improving the coverage of 3D mountainous terrains is related to as follows: how to cover the sensing field in an irregular 3D concave terrain and which sensors should be moved into the target point in order to sustain desirable node density in the sensing fields. However, the optimal deployment pattern issue in mountainous regions is specifically fundamental in 3D WSNs. Recently, there are the 3D coverage methods for the irregular 3D surfaces in small areas [8-12] and in terms of efficient routing the collected data through a multihop network in a 3D large-scale areas [6, 7, 13]. Furthermore, monitoring sensory fields in mountainous region is faced with difficulty, which is because of the difficulties of mobile sensor movement and sensor's current position measurement. Deployment task in MSNs sometimes takes long time to deploy an exact position. This generally uses GPS or reference nodes. Solutions using mobile beacons that provide the geographical position to sensor nodes lead to cause the range-based location problem. Mountainous area cannot be adequately observed by means of previous solutions, that is, to detect and observe phenomena caused from the 3D mountainous terrain with slanted sides. The sides in the mountainous terrain meet on the bias each other. Thus, this work focuses on a location model that is able to reflect the physical features in the 3D mountainous environment. In the proposed model, an opposite conical shape is similar to the shapes of the mountainous and the valley regions. The opposite conical shape is more efficient than a normal conical shape. The sensor nodes are approximately located in the middle part of the conical; moreover, when the sensors are willing to move, they travel rising curves and falling curves. The opposite conical shape, that is, the 3D spiral, has the shortest distance when a sensor goes round away obstacles and is willing to move the specific upward and downward directions (or points). In response to these issues, the 3D spiral model that is based on the Archimedean spiral [14] is proposed in this study. To date, this is the first work that practically utilises a 3D spiral, which can accommodate the physical characteristics of a 3D concave terrain with different heights and shapes and alter the shape of the spiral depending on the gradient of the concave terrain. Therefore this work makes the proposed model a versatile technique for applying in an MSN. The proposed model features simple-sensor node movement along spiral lines and permits the movement of mobile nodes in the gradient that does not allow the model to fully localise sensors and cover the sensing fields. The main contributions of this work are to provide a simple method of localising sensors that does not require additional equipment such as an anchor and control the necessary number of mobile sensor nodes, depending on the coverage and the required network lifetime. It has been extensively validated based on the concave terrain in close-to-operational conditions, 600 × 600 × −150 m in depth. This paper is organised as follows: Section 2 discusses the existing several approaches for coverage and localisation. Section 3 first addressed the mathematical rationale of the model and next identified the modelling for MSNs. Section 4 presents a coverage method using mobile sensors in concave terrain, including the planning and the positioning of mobile sensors. Section 5 shows some results obtained in the experiments. Section 6 presents conclusions and some experimental results followed by future works. 2 Related works This work present here closer views of the existing works for sensor deployment in complex terrain and detailed information of relevance for the coverage problem on mobile WSNs. Recently, many researchers have been investigating coverage and localisation in two-dimensional (2D) WSN [12]. To ensure the desired level of network connectivity in 3D WSNs, coverage is more challenging in 3D space as compared with 2D [13]. The authors on mountainous area in [15] defined the coverage hole and illustrated a coverage problem by directly applying traditional methods [14, 16]. The number of hops for transmitting data in mobile WSNs are lengthened because there may be obstacles in 3D space [17] and there may be the difference of height between sources from some forwarding sensors. Coverage in 3D space is measured by QoS that reflects how 3D space is monitored or how movement bodies are tracked [18]. The existing approaches mainly focused on sensors deployment to achieve adequate coverage level to perform a sensing task [19]. When they deployed sensors in random deployment manner, sensors are scattered on uncontrolled terrain position. This may cause sensing holes [20] because much energy can be consumed by sensors to be duplicated in the specific sensing area. Furthermore, the literature [21] proposed the topology control scheme in order to avoid sensing holes by using the sensing holes model. However, terrain features in 3D space are different depending on terrain types, elevation, obstacles, surface drainage etc. They are the key factors that limit the movement of mobile sensors [22]. To solve the environmental constraints of terrain, many methods are attempted. Mobilising nodes in the work of data collection can minimise communication cost and maximise the network reliability. The previous works focused on sink's mobility for maximising WSNs lifetime. To provide flexibility, several movement strategies are also based on logic programming. In addition, moving into a new location took much time when they face with obstacles. Mobile pattern in logic programming method can be categorised into three: randomised, predictable and controlled methods [14]. Randomised method [23] has tiered structure; a mobile node can move to any directions from its current position with the same probability. In the most cases of predictable methods [24], a mobility pattern of node follows a predetermined path. This mobility model is not suitable for the recondite terrain applications because the sensor nodes can revisit a few times. In addition the optimised mobility [25] incurs trade-off between mobility and density for coverage in MSNs. This approach can provide k-coverage over the field with a constant density and optimally relocate sensors. This k-coverage approach may cause larger self-deployment error because of the limited movement pattern. However, all the existing works on the self-deployment coverage issues in MSNs assumed that every sensor node can know its exact position by using some localisation technology. Although these methods increase the accuracy of nodes localisation for coverage, it makes the task of guaranteeing coverage much harder. In the 3D localisation for mobile WSNs, problems with these types of mobile pattern are that information may vary from place to place and from time to time and therefore a critical aspect that determines the quality of coverage related to network localisation. Owing to the variety of factors, such as the scalability of network, the inaccessibility of terrain, the information of network is often infeasible. Actually, when there are obstacles, localisation in practical 3D sensor network has been studied in the robotics. However, accuracy of localisation in MSNs can be accomplished through triangulation of neighbour nodes and on penalty of high cost using the common information of one-hop neighbours [26]. The coverage approaches, which consider connectivity in WSNs, focused on the optimal number of sensor nodes required to achieve a service quality in the literature [12]. Finding areas of high observability from sensors and identifying the best support are of primary concern. They do not examine thoroughly on a specific terrain, such as concaved shape. This coverage study based on these requirements is aimed at 3D MSNs. Furthermore, the coverage in large 3D terrain surfaces is different in terms of their complexity of terrain when compared with the mentioned problems above. 3 System model 3.1 Rationale and problem definition The Archimedean spiral is the locus of a point moving to or from the origin at a constant speed along a line rotating around that origin at a constant speed with constant angular velocity. The interesting feature of the Archimedean spiral has a constant separation distance between successive turnings of the spiral line. Feature 1 in the 3D MSNs allows for full coverage by varying the number of spiral turnings. For example, sensed data or beacon signals for localising sensors in terrestrial terrains are forwarded to a little higher place and vice versa because of the height difference of mountainous terrains; the same process is repeated until data reaches the surface of terrains. Forwarding manners in these applications can abstract to a 3D spiral. Therefore the proposed model using this spiral is applicable to monitor safety, for instance, in the open-pit mine. The most important thing in 3D MSNs is to provide fault tolerance and maximise coverage. To do this, mobile sensors move to the places where it can get the improvement of the maximum coverage [22]. Thus, this work has functions of fault-tolerance and energy efficiency in this manner. 3.2 Modelling the 3D spiral To model a sloped concave terrain, we construct a 3D spiral model, projected from a physical concave terrain, which is denoted as T with height d and radius r of l spiral turnings , as shown in Fig. 1. We first assumed that a sensing diameter of a node and some distance between σm and σm+1 are sr and sd, respectively. Fig. 1Open in figure viewerPowerPoint 3D spiral model, T T is composed of the total number of z points, T = {t0, t1,.., tm,…, tz}, where t0 = O is the origin of the spiral and also the starting point of sensing that combines and in T into an angle θ and tz is the endpoint of the spiral. The coordinates of tm on an arbitrary spiral are denoted as x(tm), y(tm) and z(tm). The point tm can be represented by the polar coordinate (rm, tm); for example, in Fig. 1, it is the Euclidean distance between the blank circular point dm on and point tm with a height z(tm) over the spiral turning. is assumed to be a virtual perpendicular line centred at O in T. The coordinates x(tm) and y(tm) of the point tm in the 3D spiral model are defined as: (1)respectively, for 0 ≤ tm ≤ r/b, where b ≤ sr/2 determines the distance between σm and σm+1. To project the physical property of a concave terrain into T, tangent θ is used, that is, ∠BOC, as shown in Fig. 1. Thus, z(tm), deciding the altitude of tm on T, can be derived as follows: (2)Based on (1) and (2), T can be derived. 3.3 Coordinating sensing points on T This subsection describes a method for determining sensing points to localise sensors on T. To decide n sensing points, this work assumes a sensing point x' for constructing 3D coverage in T. Let a set of x′ in T be in which the diameter sr, centred from a sensing point x', does not overlap each other. All S line up on the spiral turnings. Planning x′ in T can be first achieved by determining sd between spiral turnings. We exemplify two points, on and on σm+1, to derive sr in T, as shown in Fig. 1. The process of finding a point can be described as follows. First, can be expressed by using (1) and (2) as follows (3)where ti is the angle of with z(ti). In Fig. 1, the sensing point on σm+1 and are points to be located following the spiral line from O. Thus, the angle difference of and is exactly 2π. Two points are away from each other. Accordingly, can be obtained using (3) as follows (4)Therefore the distance between and in 3D space can be obtained by subtracting (3) from (4), using the Pythagorean Theorem. Thus, sd is (5)where b can be derived by sd = sr/2, as follows (6)The remaining sensing points in T can be found by adding the value of (5) from an arbitrary sensing point. The number of n sensors required to cover T is decided by sd and b. Thus, deploying method of the proposed model is to find n values in T. The total number of x′ in T, n, is greater than or equal to that of the active nodes k located in sensing point, defined as k ≤ n. In (5), the length of a spiral line in T [27] from O to tz, termed L(tz), is given as follows (7)where 0 ≤ tz ≤ r/b. The k numbers in T can be decided by dividing (7) into (5). The distance between each element (except from O to ) in set S is always equal to (5); thus, k can be acquired as follows (8)In (8), to avoid a void point that is unable to sense from sensor failures, such as energy depletion and obstacles, the entire n is (k + ε0) ε for 1.0 ≤ ε ≤ 5.0, where ε0 and ε, adjustable parameters [4], are constantly calibrated to fix a mathematical error and the number of neighbour nodes, respectively. The accuracy of monitoring in T can be managed by using ε. Before deploying all sensors, they still know all sensing points not to be assigned to a node. Accordingly, it is important whether how fast the deployed nodes enable to occupy the sensing point or not. Therefore ε parameter in T is related to fast planning, sensing accuracy and network lifetime. 4 Constructing 3D coverage 4.1 Algorithm In this section, we show how to achieve full coverage and how to deploy sensors in T. The spiral line in T, as shown in Fig. 1, is composed of a number of points with x-, y- and z-coordinates. The designated sensing points in regular sequence are located on a point of the coordinates, as well as assuming that each coordinate between sensing points is away from the same decimal number distance away from each other. For instances, the distance between the first point O and the next point increases by each 5 m in unit, as shown in Fig. 1. Thus, we can prevent error from GPS during the sensor location process. However, analysing and considering the GPS location error should consider many factors, such as multipath effects, atmospheric effects, selective availability etc., which extends the scope of this work. In this section, the technology requirements for planning and deploying sensors in T are given as follows: A spiral is a 3D curve that turns around an axis while continuously increasing its distance from that point. The gradient for climbing mobile nodes in T is < 45°; the movement of a mobile sensor can be controlled to left, right and diagonal directions. Sensing coverage, initial energy and transmission range are the same in the entire sensors. The transmission range is two times in the sensing range. Thus, the neighbouring nodes can share their information each other and construct their information tables, termed I. Before deploying the n sensors, n sensing points with their coordinates in T are planted in its memory. Thus, during the planning time, the sensors move to the closest sensing point. The planning algorithm is composed of two phases: location and filling-up. This algorithm achieves two objectives: how mobile sensors are planned in the sensory field and how many sensors effectively need to cover T. The objective of this algorithm is to minimise their moving energy while keeping their energy consumption. Assuming that there are no nodes around and some nodes in the neighbouring areas, that is, and , the proposed algorithm operates as follows. 4.1.1 Location phase In ts time period, all nodes U = {u0, u1,.., um, um+1,…, un} in each random time broadcast its position information C = {c0, c1,.., cm, cm+1, cn}. After broadcasting its information, un nodes hear other information broadcasted from other neighbouring nodes. After finishing ts, all nodes build an information table I = {I0, I1,.., Im, Im+1,…., In}. The information table, which is composed of three attributes: um, tm and ds which means the distance away from x′. The collected information is stored in order of nodes that are located in the closest distance from x′. Next, an information table constructs in Fig. 3b. Three nodes, that is, un−1, un, un+1, deployed around have its In table that constructs in step 2. First, un−1 moves to : When un−1 moves to , if the gradient is < 45°, un−1 moves in a straight line across the spiral; or else, it detours along the spiral line. In addition, the shortest path in T is a vertical movement. As soon as un−1 reach in , un−1 broadcasts its success message. Once the other remaining nodes receive a success message, un and un+1 remove In−1 in their information tables, that is, In and In+1. In the neighbouring region, let three nodes, that is, um−1, um, um+1, are deployed in around . In this case, an operation of nodes follows steps 3 and 4. There are two cases to be considered. When nodes that are deployed in around and regions did not know each other, the next order nodes un and um in In and Im judge that there are no nodes inside the neighbouring point since two nodes un and um do not receive the broadcast message from a neighbouring point . Nodes un and um move to at the same time; they follow steps 3a and 3b. When a node at first reach to , if one node disseminates its success message, other nodes that hears the success message broadcasted from the winning node stop its movement. Otherwise, if two nodes simultaneously reach ; they disseminate success messages at the same time, these messages subsequently conflict. Then, two nodes go to the sleep state for random backoff-time period. In addition, when their random backoff time expires, they again try to disseminate their success messages. If one node wins the competition, this node disseminates its success message and goes to step 5b. Fig. 2 gives an example of the operation in the location phase. After finishing the location phase, for example, u6 moves closer to and broadcasts its success message once it is located in . If the gradient from towards is < 45°, the node u6 in Fig. 2 moves in a straight line; if not, it detours along the spiral line. In addition, the shortest path in this model is a vertical movement. Once the other remaining nodes receive other success message, they remove the column including u6 from the information table Im. At the same time, if u0 within does not receive the broadcast message from a neighbouring point , then nodes within judges that there are no nodes inside the neighbouring point . Thus, the closest node un from the neighbouring point moves towards the sensing point . However, in the deployment phase when there are many rival nodes, step 6 continuously arises. This decreases system performance. We refer to as a filling-up problem. Fig. 2Open in figure viewerPowerPoint Planning in the spiral line Fig. 3Open in figure viewerPowerPoint Back-up phase a Example of filling-up mechanism b Information table 4.2 Filling-up phase for filling-up problem We describe a procedure in detail to solve the filling-up problem, and propose a filling-up algorithm that is able to heal a corrupted sensing point. In particular, when more than two nodes compete to fill-up a void sensing point in step 6 in the deployment phase, these nodes come across the filling-up problem. When the filling-up problem arises, the algorithm considers two cases: what if some nodes simultaneously try to arrive at the same sensing point and the what if the remaining nodes ranked in next order in each In continuously move towards an unoccupied sensing point until they hear a success message. We assume that there are no deployed nodes within sensing point , as shown in Fig. 3. We propose a filling-up algorithm below. 4.2.1 Filling-up phase If their disseminated messages conflict, then the concerned nodes go to slip state for a random backoff time period. If the random back off time from one of the awakening nodes expires and still is not occupied by other nodes, then the awaken node move to fill-up the unoccupied region . The node disseminates its success message and goes to a waiting state for the designated planning time. Otherwise, when the disseminated message from node do not conflicts, the node disseminates success messages and the concerned nodes that hear the disseminated message stop to move, and the concerned nodes go to sleep state. In addition, if is in a occupy state by one node, the node immediately tries to disseminate its success messages. If the disseminated messages do not conflict, in order to avoid extra messages disseminating by the other remaining nodes, the node periodically disseminate its success messages for the designated planning time. Then the other remaining nodes that hear the disseminated message in moving stop to move, disseminate success messages and go to sleep state. Otherwise, if all the remaining nodes still are moving, a node that first reaches at the target point tries to disseminate its success message. If the disseminated message do not conflict, the concerned nodes broadcast once more the received success message in order to avoid extra messages disseminating by the other remaining nodes. Else, if the disseminated message conflicts, go to step 1a. We exemplify the operation to avoid the filling-up problem in the planning algorithm, as shown in Fig. 3. In in each node are ranked in order of node closer to the sensing range. After finishing the setup phase, neighbouring nodes that are deployed in sensing points and xj+1 know that there is no success message from sensing point . They check their information table and then only node u0 moves to xj+1 not the remaining nodes. Nodes u4 and u0 in Fig. 3b have the same distance from sensing point . In this case, a node u0 first moves since a node with higher order in number has higher priority. u0 node disseminates success message and the remaining nodes that hear success message from u0 once more broadcast the received success message. Then the remaining nodes are deactivated. The nodes located within the range of periodically monitor the activated node. If the active node's energy is exhausted, the next ranked node in the information table moves to the unoccupied point. All remaining nodes deactivated periodically monitor the activated node within its sensing area until its energy is depleted. Now, we analyse that the time complexity for the planning algorithm, and derived that k numbers to be deployed is greater than or equal to n sensing points in T, that is k ≤ n. To calibrate the deployment cost by sensor failure, such as sensor malfunction, k by using calibrating constants, that is, ε0 and ε, is calibrated; therefore k ≒ n. Thus, deploying sensors to be activated in n sensing points takes O(n) time. Furthermore, in the worst case that do not use calibrating constants, the time complexity takes less than or equal to O(kn) time. 5 Performance evaluation 5.1 Evaluation environment We first compared the performance of the previous localisation strategy in simulation. To compare the proposed model, this work simulated a wireless sensor network with 100–500 sensors, which are randomly deployed and increased by 100 sensors. In this experiment, we split the lifetime of the sensor network into short periods known as time units, as shown in Fig. 4. Fig. 4Open in figure viewerPowerPoint Experiment environment The experiment results were obtained using MATLAB v7.1 for 120–2000 time units, which represents a time duration to perform timing and delay operations in sensors, on the given terrain model (600 × 600 m and −150 m in depth), and 100–500 sensors are randomly deployed and increased by 100 sensors in experiment. All mobile sensors have random altitude (0–150 m in depth) and the same energy, moving speed and power consumption. The initial energy of a mobile sensor has 1000 J and consumes 8.3 J/m in moving. The maximum and the minimum speeds of a node in the random waypoint mobility model are always set to 5 m/s and 0.5 m/s, respectively. The transmission range for 20 m ≤ sr ≤ 50 m is 2srm. 5.2 Simulation and experiments This work now compares the performance of the proposed algorithm. Locating mobile sensors on all x′ points took 41 s on average. Energy consumption ratio for the sensor setup is < 2% in total. Figs. 5a and b show the amount of the remaining energy in coverage rate 95% and 100%, respectively, after sensor setup in 1000 time units. Fig. 5Open in figure viewerPowerPoint Amount of the remaining energy after setup a Coverage rate = 95% b Coverage rate = 100% After 1700 time units, coverage rate decreased stepwise; in 2000 time units, the coverage rate in ε = 5.0 is below 50% because nodes battery exhaustion rapidly increases in an exponential way. The coverage is highly regular depending on sr and ε, and thus coverage improves when sr and ε increase from 20 to 50 m and 1.0 to 5.0
Referência(s)