|
Network design tool The optimal deployment is currently one of the most important research issues of wireless sensor networks (WSNs). Usually the sensor nodes in the sensor network can be deployed in the following ways: the random placement, the manual predicted placement or a mixture of the two means. When the targeted location is inaccessible, random placement is the only choice. For such cases sensors may be thrown from aircrafts. However, if the terrain properties can be predetermined and be accessible, the deployment of a sensor network may be planned carefully and the quality of service will be much improved as a consequence. For a certain application, the optimal strategy of sensor placement mainly depends on the particular requirements from end users. For example, if the network system is to be used for environmental monitoring, it is possible to only select a few ¡°virtual points¡± which may reflect the whole circumstances of this area and cover these ¡°virtual points¡± by sensor nodes. An example of this kind of deployment is shown as in the figure below. In a surveillance application, however, there may exist some important points which are essential to identify event occurrence and those points can be predefined and must be covered by sensor nodes. We define these important points as critical points (CP points), the CP grid coverage as covering these CP points. In many practical applications, we only need to cover the predefined CP points whilst a complete coverage of the whole area is not necessary. Hence in this work, we intend to concentrate to investigate the optimal design rule of this CP coverage issue.  Given the properties of the terrain predetermined, the field can be generally divided into grids and sensors which can be selectively deployed on these grid points. This approach is called grid-based placement. Here the grids generation is determined according to the field characteristic which is not the same as the CP points whose generation is determined according to the application characteristic. A key challenge of the grid-based sensor placement is how to determine each sensor¡¯s grid position in the field to cover all predefined CP points with minimal amount of sensor nodes. Approach Ant-inspired algorithm was first proposed by Dorigo and his colleagues as a multi-agent approach to those difficult combinatorial optimization problems like the traveling salesman problem (TSP) and the quadratic assignment problem (QAP). There are currently a lot of on-going activities in the scientific community to extend/apply ant-based algorithms to solve many different discrete optimization problems. Recent applications cover those problems like vehicle routing, sequential ordering, graph coloring, routing in communications networks, and so on. In this work, we study an ant-inspired algorithm, namely Ant Colony Optimization, as the basis for an optimal sensor placement in a grid based sensing field. Here all candidate grids are treated as the possible grids on which an ant can place a sensor. If a ant moves to a grid, this ant must place a sensor on this grid. All ants in this algorithm must initially be randomly positioned on the candidate grids within the sink node's communication range and place the first sensor on this initial grid. As shown in the figure below, all the initial placed sensors are within the circular area and can be connected to the sink node.  Here R is the communication radius of the sink node and it is set to be the same as RS and RC for legible read. In this algorithm, every ant will generate a sensor placement solution independently, and they communicate with each other by pheromone other ants left. Through this colony cooperation, an optimization solution may be generated. Because all the sensing data need to be delivered to the sink node, the connectivity problem must be considered during the process of grid selection. Here we restrict that all ants must select the grids which can be communicated with the grids having been selected by the same ant, as shown in figure below:  For example, three sensors named 1, 2, and 3 are placed in the sequence as their names. Firstly, sensor 1 is placed on the grid which can be communicated with the sink node; secondly, sensor 2 was placed on the grid which is selected among all grids within the communication range of either sink or sensor 1. As shown in the figure above, we select position 2 and place a sensor named 2. In this way, it is guaranteed that all placed sensors are connected to sink either directly or through other sensor nodes. The sensor placement procedure continues until all CP points are covered. All ants follow this procedure to build their placement solution. When algorithm ends, the output gives the best ant selected placement scheme. Systems/Experiments Based on all the our above efforts, we provide the sensor deployment platform named EasiDesign . The most significant contribution of Easidesign is that it fully considers the effectiveness of different sink position, which guarantees the connectivity to sink node when we place any sensor nodes. Extensive simulations and experiments indicated that both EasiDesign and its parameters choosing policy are valid. The output or running results of our Easidesign are showed in the figures below.
Accomplishments Wei Liu, Li Cui. An Ant Based Approach to the Optimal Deployment in Wireless Sensor Networks. Submitted to the 2nd chinese conference of wireless sensor networks (CWSN2008) Future Directions It is a new attempt to employ the ant-based algorithm to solve the sensor network deployment problem is and some other interesting issues will be studied further in our future works, For example, a QoS supported sensor placement design, a fault tolerant design rather than mainly pursuing a minimal number of sensors and so on. |
¾©ICP±¸:08012583