Actor Positioning with Minimal Movement in Wireless Sensor and Actor Networks

Abstract

This paper proposes an algorithm that relocates actors to appropriate positions in order for them to act as cluster heads (CHs) with minimal movement in a clustered sensor network. The proposed algorithm assigns actors to target positions in the cluster center (CC). The CC is an area where the transmission ranges of a CH and its neighboring sensors are overlapped. The proposed algorithm first computes a CC in a cluster and then designates the closest point from an actor in the CC as a target position. At the target position, a relocated actor establishes direct links with all neighbors of a CH in order to substitute for the CH. The target position is located on the boundary of the CC, whereas the CH position is inside the region. Therefore, the actor reduces the movement distance required to become a CH when it moves to the target position rather than to the CH position. In the simulation, our proposed algorithm is compared with the existing algorithm that places the actor at the CH position. The results of the simulation show that our algorithm reduces the movement distance by 12.7% compared with that of contemporary scheme.

1. Introduction

Wireless sensor and actor networks (WSANs) have been receiving significant attention from many researchers because of their potential for various new applications that require autonomous interaction with the environment. WSANs consist of a group of sensors and movable actors that are linked by a wireless medium to perform sensing and acting tasks [1]. The sensors detect and report events of interest to the actors. The actors, on the other hand, make decisions and perform appropriate actions based on reports received from sensors. WSANs can be used in various applications, such as forest fire monitoring, urban search and rescue, battlefield surveillance, home automation, and environmental monitoring.

One of the major issues with WSANs is determining the positions of actors in order to achieve certain goals, such as minimizing the data transmission delay, balancing message load, and maximizing the coverage of sensors [2]. Ideally, the positioning of actors should be performed autonomously because of environments that are often harsh and inaccessible. For instance, in a fire monitoring application in a forest, actors such as fire extinguishing robots or flying aircrafts can be deployed rapidly to target positions to control the fire and prevent it from spreading. This requires that actors relocate to positions without human intervention because of the harsh environment [3].

In a clustered sensor network, once the cluster heads (CHs) are determined, the actors should also be relocated while considering the distribution of the sensors to act as CHs when they are deployed randomly in the area. The reason for this is that actors have more resources and more powerful computation capabilities than sensors. However, although the actors possess more resources than the sensors, their energy is still limited. The actors use more energy when they move than when they compute or receive data [4]. Moreover, recharging actors is not easy once they have been deployed in the field. Therefore, reducing actor movement is vital for minimizing energy consumption.

Several algorithms have been proposed to identify actor positions that would reduce their travel distance within a WSAN. For instance, [5] proposed an algorithm that matches one actor to a CH without conflicts when the actors are randomly deployed in a clustered sensor network. The actors then move to the matched CH locations and act as the CHs. The approach proposed in [6] nominates a highly connected noncritical actor as a recovery candidate to restore connectivity in mobile actor/robot networks. The designated actor detects the failure of connectivity and executes a recovery procedure by repositioning itself to the location of the failed node. These algorithms reduce the total distance moved by the actors. However, the movement distance can be further reduced if the actors are relocated based on position information.

This paper proposes an actor positioning algorithm that relocates actors to appropriate locations based on position information. The proposed algorithm identifies a target position; the actor then moves to this position and acts as a CH, based on the constraint of minimal movement in the clustered sensor network. This method first computes a cluster center (CC) within a cluster and then locates a target position in the CC to assign an actor to the position. The CC is an area in which both the signal of a CH and all signals of neighboring sensors overlap. In the CC, the moved actor can establish direct links to all neighbors of a CH and then act as the CH. The target position is the closest point to an actor in the CC and is located on the boundary of the CC, whereas the CH is located inside the region. Therefore, the movement required for an actor to become a CH is minimized when the actor moves to the target position rather than to the position of the CH. Additionally, the movement time and energy consumed by the actor are minimized.

This paper is organized as follows. Section 2 provides a summary of the related research. An algorithm that assigns an actor to the target position is described in Section 3. The performance of the proposed algorithm is evaluated using a simulation in Section 4. Section 5 concludes the paper.

2. Related Work

