Energy-Efficient Scheduling for Mobile Sensors Using Connection Graphs in a Hybrid Wireless Sensor Network with Obstacles

Abstract

This paper considers the scheduling problem of mobile sensors in a hybrid wireless sensor network (WSN) with obstacles. In a WSN, static sensors monitor the environment and report where events appear in the sensing field. Then, mobile sensors are dispatched to these event locations to perform in-depth analysis. The sensing field may contain obstacles of any shape and size. A big challenge is how to efficiently dispatch the mobile sensor to find an obstacle-avoiding shortest path. To remedy this issue, we propose an efficient scheduling mechanism based on connection graphs in this paper. Specifically, the region of network is divided into grid cells with the same size. Consequently, the search space of the shortest path is restricted to the connection graphs composed of some grid cells. Through simulation, we verify the effectiveness of our method. The paper contributes to developing an energy-efficient dispatch solution in the presence of obstacles.

1. Introduction

Recent advances in microelectronics technology, computer technology, and wireless communication technology have led to the development of low-cost and low-power sensor nodes that are small in size. Sensor nodes have the ability to sense the nearby environment and perform simple computations and communication within a small region. Wireless sensor networks (WSNs) composed of these sensor nodes are becoming a hot research topic in the recent decade and have been applied in many applications including environmental monitoring, health monitoring, vehicle tracking system, military surveillance, earthquake observation, and many others [1–8]. With the advancement of embedded computing and wireless communication techniques, sensors can move around when installing sensing devices on mobile equipment. By incorporating mobile sensors to WSNs, the network capability can be further improved in many aspects, such as automatic sensor deployment, dynamic event coverage, mobile target tracking, flexible topology adjustment, and efficient data collection and processing. Mobile sensors are typically resource-rich devices with more energy, higher communication power, and more powerful sensing and computing capabilities. A hybrid wireless sensor network (WSN) consists of both static sensor and mobile sensor nodes. Static sensors monitor the environment and report where events appear in the sensing field. Then, mobile sensors are dispatched to these event locations to perform in-depth analysis [9, 10]. Therefore, mobile sensors collaborate for fulfilling high-level requirements. In this context, the efficient scheduling for mobile sensors while prolonging the lifetime of the network as long as possible is one of the major challenges. With the progress of energy harvesting technology, the lifetime of static sensors is assumed long enough. The lifetime of network is defined as the time until the first mobile sensor depletes its energy. In this paper, we focus on the energy-efficient scheduling for mobile sensors to find an obstacle-avoiding shortest path.

The scheduling for mobile sensors is one of the most important issues in hybrid WSNs, and it has received extensive research efforts in different areas of hybrid WSNs. Several techniques have been proposed for addressing this problem from different perspectives. For instance in [11], the authors argue that no static sensors are deployed to collect sensing data. Therefore, mobile sensors are dispatched to patrol the monitored region for collecting sensing data. Patrolling routes for every mobile sensor are arranged almost the same in length for ensuring the load balance of mobile sensors. In [12, 13], the network is composed of static sensors and mobile sensors, where static sensors are used for sensing data while mobile sensors can move to event locations to conduct more in-depth analysis. The author addresses how to dispatch mobile sensors to the event locations in an energy-balanced way, where dispatch problem is considered for a single round. Besides, the authors have studied the mobile sensors schedule problem in centralized and distributed situations. However, they do not consider coverage performance of the network. In [14, 15], mobile sensors are equipped with the ability to analyze multiple attributes of events. They can move to event locations to conduct more in-depth analysis. A two-phase heuristic is developed for assigning mobile sensors to event locations while extending the system lifetime. However, most mobile sensors generally have similar capabilities in most cases. The author discusses the assignment topics in wireless sensor and robot network in [16]. A big challenge is how to assign the most appropriate robot for fulfilling each task when multiple tasks happen simultaneously. However, the authors do not give a reasonable solution to remedy this problem. In [17], the author addresses multiactuator control issue in wireless sensor and actuator networks. When a very large region is to be monitored, it is almost important for static sensors to cover the whole region. In this case, actuators are used to mitigate this issue for improving the area coverage and target detection and so forth. The workload of actuators is computed dynamically according to the partition result of Voronoi diagram. Once an imbalance is detected, actuators are moved for achieving a balanced load distribution. However, Voronoi diagrams are somewhat irregular, and thus the partition may not be optimal when path traversing cost is unneglectable. References [18, 19] address the scheduling problem of mobile sensors in the sensing field with obstacles. The authors present a method to find a shortest and collision-free path for a mobile sensor. However, the authors do not give a specific implementation method. To summarize, there has been a lot of research on the dispatch of mobile sensors, and many achievements have been made. However, as argued above, how to schedule mobile sensors efficiently while prolonging the network lifetime is still a challenge.

