747 sensor network operation-1-187-10

114	PURPOSEFUL MOBILITY AND NAVIGATION
	Sink	Sink
	S2	S
		2
	S1	S
		1
	S4	S4
	S3	S3
	(a)	(b)

Figure 3.9 Generic sensor network with mobile sensors to satisfy different mission requirements.

airport control, home security, military operations, and the like. During network operation, certain sensors fail due to energy depletion or are destroyed by an external force (fire, bomb), creating coverage holes that are not covered by any sensor, as shown in Figure 3.9a. Since there are enough sensors along the perimeter of interest to fulfill the initial mission of the sensor network, that is, perimeter monitoring, no adjustment is necessary at this time. Suppose a target enters the field; the mission of the sensor network is to track the target. Since the track taken by the target may be arbitrary, it is desirable to fill the coverage holes. This can be achieved by using the mobile sensors as shown in Figure 3.9b. As the target approaches, the network also constructs a data dissemination (routing) path from the sensor monitoring the target to the sink. If some other sensor failure creates a network partition, moving S2 can fix the routing problem as shown in Figure 3.9b.

From this example, we can see that mobility may significantly increase the capability of the sensor network by making it resilient to failures, reactive to events, and able to support disparate missions with a common set of sensors. However, there has not been a great deal of work on adding mobility to sensor networks, referred to as mobile sensor networks. A mobile sensor network is different from an ad hoc network. Although both support mobility, mobility in sensor networks may be controllable and, hence, be used to help achieve the network’s missions. That is, mobility may be “purposeful” instead of being treated as an uncontrollable external stimulus to which the ad hoc communication network must respond.

In this section, we propose the following solutions to address purposeful mobility in mobile sensor networks.

Mobility-Assisted Sensing As the mission changes, or to achieve the mission when the network condition (e.g., sensor failure) changes, some mobile sensors must be relocated. The network needs to locate redundant mobile sensors and derive a scenario to move them to the target location considering the computation complexity, movement distance, communication overhead, and the impact of the mobility on other concurrently running missions.

	Mobility-Assisted Data Dissemination (Routing) When sensors move in reaction to an
	event, a mission change, or failure, they may create network partitions, undesirable routes,
	or cause other disruptions. It is a challenge to invoke sensor mobility to improve network
	communications considering issues such as network connectivity, energy consumption
	of both communications and movement, and the network lifetime.

3.3 PURPOSEFUL MOBILITY IN TACTICAL SENSOR NETWORKS

115

	Integrated Mobility Management for Sensing and Routing In addition to moving nodes
	to fulfill the sensing or communication requirements of a single mission, it is essential
	to analyze the impact of mobility on all missions sharing the sensors for sensing or com-
	munication, and it is a challenge to define utility functions that can capture the benefits
	of the movement from the perspective of all missions, and maximize the capability of
	the network.

The rest of this discussion is organized as follows. In Section 3.3.2, we discuss previous work and our solution for mobility-assisted sensing. Section 3.3.3 presents our work on mobility-assisted routing. In Section 3.3.4, we present a problem formulation and the proposed solution for mobility integration. Section 3.3.5 concludes the discussion.

3.3.2 Mobility-Assisted Sensing

In this section, we first give a brief review of the related work on sensor deployment and then present the challenges and the proposed solution on relocating mobile sensors. Finally, we present techniques to find coverage holes, which are used to invoke sensor relocation.

Related Work Since mobility-assisted sensing is still a new area, there is not much work in the literature. The closet work is sensor deployment. Previous work on sensor placement [27–29] largely addressed random and sequential deployment. In a pure random scheme, many more sensors are required than the optimal number to achieve high coverage of a target area. Due to the existence of wind and obstacles, some areas may never be covered no matter how many sensors are dropped. Moreover, during in-building toxic leaks [30], chemical sensors must be placed inside a building from the outside. In these scenarios, it is necessary to make use of mobile sensors [31, 32], which can move to the correct places to provide the required coverage. Based on the work from [33], mobile sensors have already been a reality. Their mobile sensor prototype, called Robomote, is smaller than 0.000047 m3 at a cost of less than $150 in parts. Robomote also has some capability of avoiding obstacles when moved to the designated location.

There have been some research efforts on deploying mobile sensors, but most of them are based on centralized approaches. The work in [34] assumes that a powerful cluster head is able to know the current location and determine the target location of the mobile sensors. However, such a central server may not be available in most cases, and this approach suffers from a single point failure problem. Sensor deployment has also been addressed in the field of robotics [30], where sensors are deployed one by one, utilizing the location information obtained from the previous deployment. This method has strong assumptions on the initial sensor placement in order to guarantee the communication between the deployed and undeployed sensors, and it does not work in case of network partition. Since sensors are deployed one by one, the long deployment time can significantly increase the network initialization time.

In our previous work [31], assuming that all sensors are mobile, we proposed three distributed algorithms for controlling the movement of sensors that are initially randomly placed to get high coverage. The algorithms use Voronoi diagrams to detect coverage holes. In one algorithm, VOR, sensors migrate toward holes. In the second, VEC, sensors move away from each other to achieve a uniform distribution. In the third, minimax, sensors move toward their local center. Although mobile sensors can be used to improve the sensing coverage, their costs may be high. To achieve a good balance between sensor cost and sensor

116 PURPOSEFUL MOBILITY AND NAVIGATION