The issue of actor positioning in WSANs has been studied extensively. For instance, the autonomous actor placement algorithm in [7, 8] applied the concepts of repulsive force and attractive force; actors deployed randomly can maintain constant distances by repelling each other. The goal of the algorithm is to maximize coverage while maintaining the connectivity of the actors. Research that applied the same concepts to environments with obstacles is presented in [9]. In addition, some approaches were proposed for controlled actor placement. For example, [10, 11] suggested a new architecture of a mobile robot (actor) for deployment in wireless sensor networks. The principle is to relocate the actors to target positions so as to maintain connectivity and coverage in human unfriendly environments. On the other hand, in [12, 13], stationary actors are positioned at nearby locations to collect data from moving sensors. The actors are aware of their positions and take appropriate actions based on the collected data. However, these algorithms relocate the actors without considering the sensor distribution.

Unlike these algorithms, [14, 15] proposed methods that deploy actors such that the sensor-actor binding rate is maximized within the WSANs. The algorithms divide the area of interest into cells and then assign the actors to the intersection points of the cells such that sensor coverage is maximized by binding minimal actors with maximal sensors. The algorithm proposed in [16] identifies the position of actors in a clustered sensor network. This algorithm divides the monitored region into several virtual regular hexagonal areas and places the actors in the center of each regular hexagon as CHs. This algorithm places the actors such that they can receive data and take action within an imposed time delay limit. Similarly, an algorithm proposed in [17] determines the position of actors based on the residual energy level of the CH in a clustered sensor network. The actors locate optimal positions with respect to their associated CHs such that the overall energy consumed is minimized. The work in [16] presented an actor placement approach in a clustered sensor network. The proposed algorithm forms clusters and places an actor at the center of each cluster. The goal of this algorithm is to deploy the actors to cover the monitoring area where they receive data and take actions within an imposed time delay limit. The goal of this algorithm is to extend the network lifetime. These actor positioning algorithms place the actors based on the sensor distribution. However, they do not minimize movement distance of the actors so as to reduce their time and energy consumption.

To minimize the movement distance of actors in a WSAN, various algorithms for positioning actors have been proposed. For instance, an algorithm proposed in [5] assigns actors to appropriate CH locations in a clustered sensor network. This algorithm adapted the Gale-Shapley (GS) stable matching algorithm [18] to match actors and CH locations. Once matched, the actors then move to their designated CH locations with the goal of minimizing the total distance traveled by actors, without creating any conflicts. An actor positioning algorithm proposed in [19] minimizes the actor-sensor delay time while maximizing the actor coverage. The actors are deployed uniformly to maximize the coverage; once sensor clustering is performed, each actor couples with the closest cluster to minimize its movement. The actors then relocate based on the vertex 1-center within each cluster to minimize the actor-sensor delay. An algorithm proposed in [20] places the actors within the sensor cluster. Actor placement is achieved by determining the k-hop independent dominating set (IDS) of the sensor network. Initially, the sensors select CHs based on IDS, and then the actors are placed at the CH locations. The goal of these algorithms is to maximize the coverage of actors and minimize the data delay time.

Additionally, various actor positioning algorithms for network partitioning recovery have been studied. Many approaches have been proposed to connect the subnetworks by relocating the actor(s) to the position of the failed node(s). For example, an actor positioning algorithm in [21] replaces the failed actor with a suitable candidate based on the physical proximity. The goal is to minimize the total distance travelled by the involved actors. In [22], the authors suggested an actor positioning algorithm that relocates the smallest number of actors using block movements instead of individual actors in cascade movements. This approach decreases the minimum travel distance of individual nodes of all of the involved actor nodes.

However, the actor positions identified by these approaches are the same as the positions of existing sensors. In contrast, our approach identifies a specific position, instead of an existing CH/sensor location, and assigns the actor to that position such that its movement distance is minimized.

3. Actor Positioning Based on Minimal Movement

3.1. System Model and Assumptions