The research goal of this paper is to efficiently dispatch mobile sensors to find an obstacle-avoiding shortest path. The sensing region is assumed to be covered by static sensors and has no holes. Static sensors sense their newly generated data, and these data are assumed to be delay-tolerant for applications. To achieve the goal, we propose a technique which includes the following three steps.

(1) Region Division to Grid Cells. The sensing region is divided into grid cells. These grid cells are the same in size but may contain a different number of static sensors. The size of each grid cell is in proportion to the communication radius of sensors. Grid cells are the basic unit for mobile sensors to collect data sensed by static sensors. In order to make mobile sensors movement with minimal energy consumption, there is one sink position to be identified in each grid cell such that a mobile sensor moves to the sink position for collecting data sensed by static sensors. Since each grid cell is a square in this paper, the sink position is the geometric center of the grid cell. Static sensors are responsible for reporting where suspicious events appear in grid cells. Mobile sensors then move to these grid cells to conduct in-depth analysis. Except for the location of obstacles, mobile sensors can move to the sink position in each grid cell.

(2) Obstacles Shape Regularization. In fact, the sensing field may contain obstacles of any shape and size. How to efficiently dispatch mobile sensors to find an obstacle-avoiding shortest path is a big challenge. When the sensing region is divided into grid cells, obstacles will contain some grid cells. The edges of obstacles intersect grid cells and may occupy part of some grid cells. Once obstacles occupy part of one grid cell, then the grid cell is regarded as obstacles. Therefore, we obtain regularization shape of obstacles so that scheduling for mobile sensors becomes easier. Mobile sensors have a large data communication radius. Hence, static sensors are located in the grid cells regarded as obstacles and their sensing data can be collected by mobile sensors. Taking into account the complexity of the system, this paper just considers the one-to-one shortest path problem; that is, a single mobile sensor is dispatched to a single event location.

(3) Connection Graphs Application. Considering the existence of obstacles, our goal is to find an obstacle-avoiding shortest path from the mobile sensor current position (called source grid cell) to event location position (called target grid cell) by an efficient method. It is obvious that the shape of obstacles becomes a polygon after regularization. We define the set Lp of all maximal line segments that cross boundaries of the polygon in grid cells. On the other hand, let Ls be the set of all maximal line segments that include the source grid cell and Lt the set of all maximal line segments that include the target grid cell. Note that here all these line segments are horizontal or vertical. The connection graph Gc is the intersections of the line segments in set $L=\text{Lp}\cup \text{Ls}\cup \text{Lt}$ , which certainly contains a shortest path from source grid cell to target grid cell, according to Manhattan distance. With the search space of the mobile sensor from all grid cells to the connection graph Gc, the scheduling for mobile sensor will become more efficient.

The rest of the paper is organized as follows. We introduce the network model in Section 2. Section 3 presents our network division strategy. In Section 4, we propose an approach to finding an obstacle-avoiding shortest path using connection graphs. Section 5 presents the evaluation of our technique. We present related work in Section 6. Finally, Section 7 concludes the paper.

2. Preliminary

