Britton Quist and Dr. Lee Swindlehurst, Electrical and Computer Engineering

Sensor deployment and placement has a myriad of applications. In everything from wildlife monitoring to underwater microphone surveillance to UAV (unmanned air vehicle) battlefield surveillance the placement of sensors is essential for proper coverage. Often these devices (nodes) communicate as an Ad-Hoc network where data sent to a distant sensor or node will be conveyed across the network by the nodes along the way. In this way, if a node is within the communication range of a single node with other connections, it can communicate with an entire network. This approach is an alternative to the network used in applications like cell phones where the only link of importance is being able to communicate with a base station.

The Ad-Hoc network lends itself well to remote sensors because these devices often have power constraints. Since the sensors are almost always in remote locations, the less energy required for communicating the better. At the same time, it is important that sensors detect as large an area as possible. This necessitates a tradeoff between area covered by a sensor network and the proximity of the nodes to each other within the network. Maximizing one minimizes the other. The image to the left shows a network diagram with dots representing nodes and lines representing connections.

There are two patterns or lattices that are used for node placement: the square and hexagonal lattice (the hexagonal lattice is pictured to the right.) In an ideal placement of nodes, all of the nodes are close enough to communicate with the nodes around them but far enough to be covering as much area as possible.

In practice, the placement of nodes is never exactly where planned. Sensors can be dropped from an airplane or start from a single location. In such instances, sensors that can move themselves in a coordinated algorithm can achieve the best performance. Two proposed algorithms are Virtual Force algorithm (VFA) and the VFSec . The research I performed was centered on improving these algorithms.

In order to determine the effectiveness of an algorithm, certain performance metrics have been proposed1. The overall performance of a network is calculated by adding the average number of connections per node to the coverage efficiency.

Like the two previous algorithms, a virtual force is applied to each node to direct its movement. The equation is as follows:

After all of the forces described by the above equation are calculated, the nodes are repositioned accordingly. This equation is an extension of the VFSec but performs substantially better under certain conditions. Under conditions where node density is low, the improvement in performance is as much as 18%. A chart comparing the performance of the algorithms appears below.

One specific benefit to the VFSec and the proposed algorithms is that if the calculating of the forces is done locally, only nodes that can be directly communicated with need to be considered by a given node. This is opposed to the VFA algorithm that required the location of nodes that are out of direct communication range to calculate the virtual force. In comparing the various performance metrics such as secure connections per node and effective coverage, it becomes apparent that there is no universal winner. This is the case with any sort of tradeoff-dependent performance: for example, the algorithm proposed here maximizes coverage at low node density but maximizes connectivity when nodes are closer together.

The faculty mentor that had planned on helping me with the research left the university about a month after the grant was awarded. Having already accepted the grant, I was encouraged by my mentor at the time, Dr. Petrie, to find a new professor to mentor me. I asked Dr. Swindlehurst who pointed me toward an equally interesting topic in his area of expertise. Having to switch professors meant having to start over and spend more time getting started. Despite this setback, I was able to learn a lot about research while developing the algorithm proposed in this report. It has strengthened my resolve to become a professor and research professionally.

References

• Y. Zao and K. Chakrabarty, “Sensor Deployment and Target Localization Based on Virtual Forces,” in Proc of 2004 IEEE INFOCOM, pp1293-1303, Apr. 2003.
• Y. Mao and M. Wu, “Coordinated Sensor Deployment for Improving Secure Communications and Sensing Coverage” in ACM Workshop on Security of Ad Hoc and Sensor Networks SASN ’2005, pp 117-128, Nov. 2005