Our algorithm focuses on identifying the position at which an actor will be placed within a sensor cluster to act as a CH, with minimal movement. In this paper, we assume that a set of sensors are deployed randomly in an area of interest, and that their locations do not overlap. Sensors are deployed in abundance while actors are fewer than sensors. After deployment, the sensors notify their 1-hop neighbors through messages and then establish direct links with their neighbors. We also assume that the deployed sensors form clusters, and then some sensors become CHs through existing techniques such as [20]. The CHs establish direct links with neighboring sensors and retain the position information of the sensors.

Once the CHs and their locations are determined, we assume that actors are deployed randomly in the same region. After that, each CH is matched with an actor based on their proximity to each other. This matching process can be performed using existing algorithms such as that in [5]. If the matching process is done, we assume that the CH transmits the position information of its neighboring sensors to the matched actor. The actor then computes the target position based on the position information received from the CH. Later, the actor relocates to the target position, where it can connect with the same sensors as the CH and then performs appropriate actions.

To simplify the analysis, sensors are assumed to have the same transmission range. We also assume that sensors are stationary, which is typical for WSNs. However actors are able to move at any time. In addition, it is assumed that both actors and sensors know their positions, based on onboard GPS [23] in an outdoor environment or using localization schemes [24, 25] in indoor/outdoor environments. To improve localization accuracy, we assume both that there are no obstacles in the region and that communication among sensors and actors is stable.

3.2. Cluster Center (CC)

The neighbor set (NS) is the set of sensors that are at 1-hop distance from the CH in a cluster. The core set (CS) is a set that consists of the NS and a CH. Therefore, the CC is an area in which the transmission ranges of all sensors in the CS overlap. In a CC, a moved actor can establish direct links with all sensors in the CS. To calculate the CC of a cluster, the actor needs position information regarding the sensors in the CS. The CC is formed based on the position of a CH. Therefore, the position of the CH is taken as the origin of coordinates in the cluster. Similarly, the positions of the sensors in the cluster are set relative to the position of the CH.

Figure 1 presents an example of a CC. The CS consists of four sensors, namely, a CH ( $S_i$ ) and NS ( $S_j,S_k,S_l$ ). In this figure, the CC is the colored area $\Delta (P_{jk},P_{kl},P_{lj})$ , in which the transmission ranges of all sensors in the CS overlap.

Figure 1

An example of a cluster center.

3.3. Intersection Point

An intersection point is a position at which the transmission boundaries of the sensors intersect. A transmission boundary is the perimeter of a transmission area; it can be defined as a circle with a radius equal to the transmission range r. The transmission boundaries of the sensors intersect at two points when the distance between the two sensors is less than $2r$ . The sensors can recognize (and establish a direct link with) each other when the distance between them is less than r. For instance, as shown in Figure 2, both $S_i(x_i,y_i)$ and $S_j(x_j,y_j)$ can recognize each other when the distance d between them is less than r. The sensors then create two intersection points $(P_{ij}^{\prime }(x_{ij}^{\prime },y_{ij}^{\prime }),P_{ij}^{\prime \prime }(x_{ij}^{\prime \prime },y_{ij}^{\prime \prime }))$ and establish direct links with each other.

Figure 2

Intersection points of transmission boundaries ( $d\le r$ ).

The intersection points can be computed based on the position information regarding the sensors as follows:

$$\begin{array}{cc}& P_{ij}^{\prime }\left(x_{ij}^{\prime },y_{ij}^{\prime }\right),\hspace{1em}{x}_{ij}^{\prime }=x_{\mathrm{0}}-\frac{h\left(y_j-y_i\right)}{d},\hspace{0.17em}\hspace{0.17em}{y}_{ij}^{\prime }=y_{\mathrm{0}}+\frac{h\left(x_j-x_i\right)}{d},\\ P_{ij}^{\prime \prime }\left(x_{ij}^{\prime \prime },y_{ij}^{\prime \prime }\right),\hspace{1em}{x}_{ij}^{\prime \prime }=x_{\mathrm{0}}+\frac{h\left(y_j-y_i\right)}{d},\hspace{0.17em}\hspace{0.17em}{y}_{ij}^{\prime \prime }=y_{\mathrm{0}}-\frac{h\left(x_j-x_i\right)}{d},\end{array}$$