Hybrid WSNs, which consist of mobile sensors and static sensors, have received intensive research interest in recent years. Static sensors form a backbone network to sense environment data. Mobile sensors have more powerful sensing and computing capabilities, and they can move to target locations to carry on missions such as replacing broken nodes or analyzing suspicious events. By incorporating mobile sensors to WSNs, the network capability can be further improved in many aspects. Static sensors may be deployed unevenly in the network region. Region coverage is one of the most important problems for WSNs. Without loss of generality, we assume in this paper that no hole exists in the hybrid WSN and static sensors are the same in their capabilities. In practical environment, the sensing field may contain obstacles of any shape and size. A big challenge is how to efficiently dispatch mobile sensors to finding an obstacle-avoiding shortest path. With the mechanisms of duty-cycle and energy harvesting, the lifetime of static sensors is assumed long enough. Therefore, the lifetime of the hybrid network is determined by the lifetime of mobile sensors.

In this paper, we propose an efficient scheduling technique of the mobile sensor in the presence of obstacles, which aims to prolong the lifetime of the hybrid WSN as long as possible. Taking into account the complexity of the system, we only consider the one-to-one shortest path problem. That is, we only consider that a single mobile sensor is dispatched to a single event location.

We present a network model as the example used in this paper. In Figure 1, static sensors are deployed unevenly in the network, denoted by black dots. A solid triangle and a white triangle represent the source location s and the target location t, respectively. The start position of the mobile sensor is located in the source location s, while the target location t shows the destination location that the mobile sensor will move to. There are two black irregular figures, which represent obstacles.

Figure 1

An example of scheduling for a mobile sensor with obstacles.

We will present a grid-based technique by which the sensing field is divided into grid cells in the next section.

3. Dividing Network Region into Grid Cells

In order to facilitate the dispatch of the mobile sensor in Figure 1, we will divide network region into grid cells. In fact, grid-based techniques have been widely used for the analysis of WSNs [20–23]. These grid cells are the same in size, and their shape is a square. Static sensors, which are responsible for monitoring environment, are deployed unevenly in each grid cell. We assume that each grid cell has no hole and its side length is equal to gSide in Figure 2. In this paper, there is one position (called sink position) in each grid cell such that the mobile sensor can collect environment variables of all static sensors in this grid cell when staying at this position. The sink position is located in the geometric center of each grid cell.

Figure 2

Side length of grid cell gSide and the data communication radius r.

In Figure 2, red circle and black circle represent sink position and static sensors, respectively. We assume that the data communication radius of the mobile sensor is equal to R, and R is greater than r in this paper. Therefore, when the mobile sensor stays at sink position, it can collect sensing data of all static sensors. In order to facilitate scheduling for the mobile sensor in the presence of obstacles, we assume that its movement direction can only be horizontal or vertical and its minimal movement distance is equal to one unit distance. We set the gSide as one unit distance in this paper.

Figure 3 shows grid division of monitored region in Figure 1. Obviously, two obstacles contain some grid cells and their edges intersect grid cells. Once obstacles occupy part of one grid cell, the grid cell is regarded as obstacles in this paper. Figure 3 obtains two regularization shapes of the obstacles. Red circles represent sink positions of each grid cell. Next we present method based on connection graphs for scheduling for the mobile sensor.

Figure 3

The grid graph G of monitored region.

4. Using Connection Graphs to Find an Obstacle-Avoiding Shortest Path

Once the target location is identified, the mobile sensor should move to the target location and should not collide with any obstacles in the network. Finding a shortest path for mobile sensors is an important research topic in hybrid WSNs with obstacles. Several studies have addressed this issue [24–26]. We propose a modified approach of these literatures. In Figure 3, given the source node s and the target node t, we denote the Manhattan distance between s and t by $M(s,t)$ . Note that here a node is equivalent to a grid cell. Obviously, when there is no obstacle, the distance which the mobile sensor will move from the source node s to the target node t is equal to $M(s,t)$ . In fact, the sensing field usually contains obstacles of any shape and size, like Figure 1. Let D be an obstacle-avoiding path from s to t; the detour number $d(D)$ is defined as the total number of nodes on D that are directed away from t. Hence, the length of D is equal to $M(s,t)+2d(D)$ . Obviously, D is a shortest path if and only if $d(D)$ is minimized among all paths connecting s and t.