coverage, we proposed a bidding protocol [32] to assist the movement of mobile sensors when a mix of mobile and static sensors are used. In this protocol, mobile sensors act as the hole healing server, the base price of whose service is the size of the hole generated if they leave. Static sensors detect coverage holes and bid mobile sensor based on the hole size. Mobile sensors accept the highest bid and move to heal the hole if the bid is larger than its base price. In this way, mobile sensors always move to heal the largest holes and increase the coverage.

Challenges of Sensor Relocation The motion capability of sensor nodes can also be used for purposes other than sensor deployment. For example, in case of a sensor failure or node malfunction, other sensors can move to replace the role of the failed node. As an event (i.e., fire, chemical spill, incoming target) occurs, more sensors should relocate to the area of the event to achieve a better coverage. Compared with sensor deployment, sensor relocation, which relocates mobile sensors from one place to another place, has many challenges. First, sensor relocation has strict time constraints. Sensor deployment is done before the network is in use, but sensor relocation is on demand and should be finished in a short time. For example, if the sensor monitoring a security-sensitive area dies, another sensor should take the responsibility as soon as possible; otherwise, some security policy may be violated. Second, relocation should not affect other missions currently supported by the sensor network, which means that the relocation should minimize its effect on the current topology. Finally, since physical movement costs much more energy than computation and communication, the moving sensor may suffer. As some nodes die due to low battery power, other nodes need to move again and cost more power. To be fair to each sensor and to prolong the network lifetime, it is important to balance the trade-offs between minimizing the total energy consumption and maximizing the minimum remaining energy of the mobile sensors. Sensor relocation has been mentioned in [35], which focuses on finding the target locations of the mobile sensors based on their current locations and the locations of the sensed events. However, they did not address the challenges of finding the relocation path under time, topology, and energy constraints.

Due to these new challenges, our deployment protocols [31,32] cannot be directly applied for sensor relocation. For example, if the area covered by a failed sensor does not have redundant sensors, moving neighbor sensors may create new holes in that area. To heal these new holes, more sensors need to be involved. This process continues until some area having redundant sensors is reached. During this process, sensors may move back and forth and waste lots of energy. Based on this observation, we propose to first find the location of the redundant sensors and then design an efficient relocation schedule for them to move to the target area (destination).

Finding the Redundant Sensors Using flooding to find the redundant sensors may significantly increase the message overhead. Techniques based on publisher/subscriber [36] are designed for distributed systems or wired networks and may not be applied to sensor networks due to high overhead. To reduce the message overhead, solutions similar to Twotier data dissemination (TTDD) [37] can be used. In TTDD, the target field is divided into grids, and each has a grid head. The grid head is responsible for disseminating the sensing data to other grid heads. To find the interested data, the sink floods the query, which will be served by the grid head that has the sensing data. Since the data needs to be flooded to the whole network, although only grid heads, it still has significant overhead.

3.3 PURPOSEFUL MOBILITY IN TACTICAL SENSOR NETWORKS					117
(0,4)	(1,4)	(2,4)	(3,4)	(4,4)
(0,3)	(1,3)	(2,3)	(3,3)	(4,3)
(0,2)	(1,2)	(2,2)	(3,2)	(4,2)
(0,1)	(1,1)	(2,1)	(3,1)	(4,1)
(0,0)	(1,0)	(2,0)	(3,0)	(4,0)
Figure 3.10		System model.

We apply the quorum concept [38–40] to reduce the message overhead. A quorum is a set of grids, and any two quorums must have an intersection grid. If the grid with redundant sensors advertises to sensors in its quorum, any destination grid head can obtain this information by sending a request to the sensors in its quorum. A simple quorum can be constructed by choosing the grids in a row and a column. Suppose N is the number of grids

in the network. By using this quorum-based system, the message overhead can be reduced

√

from O(N ) to O( N ) [38].

By organizing grids as quorums, each advertisement and each request can be sent to a quorum of grids. Due to the intersection property of quorums, there must be a grid that is the intersection of the advertisement and the request. The grid head will be able to match the request to the advertisement. A simple quorum can be constructed by choosing the nodes in a row and a column. Instead of flooding the network with advertisements or requests, the request and the advertisement are only sent to nodes in a row or column. For example, as shown in Figure 3.10, suppose grid (0,3) has redundant sensors, it only sends the advertisement to grids in a row [(0,3), (1,3), (2,3), (3,3), (4,3)] and a column [(0,4), (0,3), (0,2), (0,1), (0,0)]. When grid (3,0) is looking for redundant sensors, it only needs to send a request to grids in a row [(0,0), (1,0), (2,0), (3,0), (4,0)] and a column [(3,4), (3,3), (3,2), (3,1), (3,0)]. The intersection node (0,0) will be able to match the request to

the advertisement. Suppose N is the number of grids in the network. By using this quorum-

√

based system, the message overhead can be reduced from O(N ) to O( N ). Although the message overhead is very low compared to flooding, we can further reduce the message overhead by observing the specialty of our problem.

We can further reduce the message complexity by using the geographic information in sensor networks. For example, we can specify that an advertisement must be sent to grids in one column (advertisement quorum), and a request must be sent to grids in one row (request quorum). Since there is always an intersection grid between any column and row, the grid head of that intersection grid will be able to match the request to the advertisement. Still using the example of Figure 3.10, grids (0,4), (1,4), (0,3), and (1,3) have redundant sensors, while grid (3,0) needs more sensors. The grid head of (1,3) propagates its redundant sensor information through its supply quorum [(1,4), (1,3), (1,2), (1,1), (1,0)]. The grid head in