(1)

where

$$\begin{array}{cc}& x_0=\frac{\left(x_i+x_j\right)}{2},\\ y_0=\frac{\left(y_i+y_j\right)}{2},\\ h=\sqrt{\left(r^2-a^2\right)},\\ a=\frac{d}{2},\\ d=\sqrt{{\left(x_j-x_i\right)}^2+{\left(y_j-y_i\right)}^2}.\end{array}$$

(2)

3.4. Central Angle of an Intersection Point

The central angle of an intersection point is the counterclockwise angle whose vertex is the position of a sensor, and whose sides consist of the positive x-axis at the sensor and the virtual line that passes through both the sensor and the intersection point. For instance, in Figure 2, the central angle of intersection point $P_{ij}^{\prime }(x_{ij}^{\prime },y_{ij}^{\prime })$ at sensor $S_i$ is the counterclockwise angle ${\theta }_{ij}^{\prime }$ whose vertex is $S_i$ and whose sides are the positive x-axis at $S_i$ and the virtual line that passes through both the sensor $S_i$ and the intersection point $P_{ij}^{\prime }(x_{ij}^{\prime },y_{ij}^{\prime })$ . Similarly, the central angle of the intersection point $P_{ij}^{\prime \prime }(x_{ij}^{\prime \prime },y_{ij}^{\prime \prime })$ is ${\theta }_{ij}^{\prime \prime }$ .

The central angle ${\theta }_{ij}^{\prime }$ of intersection point $P_{ij}^{\prime }(x_{ij}^{\prime },y_{ij}^{\prime })$ at sensor $S_i(x_i,y_i)$ is computed as follows:

$$\begin{array}{cc}& {\theta }_{ij}^{\prime }=\arctan \left(\frac{D_y}{D_x}\right)+2\pi \sigma ,\end{array}$$

(3)

where