According to the source node s and the target node t in Figure 3, the Manhattan distance of the mobile sensor movement is a determined value. Therefore, an obstacle-avoiding shortest path of the mobile sensor is decided by the detour number. Next, we generalize the concept of detour number. If a direction is assigned to an edge $(u,v)$ , the direction will be from u to v. Without loss of generality, we assume that the direction from u to v is represented by $u\to v$ . In this paper, we define the detour length of $u\to v$ in regard to a target node t, denoted by $dl(u\to v)$ . l is assumed to be the line passing through t and perpendicular to $u\to v$ .

Figure 4 shows that the detour length of $u\to v$ in regard to the target node t is different in all circumstances. Red circles represent sink positions of each grid cell and l is perpendicular to $u\to v$ . w is the intersection of line segment $(u,v)$ and line segment l. Obviously, formula of the detour length $dl(u\to v)$ is as follows:

$$\begin{array}{l}dl(u⟶v)\\ =\{\begin{array}{ll}0,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}u\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and}\mathrm{\hspace{0.17em}\hspace{0.17em}}v\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{are}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{on}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{the}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{same}\hfill \\ \hfill & \text{side}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{of}\mathrm{\hspace{0.17em}\hspace{0.17em}}l\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and}\mathrm{\hspace{0.17em}\hspace{0.17em}}u\hfill \\ \hfill & \text{is}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{further}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{from}\mathrm{\hspace{0.17em}\hspace{0.17em}}l\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{than}\mathrm{\hspace{0.17em}\hspace{0.17em}}v;\hfill \\ \text{the}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{length}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{of}\mathrm{\hspace{0.17em}\hspace{0.17em}}u⟶v\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}u\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and}\mathrm{\hspace{0.17em}\hspace{0.17em}}v\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{are}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{on}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{the}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{same}\hfill \\ \hfill & \text{side}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{of}\mathrm{\hspace{0.17em}\hspace{0.17em}}l\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and}\mathrm{\hspace{0.17em}\hspace{0.17em}}u\hfill \\ \hfill & \text{is}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{closer}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\mathrm{\hspace{0.17em}\hspace{0.17em}}l\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{than}\mathrm{\hspace{0.17em}\hspace{0.17em}}v;\hfill \\ \text{the}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{length}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{of}\mathrm{\hspace{0.17em}\hspace{0.17em}}w⟶v,\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}l\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{intersects}\mathrm{\hspace{0.17em}\hspace{0.17em}}u⟶v\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{at}\mathrm{\hspace{0.17em}\hspace{0.17em}}w.\hfill \end{array}\end{array}$$

(1)

Figure 4

The detour length from node u to node v.

Lee's algorithm [27], which is a breadth-first search algorithm, is widely used to find a shortest path in the presence of obstacles. To increase the chance of reaching the target node quickly, a guided depth-first search feature is incorporated into the search process in [26]. In this paper, we use connection graphs to find an obstacle-avoiding shortest path. We define the set Lp of all maximal line segments that cross boundaries of polygon in grid cells. Let Ls be the set of all maximal line segments that include source grid cell and Lt the set of all maximal line segments that include target grid cell. Note that here all these line segments are horizontal or vertical. The connection graph Gc is the intersections of the line segments in set $L=\text{Lp}\cup \text{Ls}\cup \text{Lt}$ , which certainly contains an obstacle-avoiding shortest path from source grid cell to target grid cell, according to Manhattan distance. By this method for processing the grid graph G in Figure 3, we obtain the connection graph Gc in Figure 5.

Figure 5

The connection graph Gc of grid division.

With the search space of the mobile sensor from the grid graph G to the connection graph Gc, our algorithm makes it more efficient to schedule for the mobile sensor.

