We compute BCP(s, t), a Best coverage Path between two points s and t in the presence of m line segment obstacles in a 2D field under surveillance by n sensors. Based on nature of obstacles, we have studied two varian...
详细信息
We compute BCP(s, t), a Best coverage Path between two points s and t in the presence of m line segment obstacles in a 2D field under surveillance by n sensors. Based on nature of obstacles, we have studied two variants of the problem. For opaque obstacles, which obstruct paths and block sensing capabilities of sensors, we present algorithm ExOpaque for computation of BCP(s, t) that takes O((m(2)n(2) + n(4)) log(mn + n(2))) time and O(m(2)n(2) + n(4)) space. For transparent obstacles, which only obstruct paths but allow sensing, we present an exact as well as an approximation algorithm, where the exact algorithm ExTransparent takes O(n(m + n)(2)(logn + log(m+n))) time and O(n(m+n)(2)) space. On the other hand, the approximation algorithm ApproxTransparent takes O(n(m + n)(logn + log(m + n))) time and O(n(m + n)) space with an approximation factor of O(k), using k-spanners of visibility graph. (C) 2012 Elsevier B.V. All rights reserved.
Effective network coverage and operational life span is key concern of randomly deployed Wireless Sensor Network (WSN) for performing monitoring function in designated region. Intrinsically, WSN consists of resource c...
详细信息
ISBN:
(纸本)9788132204862
Effective network coverage and operational life span is key concern of randomly deployed Wireless Sensor Network (WSN) for performing monitoring function in designated region. Intrinsically, WSN consists of resource constraints sensor nodes. For effective coverage, it is undesirable activating all deployed set of nodes for getting the desired degree of coverage if the same result can be obtained by activating a small subset of deployed nodes for providing the sensing function in the concerned region. We study the problem of extending the life span of the sensor network for fault tolerant area coverage. The proposed genetic algorithm based approach aims to cover a sensed area with minimum number of active nodes and compute the maximum number of Sensing Cover Set (SCS) so that network life time can be prolonged by calculating the working schedule of cover set. Each SCS has been assigned the cover set ID. Each SCS works for the specified amount of time in an alternate fashion. Simulation experiment indicates that genetic algorithm based approach is able to optimally partition the nodes into different SCS.
Evolutionary sensor deployment algorithm using the dual population scheme and the multiple overlap measure (ESDA-DPMO) is proposed to solve the full-coverage problem with non-penetrable obstacles. The full-coverage st...
详细信息
ISBN:
(纸本)1601322178
Evolutionary sensor deployment algorithm using the dual population scheme and the multiple overlap measure (ESDA-DPMO) is proposed to solve the full-coverage problem with non-penetrable obstacles. The full-coverage state group (FCSG) and the non-full-coverage state group (NFCSG) find sensor deployment solutions using different fitness functions, mutation operators and selection operators, respectively. Two distinguished search directions keep genetic diversity of sensor deployment solutions and avoid getting stuck in local optimum. In addition, information change between two is well designed for efficient exploration ability. The proposed multiple overlap measure boosts both evolution of FCSG and NFCSG. In the FCSG, by gathering sensors together as much as possible, there is a high probability of reducing redundant sensor without breaking full-coverage state. In contrast, in the NFCSG, by scattering sensors as much as possible to get lower overlap rate, higher coverage rate is obtained using same number of sensors. We perform simulations on 3 virtual maps to verify the proposed ESDA-DPMO as compared to conventional approaches. The results show that the proposed ESDA-DPMO provides full-coverage solutions efficiently.
Wireless sensor networks are formed by connected sensors that each have the ability to collect, process, and store environmental information as well as communicate with others via inter-sensor wireless communication. ...
详细信息
Wireless sensor networks are formed by connected sensors that each have the ability to collect, process, and store environmental information as well as communicate with others via inter-sensor wireless communication. These characteristics allow wireless sensor networks to be used in a wide range of applications. In many applications, such as environmental monitoring, battlefield surveillance, nuclear, biological, and chemical (NBC) attack detection, and so on, critical areas and common areas must be distinguished adequately, and it is more practical and efficient to monitor critical areas rather than common areas if the sensor field is large, or the available budget cannot provide enough sensors to fully cover the entire sensor field. This provides the motivation for the problem of deploying the minimum sensors on grid points to construct a connected wireless sensor network able to fully cover critical square grids, termed CRITICAL-SQUARE-GRID coverage. In this paper, we propose an approximation algorithm for CRITICAL-SQUARE-GRID coverage. Simulations show that the proposed algorithm provides a good solution for CRITICAL-SQUARE-GRID coverage.
Wireless sensors networks are active area for research and a broad platform for many commercial applications. coverage in a wireless sensor network can be thought of as how well the wireless sensor network is able to ...
详细信息
ISBN:
(纸本)9781457715808;9781457715839
Wireless sensors networks are active area for research and a broad platform for many commercial applications. coverage in a wireless sensor network can be thought of as how well the wireless sensor network is able to monitor a particular field of interest. Ensuring sufficient coverage in a sensor network is essential to obtaining valid data. In this paper coverage strategies are studied which are used in deployment stage. Strategies are categorized into three groups;Force Based, Grid Based and Computational Geometry Based Approach. In this paper Delaunay Triangulation computational geometry coverage strategy is implemented using MATLAB. It is found that Delaunay triangulation coverage strategy is efficient coverage strategy.
This model has the advantage of solving the sensor coverage problems with complex target types. In this paper, we analyze the problem of Clifford connected partial Hybrid-type target coverage where cover sets are allo...
详细信息
ISBN:
(纸本)9783037850992
This model has the advantage of solving the sensor coverage problems with complex target types. In this paper, we analyze the problem of Clifford connected partial Hybrid-type target coverage where cover sets are allowed to monitor a subset of the Hybrid-type targets at any point in time, while Clifford connectivity with the base station is retained. We analyzed the Clifford connection Partial target coverage, and proposed an algorithm- CSNCPCCA on the basis of the Clifford connecting partial Hybrid-type coverage model of Clifford sensor network. At the same time the deployment of the sensor network achieves full coverage and connectivity among working nodes. Finally, we tested and verified the rationality of the model and the algorithm with actual data.
This model has the advantage of solving the sensor coverage problems with complex target types. This paper studied the coverage model when target traversed the network by taking advantage of this network model, and pr...
详细信息
ISBN:
(纸本)9783642226939
This model has the advantage of solving the sensor coverage problems with complex target types. This paper studied the coverage model when target traversed the network by taking advantage of this network model, and proposed the substantive target using Clifford geometric algebra. Experimental results show the practicality and efficiency in searching best traverse gap for specific target by using Clifford geometric algebra.
In this paper, we study the Maximum lifetime Target coverage problem (MTC), which is to maximize the network lifetime while guaranteeing the complete coverage of all the targets. Many centralized algorithms have been ...
详细信息
ISBN:
(纸本)9781424411375
In this paper, we study the Maximum lifetime Target coverage problem (MTC), which is to maximize the network lifetime while guaranteeing the complete coverage of all the targets. Many centralized algorithms have been proposed to solve this problem. A very few distributed versions have also been presented but none of them obtains a good approximation ratio. In this paper, we propose two O(log n) localized algorithms. In particular, we first reduce the MTC problem to the domatic number problem in directed graphs. This relation shows that a feasible solution to the domatic number problem is also a feasible solution to the MTC problem. We next prove the lower and upper bounds of this domatic number, Based on this proof, we present two O(log n)-localized algorithms to solve the MTC problem.
An energy-efficient heuristic mechanism is presented to obtain the optimal solution for the coverage problem in sensor networks. The mechanism can ensure that all targets are fully covered corresponding to their level...
详细信息
An energy-efficient heuristic mechanism is presented to obtain the optimal solution for the coverage problem in sensor networks. The mechanism can ensure that all targets are fully covered corresponding to their levels of importance at minimum cost, and the ant colony optimization algorithm （ACO） is adopted to achieve the above metrics. Based on the novel design of heuristic factors, artificial ants can adaptively detect the energy status and coverage ability of sensor networks via local information. By introducing the evaluation function to global pheromone updating rule, the pheromone trail on the best solution is greatly enhanced, so that the convergence process of the algorithm is speed up. Finally, the optimal solution with a higher coverage- efficiency and a longer lifetime is obtained.
One of the fundamental issues in sensor networks is the coverage problem, which reflect-show well a sensor network is monitored or tracked by sensors. In this paper, we formulate this problem as a decision problem, wh...
详细信息
One of the fundamental issues in sensor networks is the coverage problem, which reflect-show well a sensor network is monitored or tracked by sensors. In this paper, we formulate this problem as a decision problem, whose goal is to determine whether every point in the servicearea of the sensor network is covered by at least α sensors, where ff is a given parameter andthe sensing regions of sensors are modeled by balls (not necessarily of the same radius). This problem in a 2D space is solved in [10] with an efficient polynomial-time algorithm (in termsof the number of sensors). In this paper, we show that tackling this problem in a 3D space is still feasible within polynomial time. Further, the proposed solution can be easily translated intoan efficient polynomial-time distributed protocol. We demonstrate an application of the derived result by proposing an energy-conserving scheduling protocol.
暂无评论