$$\begin{array}{cc}& D_x=x_{ij}^{\prime }-x_i,\\ D_y=y_{ij}^{\prime }-y_i,\\ \sigma =\left\{\begin{array}{cc}0,\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{D}_x\ge 0,\hspace{0.17em}\hspace{0.17em}{D}_y\ge 0,\hfill \\ 1,\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{D}_x\ge 0,\hspace{0.17em}\hspace{0.17em}{D}_y<0,\hfill \\ \frac{1}{2},\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{D}_x<0.\hfill \end{array}\right.\end{array}$$

(4)

3.5. Degree of Overlap of an Intersection Point

The degree of overlap of an intersection point is the number of sensors that cover the point within their transmission ranges. In other words, the degree of overlap of the intersection point is the number of sensors that are within the distance r from the point. The degree of overlap of the point p, $\mathrm{O}\mathrm{D}(p)$ , is defined as follows:

$$\begin{array}{cc}& \mathrm{O}\mathrm{D}\left(p\right)={{\displaystyle \sum }}_{\forall S_i\in \text{CS}}\tau ,\end{array}$$

(5)

where

$$\begin{array}{cc}& \tau =\left\{\begin{array}{cc}\mathrm{1},\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}d\left(p,S_i\right)\le r,\hfill \\ \mathrm{0},\hfill & \text{otherwise},\hfill \end{array}\right.\end{array}$$

(6)

where $d(p,S_i)$ is distance between point p and sensor $S_i$ .

The degree of overlap of the intersection points that form the CC is equal to the number of sensors in the CS, $\left|\mathrm{C}\mathrm{S}\right|$ , because the points are within the transmission ranges of all sensors in the CS. Therefore, the intersection point p, which is created between the sensors in NS, is one of the points that form the CC if $\mathrm{O}\mathrm{D}(p)$ is equal to $\left|\mathrm{C}\mathrm{S}\right|$ . For instance, in Figure 1, $\mathrm{O}\mathrm{D}(P_{jk})$ is 4 because the point $P_{jk}$ is included in the transmission ranges of all sensors $(S_i,S_j,S_k,S_l)$ in the CS. Therefore, the point $P_{jk}$ is one of the points that form the CC. Similarly, both $P_{kl}$ and $P_{ij}$ are points of the CC.

3.6. Nearest Intersection Point (NIP)

The nearest intersection point (NIP) is the closest point to an actor among the intersection points in the CC. The $L_{\mathrm{C}\mathrm{C}}$ is defined as the list of intersection points that form the CC (i.e., $\mathrm{O}\mathrm{D}(p)$ is equal to $\left|\mathrm{C}\mathrm{S}\right|$ ). Therefore, the NIP is the closest point to an actor, among the points in the $L_{\mathrm{C}\mathrm{C}}$ . The distance between an actor, $A(x_A,y_A)$ , and an intersection point, $P_k(x_k,y_k)$ , in the $L_{\mathrm{C}\mathrm{C}}$ is computed using their position coordinates as follows:

$$\begin{array}{cc}& d\left(A,P_k\right)=\sqrt{{\left(x_A-x_k\right)}^{\mathrm{2}}+{\left(y_A-y_k\right)}^{\mathrm{2}}}.\end{array}$$

(7)

3.7. Nearest Boundary Point (NBP)

The nearest boundary point (NBP) of a sensor is the closest point to an actor in the transmission range of the sensor. Therefore, the NBP exists on the transmission boundary of the sensor and is created when the transmission boundary of the sensor intersects at one point with the virtual circle which is centered on an actor. Similarly, an NBP of a CC is the closest point to an actor in the CC and exists on the boundary of the CC.

The boundaries of the CC consist of the transmission boundaries of the sensors that create the intersection points of the CC. Therefore, the NBP of a CC is created when the virtual circle surrounding an actor intersects at one point with the transmission boundary of a sensor that generates a point (or points) belonging to the $L_{\mathrm{C}\mathrm{C}}$ . In this case, the created point(s) should be within the scope of the CC.

For example, Figure 3 shows a CC that is created by both a CH ( $S_i$ ) and its neighboring sensor ( $S_j$ ). The boundaries of the CC consist of the transmission boundaries of the two sensors $(S_i,S_j)$ . The NBP of sensor $S_i$ is the intersection point $P_{iA}$ . The NBP of sensor $S_j$ is the point $P_{jA}$ . In this case, the $P_{iA}$ is within the scope of the CC at $S_i$ , and the $P_{jA}$ is outside the scope of the CC at $S_j$ . Therefore, the $P_{iA}$ becomes the NBP of the CC.

Figure 3

The NBP in the CC.

The NBP of sensor $S_i(x_i,y_i)$ can be computed as follows:

$$\begin{array}{cc}& P_{iA}\left(x_{iA},y_{iA}\right)=S_i+\frac{r\left(A-S_i\right)}{d}=\left(x_i,y_i\right)+\frac{r\left(x_A-x_i,y_A-y_i\right)}{d}=\left(x_i+\frac{r\left(x_A-x_i\right)}{d},y_i+\frac{r\left(y_A-y_i\right)}{d}\right),\end{array}$$

(8)

$$\begin{array}{cc}& {\theta }_{iA}=\arctan \left(\frac{\left(y_{iA}-y_i\right)}{\left(x_{iA}-x_i\right)}\right),\end{array}$$

(9)

where

$$\begin{array}{cc}& d=\sqrt{{\left(x_A-x_i\right)}^2+{\left(y_A-y_i\right)}^2}.\end{array}$$

(10)

3.8. Target Position (TP)

A target position (TP) is the closest point to an actor in the CC; it is also the position to which an actor will be relocated. The TP is determined from either an NIP or an NBP. An NBP becomes the TP if it is within the CC, because it is the closest point to the actor in the region. However, if all the NBPs of the sensors in CS are out of the CC, the NIP becomes the TP, because the NIP is the closest point to an actor in the CC. The TP is created on the boundary of the CC if the actor is located outside the region. The actor moves to the TP to act as a CH if the TP is identified. However, it is unnecessary for the actor to move if it is already located within the CC.

Theorem 1.

The distance travelled by an actor to a TP is less than or equal to the movement distance to a CH.

Proof.

A CC is created by both a CH and the sensors in the CS. The CH is located within the CC if $d(\mathrm{C}\mathrm{H},S_i)<r$ for each sensor $S_i$ in the CS, where $d(\mathrm{C}\mathrm{H},S_i)$ is the distance between the CH and the $S_i$ . In this case, the distance between the TP and the actor A, $d(\mathrm{T}\mathrm{P},A)$ , is less than the distance between the CH and the actor A, $d(\mathrm{C}\mathrm{H},A)$ ; that is, $d(\mathrm{T}\mathrm{P},A)<d(\mathrm{C}\mathrm{H},A)$ . However, the CH is on the boundary of the CC if $d(\mathrm{C}\mathrm{H},S_i)=r$ for any sensor $S_i$ , and, thus, $d(A,\mathrm{T}\mathrm{P})$ is less than or equal to $d(\mathrm{C}\mathrm{H},A)$ . Therefore, in the worst case, the actor movement distance to the TP is equal to the movement distance to the CH.

The TP can be computed based on the position information regarding the sensors in the CS rather than the whole sensors in the cluster. To minimize the distance between an actor and a TP, the size of a CC should be maximized because the TP is located on the boundary of the CC. The size of the CC is affected by the density of the sensors in the CS. If this density increases, then more sensors are located near the transmission boundary of the CH, and thus the size of the CC decreases. This means that the distance between the actor and the TP increases up to the $d(\mathrm{C}\mathrm{H},A)$ ; that is, $d(\mathrm{T}\mathrm{P},A)=d(\mathrm{C}\mathrm{H},A)$ . However, the size of the CC increases once the density of the sensors in the CS decreases. In such case, the distance between the actor and the TP decreases; that is, $d(\mathrm{T}\mathrm{P},A)\le d(\mathrm{C}\mathrm{H},A)$ .

3.9. Actor Positioning Algorithm

The algorithm consists of two parts: computing a CC of the cluster and identifying the NIP and NBP of the CC. Algorithm 1 shows the algorithm that assigns an actor to the TP in a cluster.

Algorithm 1: Actor positioning algorithm.

// Create matrix M for the intersection points of the sensors

(1) for each pair of $S_i,S_j\hspace{0.17em}(i\ne j)\in CS$

(2)    $M(i,j)\leftarrow p_{ij}$

(3) end for

// Compute the degree of overlap of the intersection point p

(4)   for each point $\mathit{p}\in M(i,j)$   &   $S_k\in \text{CS}$

(5)     if $d(\mathit{p},S_k)\le r$

(6)    increase $\text{OD}(p)$

(7)    if $(\text{OD}(p)==|\text{CS}|)$

(8)    Append $(L_{\text{CC}},p)$

(9)    end if

(10)   end if

(11)  end for

// Compute NIP, $P_{\text{NIP}}$ , and assign to target position, $P_{\text{TP}}$

(12) for each point $\mathit{p}\in L_{\text{CC}}$

(13)  identifies the MIN $(d(A,\mathit{p}))$

(14)   $P_{\text{TP}}\leftarrow P_{\text{NIP}}\leftarrow$  Position( p )

(15)  Append $(L_{\text{ID}},\text{ID}(\mathit{p}))$

(16) end for

// Compute NBP, $P_{\text{NBP}}$ , and check whether it is within the CC

(17) for each id $i\in L_{\text{ID}}$

(18)  compute $P_{iA}$ , ${\theta }_{iA}$

(19)  identifies intersection point $p_1$ , $p_2$ of i in $L_{\text{CC}}$

(20)  assign $\text{Angle}(p_{\mathrm{1}})$ , $\text{Angle}(p_{\mathrm{2}})$ to ${\Phi }^{\prime }$ , ${\Phi }^{\prime \prime }$ in counter-clockwise order

(21)  if (( ${\theta }_{iA}$ is within ${\Phi }^{\prime }$ , ${\Phi }^{\prime \prime }$ ) & ( $d(A,P_{iA})<d(A,P_{\text{TP}}))$ )

(22)    $P_{\text{TP}}\leftarrow P_{\text{NBP}}\leftarrow P_{iA}$

(23)  end if

(24) end for

Initially, the intersection points and central angles of the points are calculated using (1) and (3). Then, a matrix M is created for the intersection points (lines (1)–(3)).

The degree of overlap of the intersection point is determined by computing the distance between the point and each sensor in the CS (lines (4)–(11)). The degree of overlap of the point is the number of sensors that are within a distance r from the point and can be calculated using (5). The intersection point p is appended to the list, $L_{\mathrm{C}\mathrm{C}}$ , if $\mathrm{O}\mathrm{D}(p)=\left|CS\right|$ , because the point is within the transmission ranges of all sensors in the CS, which means that the point forms the CC.

The NIP, $P_{\mathrm{N}\mathrm{I}\mathrm{P}}$ , is computed. Then it becomes the candidate of a TP, $P_{\mathrm{T}\mathrm{P}}$ , (lines (12)–(16)). The NIP is a point of the $L_{\mathrm{C}\mathrm{C}}$ that is closest to the actor. The identifier of the sensor that creates the NIP is added to the list, $L_{\mathrm{I}\mathrm{D}}$ , to be used in identifying the NBP.

The NBP, $P_{\mathrm{N}\mathrm{B}\mathrm{P}}$ , is computed with respect to the sensors in $L_{\mathrm{I}\mathrm{D}}$ (lines (17)–(24)), because the sensors that create the NIP also generate the NBP. The NBP is then checked to determine whether it is included in the scope of the CC. The NBP with the shortest distance from the actor becomes the TP only if it exists within the CC.

For instance, Figure 4 has an actor A and four sensors in the CS, where CH is $S_i$ and its neighbors are $S_j$ , $S_k$ , and $S_l$ . The CC consists of three intersection points ( $P_{jk}$ , $P_{kl}$ , and $P_{lj}$ ), whose degree of overlap is 4. In this case, the NIP is $P_{lj}$ , as it is closest to the actor. The NIP that is created by two sensors ( $S_l$ , $S_j$ ) becomes the candidate target position. The NBPs of sensors $S_l$ and $S_j$ are points $P_{lA}$ and $P_{jA}$ , respectively. Point $P_{lA}$ , which is the NBP of $S_l$ , is within the scope of the CC. However, point $P_{jA}$ , which is the NBP of $S_j$ , is outside the scope of the CC. Given this fact, point $P_{lA}$ becomes both the NBP and the TP of the actor.

Figure 4

Target position of an actor.

4. Simulation

The performance of the proposed algorithm is validated through simulations. Simulations have been performed in a WSN simulator developed in C++; we have adopted the parameters and network operation model of [5]. We have randomly deployed a varying number of sensors (100–900) in a 1,000 m × 1,000 m area. After the sensors are deployed, the actors are also placed randomly within the same region. We then have compared the movement distance of the actors using our algorithm and the movement distance when using the existing approach when an actor matches a CH.

In the simulation, Move[Actor-TP] refers the movement that an actor travels to reach a TP in our proposed algorithm, and Move[Actor-CH] is the movement that an actor travels to reach the CH position in the existing approach. To achieve performance stability, the results of individual experiments are averaged over 1,000 trials.

The following performance metrics are used to assess the performance:

• (i)

The average movement distance of an actor: this metric is the average distance travelled by an individual actor. It indicates the superiority of the proposed algorithm in terms of movement distance.

(ii)

The total movement distance of the actors: this is the sum of the distance travelled by all actors deployed in the area. It indicates the efficiency of the proposed algorithm in terms of the reduction of movement distance.

In the simulation, the following parameters are used to vary the WSAN configuration:

• (i)

The transmission range of the sensors: this influences the size of the CC and the number of neighboring sensors of the CH.

(ii)

The number of sensors in the cluster: this affects the number of sensors in the CS.

(iii)

The number of actors in the area: this influences the average distance between an actor and a matched CH.

Figure 5 shows the distance traveled by actors as the number of deployed actors is varied. The figure indicates that the average movement distance of actors when the transmission range of sensors is set to 150 m and the number of deployed sensors in the area is 80. The graph indicates that the movement distance using our algorithm is 9.7–16.2% less than the distance traveled when using the existing approach.

Figure 5

Average distance moved by actors ( $r=150$ , sensor = 80).

Figure 6 shows the movement distance of actors after their deployment. Figure 6(a) depicts the average movement distance of actors as the number of sensors in the CS is varied. The figure illustrates the movement distance when the sensor transmission range is set to 50 m, 100 m, and 150 m. The graph indicates that the distance moved by the actor is further reduced when there are fewer sensors.

Figure 6

Movement distance of actors.

Similarly, Figure 6(b) depicts the average movement distance of actors as the transmission range of sensors is varied. The figure illustrates the movement distance when the number of sensors in the CS is set to 5, 15, and 25. The graph indicates that the movement distance is further reduced as the transmission range of the sensor increases.

Figure 7 shows the consumed time and energy of actors while moving when the transmission range of the sensors is 150 m and the number of the deployed sensors is 200. Figure 7(a) depicts the average movement time of the actors as the number of deployed actors is varied. The figure illustrates the movement time when the speed of the actor and the initial processing delay are set to 2 m/s and 10 s, respectively [26]. Figure 7(b) depicts the average energy consumed by actors as the number of deployed actors is varied. The figure illustrates the consumed energy when the energy consumption rate of an actor is set to 27.96 J/m, which is calculated based on a mobile sensor prototype [27]. The graph indicates that the energy consumed by actors when using our algorithm is less than the energy from the existing approach by 14.7–17.4%.

Figure 7

Movement time and energy consumed by actors.

Figure 8 shows the cumulative movement distance of actors when both the density and the transmission range of sensors are varied. The figure illustrates the movement distance when using our proposed algorithm when the number of the actors is 9. The graph indicates that the movement distance is reduced when either the sensor density is lower or the transmission range of the sensor is higher. This phenomenon results because these conditions extend the CC. Additionally, to minimize the actor movement, the number of actors that will be deployed should be decided based on the number of CHs. If the number of actors is greater than the number of CHs, the remaining actors become redundant. However, if the number of CHs is greater, then certain CHs will be left without an actor assignment. That is to say, if the number of CHs and actors is not equal, additional actor movement will be required to merge the clusters or spread the actors further apart in the network [5]. Therefore, the movement distance of the actors is minimized when the number of CHs is equal to that of the actors in the network. In the graph, the fluctuation of the movement distance is caused by the CC temporarily shrinking when a new sensor joins the CC while either the sensor density or sensor signal varies. Despite these fluctuations, the graph demonstrates that the total distance traveled by the actors gradually reduces.

Figure 8

Movement distance of actors while varying the amount and transmission range of sensor (actor = 9).

The simulation results show that our proposed algorithm significantly outperforms the existing algorithm in terms of the distance traveled by the actors. Additionally, the movement distance is further reduced when the density of the deployed sensors is low and the transmission range of the sensors is high.

5. Conclusion

This paper proposes an actor positioning algorithm that relocates actors to TP such that their total movement distance in a clustered sensor network is minimized. The TP is the closest point to an actor in the CC. The CC is an area in which the transmission ranges of a CH and its neighboring sensors overlap. The proposed algorithm first computes a CC in a cluster and then determines the closest point to an actor in the CC as a TP. At the TP, a relocated actor establishes direct links with all neighbors of a CH so as to substitute for the CH. The TP is located on the boundary of the CC, whereas the CH position is inside the region. Therefore, the actor minimizes the movement distance required to become a CH when it moves to the TP rather than to the CH position.

A simulation has been performed to evaluate the performance of the proposed algorithm. In the simulation, our proposed algorithm is compared to the existing algorithm, which places the actor at the CH position, while varying both the number of deployed sensors and their transmission ranges. The results of the simulation show that our algorithm reduces the movement distance by 12.7% compared with that of the contemporary scheme. In addition, the algorithm reduces the movement time and energy required for actors to relocate. The results also confirm that the proposed algorithm further reduced actor movement when the number of sensors in a CS decreased or when the transmission range of sensors increased. This indicates that our algorithm performs better when applied to sparse networks than when applied to dense networks. In the future, we plan to apply this algorithm for maintaining and restoring actor connectivity in WSANs.