As presented in Algorithm 1, we define the function ShortestPath for the mobile sensor to find an obstacle-avoiding shortest path. Note that here the node is equivalent to the grid cell. We define length $(u,v)$ that denotes the length of the edge connecting two adjacent nodes u and v in Gc. Once we replace $dl(u\to v)$ with length $(u,v)$ , then Algorithm 1 is essentially similar to Dijkstra's algorithm. Because of the correctness of Dijkstra's algorithm, we conclude that Algorithm 1 can correctly compute an obstacle-avoiding shortest path from s to t in Gc. ALTERNATIVES and PATHWAY are two subsets of nodes of Gc. Initially, PATHWAY is initialized to empty set, and eventually it is the set of nodes which constitute the shortest path from s to t. Firstly, the variances in Algorithm 1 are initialized (lines 1–9). A one-dimensional array $\text{DL}[u]$ , which associates with each node u, contains an upper bound of the detour length $\delta (t)$ of u computed during the execution of the algorithm. Furthermore, each node u has another field PRIOR[u], which links node u to its predecessor in a path from s to t. Once the algorithm terminates, the chain of predecessors starting from node t runs backward along a shortest path from s to t. Finally, lines 10 to 25 are to implement the search process of algorithm. A node u in ALTERNATIVES, which has the smallest DL value, is selected for grid expansion.

Algorithm 1: ShortestPath.

Require:

  ALTERNATIVES: the subset of nodes of Gc, where nodes of Gc represent grid cells

Ensure:

  PATHWAY: the subset of nodes of Gc, which constitute a shortest path from s to t

(1) begin

(2) PATHWAY $\leftarrow \mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{\Phi }$ ;

(3)  $\text{DL}[s]\leftarrow \mathit{0}$ ;

(4) PATHWAY ← PATHWAY $\cup \hspace{0.17em}\hspace{0.17em}\{s\}$ ;

(5) for each adjacent u of s in Gc do

(6)     $\text{DL}[u]\leftarrow \text{dl}(s\to u)$ ;

(7)    PRIOR $[u]\leftarrow s$ ;

(8)    ALTERNATIVES ← ALTERNATIVES $\cup \hspace{0.17em}\hspace{0.17em}\{u\}$ ;

(9) end  for

(10)  while ( $u\leftarrow$ deletemin(ALTERNATIVES) $!=t$ ) do

(11)   PATHWAY ← PATHWAY $\cup \hspace{0.17em}\hspace{0.17em}\{u\}$ ;

(12)    $d\leftarrow \text{DL}[u]$ ;

(13)   if  u has a adjacent v in Gc such that $\text{dl}(u\to v)=\mathit{0}$ and v ∉ PATHWAY then

(14)     UpDate(ALTERNATIVES, u, v, d);

(15)      for each such adjacent v of u  do

(16)        dir ← direction of $u\to v$ ;

(17)        GoForward(u, dir, d);

(18)      end  for

(19)      else

(20)     for each adjacent v of u in Gc such that v ∉ PATHWAY do

(21)        UpDate(ALTERNATIVES, u, v, $\text{DL}[u]+\text{dl}(u\to v))$ ;

(22)     end  for

(23)    end  if

(24)  end  while

(25) end

The function UpDate is presented in Algorithm 2, which aims to perform ALTERNATIVES update operations to ensure that nodes are in ALTERNATIVES with their current smallest DL values.

Algorithm 2: UpDate.

Require:

  ALTERNATIVES, u, v, dl: parameters generated by Algorithm 1

Ensure:

  Ensure that all adjacent nodes of u are in ALTERNATIVES with their current smallest DL value

(1) begin

(2) if  v ∈ ALTERNATIVES and dl < DL $[v]$   then

(3)   delete(ALTERNATIVES, v);

(4) end  if

(5)  $\text{DL}[v]\leftarrow \text{dl}$ ;

(6) PRIOR $[v]\leftarrow u$ ;

(7) ALTERNATIVES ← ALTERNATIVES $\cup \hspace{0.17em}\hspace{0.17em}\{v\}$ ;

(8) end

The function GoForward in Algorithm 3 ensures that the direction of search process will not be changed, which increases the chance of reaching the target node quickly.

Algorithm 3: GoForward.

Require:

  u: a node which lies between the source node s and the target node t

  dir: direction of movement

  d: the length of movement

Ensure:

  A guided depth-first search feature is incorporated into the search process

(1) begin

(2) new $\text{dl}\leftarrow d$ ;

(3) while newdl = d and u has a neigboring node v in Gc such that the

(4)     direction of $u\to v=\text{dir}$ and v ∉ PATHWAY do

(5)   new $\text{dl}\leftarrow \text{DL}[u]+\text{dl}(u\to v)$ ;

(6)   UpDate(ALTERNATIVES, u, v, newdl);

(7)   if new $\text{dl}=d$   then

(8)      $\text{DL}[v]\leftarrow d$ ;

(9)     PRIOR $[v]\leftarrow u$ ;

(10)      PATHWAY ← PATHWAY $\cup \hspace{0.17em}\hspace{0.17em}\{v\}$ ;

(11)       if   $v=t$   then  stop;

(12)   end  if

(13)    $u\leftarrow v$ ;

(14)  end  while

(15) end

5. Evaluation

This section introduces the implementation of our approach. The prototype has been implemented in Matlab program and experiments have been conducted for evaluating the technique proposed previously. Below we introduce the experiment settings and the results of evaluation.

5.1. Experiment Settings

In this paper, a hybrid WSN is composed of a mobile sensor and many static sensors, and it contains two obstacles. Figure 1 shows an example of scheduling for a mobile sensor with two obstacles. The number of static sensors is enough so that no hole exists. These static sensors are deployed in a region of 20 × 15 unit space. We set gSide = 1 unit and the hybrid WSN is divided into 20 × 15 = 300 grid cells. In order to facilitate scheduling for the mobile sensor in the presence of obstacles, we assume that its movement direction can only be horizontal or vertical and its minimal movement distance is equal to one unit distance. The experiments are conducted on a laptop with Intel i5-2400 M processor, 4 GB memory, and 32-bit Windows 7 system.

5.2. Evaluation Results

To evaluate the performances of our proposed algorithms, we have developed a simulator in Matlab. Figure 6 shows the movement path and search space of the mobile sensor in the grid graph G. The search space contains 104 grid cells whose faces are labeled by a black circle and a white circle. From the source node s to the target node t, the movement distance of the mobile sensor is equal to 23 units. These grid cells, whose faces are labeled by a black circle, represent the shortest path that the mobile sensor will pass through.

Figure 6

Expanded nodes of the grid graph G.

The difference between Figures 6 and 7 is that Figure 7 gives the dispatch of the mobile sensor in the connection graph Gc. In Figure 7, the search space of the mobile sensor has 52 grid cells, but the movement distance of the mobile sensor is the same. Compared with the search space in Figure 6, the search space in Figure 7 is reduced by half, but the movement distance of the mobile sensor is the same. According to Manhattan distance, the movement distance of the mobile sensor is an obstacle-avoiding shortest path. Table 1 shows that the program run time of the connection graph Gc is less than that of the grid graph G.

Table 1

Program run time of two graphs.

	Run time (s)
The grid graph G	0.1118
The connection graph Gc	0.0558

Figure 7

Expanded nodes of the connection graph Gc.

We have analyzed these experiments in search space and program run time. According to these experiments, the scheduling for the mobile sensor in the connection graph Gc is more efficient than that in the grid graph G. By method based on connection graphs, we can quickly find an obstacle-avoiding shortest path. In addition, this also indicates that our technique is feasible for scheduling for the mobile sensor.

6. Related Work

The dispatch of mobile sensors is one of the most important issues in hybrid WSNs, and it has received extensive research efforts in recent years. Mobility is considered as a means of relieving the traffic burden and enhancing energy efficiency in hybrid WSNs. Then, we study the relevant techniques of the sensor dispatch problem in the literature.

In [14, 15], the authors consider the dispatch of mobile sensors as a multiround multiattribute sensor dispatch problem. In a hybrid WSN, each static sensor can detect only one attribute of event, while a mobile sensor can analyze multiple attributes of events. Static sensors monitor the environment and report where events appear. Then, mobile sensors are dispatched to reach these event locations to perform more in-depth analysis. To reduce and balance the energy consumption of mobile sensors, a two-phase heuristic is proposed for assigning mobile sensors to event locations. In the first phase, MAM sensors are assigned to event locations in a one-to-one manner. In the second phase, a spanning-tree construction algorithm is proposed for dispatching MAM sensors to unassigned event locations. However, sensors usually have similar capabilities, and how to efficiently dispatch mobile sensors to these event locations remains a challenge. Reference [12] investigates mobility as a means of relieving traffic burden and enhancing energy efficiency in wireless sensor networks (WSNs). Besides, the authors have discussed the mobility management algorithms of mobile sensors and reviewed some existing WSN platforms. Reference [13] addresses how to dispatch mobile sensors to the event locations in an energy-balanced way. Given event locations in each round, the authors consider dispatching mobile sensors to visit these event locations in a round-by-round manner such that the number of rounds is maximum. The idea is to minimize the energy consumption of all mobile sensors while balancing their moving costs in every round. In addition, the authors have studied the mobile sensors schedule problem in centralized and distributed situations. The difference between these literatures and ours is that they assume no obstacle in the sensing field. In fact, the sensing field may contain obstacles of any shape and size.

In [17, 28], the authors discuss that static sensors can hardly cover the entire target region and cannot ensure the network connectivity. In this case, how to deploy mobile actuator to mitigate this network architecture is a challenge. Therefore, balancing the workload of actuators is a critical issue for prolonging the network lifetime. A single actuator, which is responsible for a certain area, needs to find a minimum load. After the initial deployment of actuators to subareas, their workload is computed dynamically according to the partition result of Voronoi diagram. Once an imbalance is detected, actuators are moved for achieving a balanced load distribution. However, the area that is divided by means of Voronoi diagrams may be irregular subareas in most cases. Once the path traversing cost is unneglectable, the partition may not be optimal. In [11], the authors assume that no static sensors are deployed for sensing field because of the complicated reciprocal between coverage and communication ranges. Therefore, a number of mobile sensors are assigned to collect sensing data through routes. To balance the load, the routes of the mobile sensors should be planned in almost equal length and are constructed based on a set of carefully selected critical sensing locations. By constraining the sinks to a finite number of locations, the authors construct an optimization framework to investigate some fundamental issues of this joint sink mobility and routing problem in [29]. They mathematically formulate the problem and develop an approximate algorithm based on the primal-dual method. In [30], the authors concentrate on a data aggregation mechanism that reduces energy consumption by lowering the number of transmissions. In [31], the authors propose a new approach called Chain-Based Relocation Approach (CBRA) which reduces the energy consumption.

In [18, 19], the authors consider dispatch of mobile sensors in sensing field with obstacles. Static sensors monitor the environment and report events occurring in the sensing field, and then mobile sensors move to these event locations to conduct more advanced analysis. How to dispatch the mobile sensor to the event location without colliding with any obstacles and in a shortest path is a big challenge. The authors propose modified Dijkstra's algorithm to solve scheduling for the mobile sensor in the presence of obstacles. In these papers, the authors just consider that the shape of obstacles is convex. However, scheduling for mobile sensors in sensing field containing concave obstacles is more complex than that in sensing in sensing field containing convex obstacles.

In summarization, current research has addressed the scheduling for mobile sensors in WSNs. These research investigate the dispatch of mobile sensors with multicapability, or the sparse static sensors deployment situation. However, as discussed above, a big challenge is how to dispatch mobile sensors efficiently while prolonging the network lifetime. Particularly, once the sensing field contains obstacles of any shape and size, the deployment of mobile sensors will become more complex. This paper aims to propose a technique of remedying this issue.

7. Conclusion

In this paper, we have formulated the dispatch problem of the mobile sensor in a hybrid WSN with obstacles. To efficiently schedule the mobile sensor to find an obstacle-avoiding shortest path, a method based on connection graphs is developed by reducing the search space of the mobile sensor. Firstly, the network region is divided into grid cells with the same size and the mobile sensor can move to the sink position in each grid cell to collect sensing data. Secondly, to facilitate scheduling for the mobile sensor, regularization shape of obstacles is acquired by grid-based techniques. Finally, we find an obstacle-avoiding shortest path using connection graphs. Consequently, the network lifetime is prolonged. Experimental results show that our technique is feasible for scheduling for the mobile sensor. Once the search space is restricted to the connection graphs, the mobile sensor can be efficiently dispatched to find an obstacle-avoiding shortest path. In this paper, we just consider a one-to-one shortest path problem. As for the future work, we plan on extending current work to the many-to-many shortest path problem.