K-Hop Coverage and Connectivity Aware Clustering in Different Sensor Deployment Models for Wireless Sensor and Actuator Networks

Abstract

In wireless sensor and actuator networks, WSAN, actuators often act as cluster headers. Since the transmission range of actuator is much larger than that of sensor, both of the coverage of actuator and the connectivity of sensor-actuator require to be considered in the clustered WSAN. However, the existing clustering algorithms in WSAN only addressed the coverage issue. None of them considered the coverage and the connectivity jointly. Thus we proposed a K-hop coverage and connectivity aware clustering (K-CCAC) in this paper. The different sensor deployment models may affect the coverage and the connectivity for clustering. Thus K-CCAC was evaluated in five sensor deployment models we proposed. Simulation results demonstrated that the coverage and the connectivity in K-CCAC could be up to 100 % with fewer actuators in each model. The hop count from leaf sensors to cluster headers could be limited to K. Moreover, the number of actuators could decrease when the ratio of the transmission radius of actuator to that of sensor or the number of sensors increased.

1 Introduction

WSAN is a new kind of heterogeneous wireless sensor networks (WSN). Sensors are low cost and low power devices with limited sensing computation and wireless communication capabilities. Sensors are responsible for measuring ambient conditions and reporting such measurements to some actuators over wireless communication links. Actuators are equipped with higher processing capabilities, longer transmission radius, and larger battery energy. Actuators have the capability for processing the sensed data, making decisions, and performing the appropriate actions.

For different types of applications, WSAN was divided into semi-centralized and centralized architectures [1]. In the semi-centralized architecture, sensors detect a phenomenon and route data back to the sink which may issue action commands to actuators. Thus the semi-centralized architecture could not need to develop new algorithms or protocols for communication and coordination. However, actuators may postpone performing the actions because of waiting the action commands from the sink.

In the centralized architecture, sensors gather and transmit the sensed data to the appropriate actuators directly. Actuators thus take decisions and perform actions from the sensed data directly. So sensors could save more energy without forwarding the sensed data to sink. Moreover, the latency of performing actions could be minimized and the lifetime of network could be prolonged. In the rest of this paper, we focused on the centralized architecture in WSAN.

In WSAN, several proposals were concerned with enhancing and complementing the existing WSN applications [1–4]. For example, in the case of a fire, sensors relay the exact origin and intensity of the fire to water sprinkler actuators so that the fire can easily be extinguished before it becomes uncontrollable. To provide this service, a clustered architecture was proposed in WSAN.

In the clustered architecture, each actuator acts as a cluster header and performs the appropriate actions based on the sensed data from the sensors in its cluster. However, most of researches focused on the coverage of sensed data without considering the connectivity [5–8]. Once the connectivity is fail, actuators could not perform actions because no routing path exists among sensors and actuators. In addition, the number of deployed actuators will affect the cost of clustering.

Therefore, it is important to use the fewer actuators to maximize the coverage and guarantee the connectivity. To address this issue, we proposed K-CCAC in this paper. Since the cluster may be affected by the different sensor deployment models, we analyzed the performance of K-CCAC in the different sensor deployment models. In other words, K-CCAC could cluster sensors in K-hop independent dominating set (K-IDS) [7].

Since to determine K-IDS of a network was a NP-hard problem [9, 10], K-CCAC aimed to propose a heuristic approach to solve this problem without considering the whole network status in a distributed manner. In K-CCAC, the parameter K showed the maximal hop count for a sensor to reach its cluster header. Therefore, each sensor could relay its data within K hops to its cluster header without considering the whole network status to perform actions in K-CCAC. Finally, we evaluated the performance of K-CCAC in the different sensor deployment models we proposed.

The rest of the paper was in the following sections. Section 2 presented the related work. Our scheme was stated in Sect. 3. Section 4 presented the performance evaluation. The conclusions were shown in Sect. 5.

2 Related Work

In WSN, the coverage problem was an important issue and had been studied as an important quality of service in many literatures [11–13]. However, it may not be suitable for the unique features and the application requirements of WSAN due to the heterogeneous actuators. To solve this problem, the clustered architecture was usually used.

Regarding the clustering problem, it had been a lot of research in WSN [12–16]. However, most of these algorithms aimed to maximize network lifetime and data throughput, and provide load balancing and fault tolerance. None of them were geared for picking the cluster header, like a good coverage, since the coverage of cluster header was not an issue in WSN. In addition, WSAN not only had the sensing coverage problem but also the action coverage problem.

Hence, it was fairly new and did not have much work on coverage and clustering problems in WSAN. However, given the infinite solution space and the minimum overlap of actuator’s coverage, finding the optimal locations and number of actuators was a very complex problem which had been proven to be a NP-hard problem [7, 8]. Therefore, the solutions for this issue were usually heuristics.

C²AP [6] was a clustering mechanism concerned with the actuator coverage and the inter-connectivity of actuators in WSAN. In C²AP, the actuator position was based on sensors’ location and connectivity, while both sensors and actuators known their locations through methods, like GPS or other means. It placed n actuators and m sensors in an interested area randomly, where n was much less than m. In C²AP, sensors were static but actuators were mobile. The orphan actuators were defined as that they were isolated from the core network, for example, when they got placed away from the other actuators.

To determine whether actuators could be moved or not, C²AP defined a repelling formula. If the actuator is determined to move, new location of actuator is determined by the derived location rule. For example, A ₁, A ₂, and A ₃ are the actuators, where A ₃ is connected with A ₁ and A ₂. The locations of A ₁, A ₂, and A ₃ are defined as (a ₁, b ₁), (a ₂, b ₂), and (a ₃, b ₃), respectively. To maximize the actuator coverage without affecting the inter-connectivity among actuators, A ₃ is moved to new location (a _3new , b _3new ) by C²AP as shown in Fig. 1, where r _A is defined as the transmission radius of actuator. We found that the new coverage was larger than the former coverage after A ₃ was moved by C²AP. Moreover, A ₃ is still connected with A ₁ and A ₂ without affecting the original inter-connectivity among actuators. However, C²AP only considered the relocation of actuators without addressing the number of actuators for deploying. In this situation, C²AP may deploy the redundant actuators to serve the network area in which no sensor was or could not serve the network area due to the insufficient actuators.

Fig. 1

C²AP

Hence, a coverage-based clustering (CBC) was proposed [7]. In CBC, the coverage was referred to the number of sensors that were under the actuator coverage with respect to the total sensors. It was a new interpretation of coverage in contrast to C²AP. CBC considered the distribution of sensors within the monitored region as some parts may not have any deployed sensor at all. Even if some events may happen in those areas, the actuators will not be able to know about those events since no sensor will be reporting about those events. It is a waste of resource if an actuator is deployed in such a place. Hence, CBC aimed to minimize the overlap coverage of actuators and cover all of the sensors deployed in the monitored region.

CBC defined five types of sets as independent set (IS), dominating set (DS), K-DS, independent dominating set (IDS), and K-IDS, respectively. Initially, CBS determined IS, DS, and IDS sequentially from sending the ALIVE, DOMINATOR, and BORDER messages. After IS, DS, and IDS were determined, K-DS and K-IDS were determined by the transmission radius of actuators. Figure 2 showed the example for DS, IDS, K-DS and K-IDS in a given network topology. In these 14 nodes networks, A ₂, A ₈, A ₉, and A ₁₃ formed a 1-DS; A ₄, A ₈, A ₉, A ₁₁, and A ₁₃ formed an IDS; A ₂ and A ₄ formed a 2-DS; A ₁ and A ₇ formed a 2-IDS; and A ₄ formed a 3-DS.

Fig. 2

DS, IDS, K-DS, and K-IDS in CBC

In C²AP and CBC, to minimize overlap of coverage among actuators and cover each sensor by one actuator at least were not addressed jointly. In addition, they only addressed the orphan actuators problem without considering the orphan sensors problem. In this situation, sensor could not send the sensed data to the actuator in its cluster. Moreover, C²AP and CBC only addressed the random sensor deployment model. To solve these issues, K-CCAC was proposed and evaluated in different sensor deployment models.

None of literatures considered both of the coverage and the connectivity in WSAN. In [7, 8], it showed that to maximize the coverage with the minimum overlap and number of deployed actuators was a NP-Hard problem. Hence, all clustering algorithms were compared to the full proximity based clustering (FPC) and the random proximity based clustering (RPC). However, these algorithms addressed nothing for the connectivity problem. Hence, K-CCAC was proposed to address the coverage and connectivity jointly. In addition, we evaluated the performance under K-CCAC, FPC, and RPC in different sensor deployment models.

3 K-Hop Coverage and Connectivity Aware Clustering in Different Sensor Deployment Models

Because of the limited transmission range, to design an efficient coverage method to guarantee each sensor covered within the coverage of one actuator at least becomes an important issue. However, it requires a central node which knows the number and the locations of all deployed sensors. In most of applications, sensors are assumed to be scattered. However, this may not always be possible. Some orphan sensors within the coverage of actuators could not forward the data to the actuators because no routing path exists from these orphan sensors to the actuators. To solve the coverage and the connectivity issues jointly, K-CCAC was proposed in this paper. K-CCAC used few actuators and found the appropriate locations of these actuators to ensure all sensors within the actuator coverage. Moreover, K-CCAC could avoid the orphan sensors in each cluster to guarantee the connectivity of sensor-actuator. Before describing K-CCAC on detail, we defined the coverage and the connectivity problems in this paper. Because the different sensor deployment models may affect the performance of clustering, we also evaluated the performance of K-CCAC in five sensor deployment models we proposed. Hence, we will describe these models in the following.

3.1 Coverage and Connectivity Problem Definition

Our goal in this paper was not to improve the sensing coverage, but rather focus on the actuator coverage and guarantee the connectivity of sensor-actuator. The actuator coverage problem was defined as the maximization of all sensors covered by more one actuator at least. C _ov is defined as the number of sensors covered by actuators (N _c ) divided by total sensors (N), as in (1). For example, in Fig. 3, S ₂₃ and S ₂₅ are out of the coverage of actuator. C _cov is then calculated as 92 %.

Fig. 3

Coverage and connectivity problems

For clustering in WSAN, the connectivity between sensors and actuators is also important since actuators needed to receive the sensed data to perform actions. However, no literature was for considering the connectivity of sensor-actuator in the clustering mechanisms of WSAN. If a sensor cannot build a routing path from itself to an actuator, the connectivity is defined as the failed connectivity. This kind of sensor is defined as an orphan sensor. C _con is defined as the number of non-orphan sensors (N _o ) divided by N, as in (2). As shown in Fig. 3, S ₂₀, S ₂₁, S ₂₂, and S ₂₄ are the orphan sensors, so C _con is calculated as 84 %.

Actuators cannot perform actions if no sensor is within the coverage area or if the sensor is an orphan one. Thus both of coverage and connectivity are important in WSAN. Therefore, we defined coverage and connectivity (CC) as the total number of non-orphan sensors covered by actuators (N _nc ) divided by N, as in (3). For example, S ₂₀, S ₂₁, S ₂₂, S ₂₃, S ₂₄, and S ₂₅ are beyond the coverage of actuator or the orphan sensors, as shown in Fig. 3. CC is thus calculated as 76 %.

$$ C_{cov} = {\raise0.7ex\hbox{${N_{c} }$} \!\mathord{\left/ {\vphantom {{N_{c} } N}}\right.\kern-0pt} \!\lower0.7ex\hbox{$N$}} \times 100\;\% $$

(1)

$$ C_{con} = {\raise0.7ex\hbox{${N_{o} }$} \!\mathord{\left/ {\vphantom {{N_{o} } N}}\right.\kern-0pt} \!\lower0.7ex\hbox{$N$}} \times 100\;\% $$

(2)

$$ CC = {\raise0.7ex\hbox{${N_{nc} }$} \!\mathord{\left/ {\vphantom {{N_{nc} } N}}\right.\kern-0pt} \!\lower0.7ex\hbox{$N$}} \times 100\;\% $$

(3)

3.2 Sensor Deployment Model

The main goal of K-CCAC was to ensure that all sensors were covered by an actuator at least and no orphan sensor existed. Since the different sensor deployment model may affect C _cov and C _con , to evaluate the performance in different sensor deployment models is important. However, most of researches only assumed that sensors were scattered without considering other deployment models. Hence, we added the single region deployment, the vertical deployment, the horizontal deployment, and the oblique deployment models to evaluate the performance of K-CCAC, as shown in Fig. 4.

Fig. 4

Sensor deployment models

3.3 K-Hop Coverage and Connectivity Aware Clustering

K-CCAC used less number of actuators to maximize the coverage of the sensed data and guaranteed the connectivity of sensor-actuator. Moreover, K-CCAC could limit the maximal hop count from leaf sensors to actuators within K hops. In K-CCAC, sensors in the monitoring area were clustered in a distribute manner and each sensor only needed the information of one-hop neighboring sensors without considering the information of whole network. The algorithm of K-CCAC was as follows:

Step 1:

Each sensor broadcasts an ALIVE packet (TTL, SID) to its neighboring sensors, where TTL and SID are defined as the time-to-live value and the identity of the sensor, respectively. The initial TTL is set to K.

Step 2:

Sensors received a non-duplicate ALIVE packet subtract 1 from TTL.

Step 3:

AL _i is added to 1 while TTL is not expired, where AL _i is the accumulative number of non-duplicate ALIVE packets recorded by S _i .

Step 4:

Sensor received an ALIVE packet forwards the updated ALIVE packet with new TTL to its one-hop neighboring sensors until TTL is expired. Otherwise, the sensor stops broadcasting the ALIVE packet.

Step 5:

If a sensor does not receive any ALIVE packet and is not clustered by any actuator in a predefined time (T), it transforms itself into a dominator and an actuator is placed next to it.

Step 6:

If S _i receives an ALIVE packet but is not clustered by any actuator, it broadcasts AL _i to its one-hop neighboring sensors.

Step 7:

Non-clustered sensor i compares AL _i with other AL of its one-hop neighboring sensors.

Step 8:

If S _i has the maximal AL _i , it transforms itself into a dominator and an actuator is placed next to it.

Step 9:

If S _i does not have the maximal AL _i and its AL is not less than other AL of its one-hop neighboring sensors, S _i compares its NNC with other NNC of its one-hop neighboring sensors which their AL equaled to AL _i . S _i with maximal NNC transforms itself into a dominator and an actuator is placed next to it. NNC _i is the number of the one-hop neighboring non-clustered sensors of S _i .

Step 10:

If S _i does not have the maximal NNC _i and its NNC is not less than other AL of its one-hop neighboring sensors, S _i compares its SID with other SID of its one-hop neighboring sensors which their AL equaled to AL _i . S _i with minimum SID transforms itself into a dominator and an actuator is placed next to it.

Step 11:

The actuator broadcasts a HELLO (AID) packet, where AID shows the identity of actuator.

Step 12:

The sensors which receive a non-duplicate HELLO packet are defined as a clustered sensor. The sensors subtract 1 from TTL _HELLO and forward the updated HELLO packets with new TTL _HELLO to its one-hop neighboring sensors until TTL _HELLO is expired.

Step 13:

Sensors received the HELLO packet inform its one-hop neighboring sensors by sending a JOIN (SID, TTL _JOIN ) packet, where TTL _JOIN is defined as the time-to-live value of JOIN packet. TTL _JOIN equals to the hop count from the sensor which sends the JOIN packet to the actuator which sends the HELLO packet.

Step 14:

Sensors received a non-duplicate JOIN packet subtract 1 from TTL _JOIN and their sensors’ AL. These sensors forward the updated JOIN packets with new TTL _JOIN to its one-hop neighboring sensors until TTL _JOIN is expired.

Step 15:

Go to step 7 until all sensors are clustered by one actuator at least.

We illustrated K-CCAC with an example. Sensors are deployed randomly. Each sensor records AL and NNC, as shown in Fig. 5a. The non-clustered sensors that have not received any ALIVE packet advertise themselves as dominators within their neighborhood. Sensors with maximal AL or NNC become dominators, as shown in Fig. 5b and non-clustered sensors update their AL and NNC Non-clustered sensors with minimal SID among one-hop neighboring non-clustered sensors become dominators, as shown in Fig. 5c. Finally, all sensors are clustered, as shown in Fig. 5d. An actuator is placed next to the dominator, and broadcasts a HELLO packet to sensors within its coverage area. In Fig. 5a–d, we can see that all non-clustered sensors are within the coverage of actuator and there are no orphan sensor in the monitored region.

Fig. 5

a–d Example in K-CCAC

We could find that K-CCAC could ensure 100 % of CC within 3 hops in Fig. 5. In [9, 10], to determine an optimal number of deployed actuators to minimize the overlap coverage was a NP-hard problem for clustering. Hence, we evaluated the performance in K-CCAC, FPC, and RPC [7, 8] for different sensor deployment models. A comparison of C²AP, CBC, RPC, FPC, and CCAC-k was listed in Table 1.

Table 1 Comparison of CBC, C²AP, RPC, FPC, and K-CCAC

3.4 Mathematical Analysis

$C_{cov}^{\prime}$ and $C_{con}^{\prime}$ are calculated based on C _cov and C _con after a certain period of time. $N_{c}^{\prime}$ and $N_{o}^{\prime}$ are calculated based on N _c and N _o after a certain period of time. In FPC, N _c always equaled to $N_{c}^{\prime}$. It meant that $C_{cov}^{\prime}$ in FPC was not changed, as in (4). Hence, for applications with 100 % of C _ov , FPC cannot be used. In K-CCAC, $N_{c}^{\prime}$ must equal to N after clustering. It meant than $C_{cov}^{\prime}$ equaled 100 %, as in (5). Thus K-CCAC was suitable for applications required 100 % of C _cov . For RPC, because m and n are random, $C_{cov}^{\prime}$ was random and below 100 %. Therefore, the mathematical analysis of C _cov focused on FPC and K-CCAC.

$$ C_{cov} \equiv C_{cov}^{\prime} ,\;{\text{in}}\;{\text{FPC}} $$

(4)

$$ C_{cov} \le C_{cov}^{\prime} \equiv 100\;\% ,\;{\text{in}}\;K{\text{-CCAC}} $$

(5)

$C_{con}^{\prime}$ in FPC equaled to 100 % only if K equaled 1. K-CCAC ensured $C_{con}^{\prime}$ up to 100 % under different K. In RPC, the actuators were deployed randomly. Hence, $C_{con}^{\prime}$ was thus below 100 %. Therefore, the mathematical analysis of $C_{con}^{\prime}$ in RPC was not addressed. When C _con reached 100 %, each sensor had a routing path from itself to at least one actuator, but some sensors may not be covered by actuators. While C _cov reached 100 %, some sensors may not be able to send its data to actuators. Therefore, we defined a new mathematical equation in (3). CC in FPC could be up to 100 % only while K was set to 1. When K increased, CC in FPC decreased. However, CC in K-CCAC was always 100 % even if K was greater than 1. It showed that K-CCAC had higher CC than FPC.

Number of deployed actuators (N _A ) is another important performance metric for clustering in WSAN. In FPC, actuators were deployed fully and uniformly. Thus N _A depended on the size of the area as (6), where l, w, and r _A were defined as the length of area, the width of area, and the transmission radius of actuator, respectively. For example, l, w, and r _A are set to 1000, 1000, and 20. N _A is thus calculated as 625 in FPC. N _A in K-CCAC was calculated based on K and N without considering l, w, and r _s . Because determining of an optimal N _A to ensure 100 % of CC was a NP-hard problem [7, 8], it was difficult to derive a mathematical equation for N _A in K-CCAC. A mathematical analysis of N _A between FPC and K-CCAC was described in simulation results.

$$ N_{A} = \left\lceil {{\raise0.7ex\hbox{$l$} \!\mathord{\left/ {\vphantom {l {r_{s} \times 2}}}\right.\kern-0pt} \!\lower0.7ex\hbox{${r_{A} \times 2}$}}} \right\rceil \times \left\lceil {{\raise0.7ex\hbox{$l$} \!\mathord{\left/ {\vphantom {l {r_{A} \times 2}}}\right.\kern-0pt} \!\lower0.7ex\hbox{${r_{A} \times 2}$}}} \right\rceil $$

(6)

4 Simulation Results

A simulator we coded in a C# language was applied to conduct experiments for measuring the performance of K-CCAC, FPC, and RPC [7, 8]. Since the vertical model is similar to the horizontal model, the sensor deployment models are classified into single region model, vertical model, oblique model, and random models in the simulations. The parameter name(s) and their value(s) invoked in simulations were listed in Table 2. Two performance metrics, CC and N _A , for the evaluation of K-CCAC, FPC, and RPC was as follows.

Table 2 Simulation parameters

4.1 Experimental Results for Coverage and Connectivity

We evaluated CC with the single region model, the vertical model, the oblique model, and the random model, respectively, where K was set from 2 to 4. In Fig. 6, it showed that CC of K-CCAC all retained at 100 % in different sensor deployment models. In single region model, CC of RPC and FPC was 37 % and 62 %. In vertical model, CC of RPC and FPC was 50 % and 56 %. In oblique model, CC of RPC and FPC was 49 % and 51 %. In random model, CC of RPC and FPC was 50 % and 30 %. It proved that CC of K-CCAC was higher than that of RPC and FPC in each deployment model. As N increased over time, CC in RPC and FPC increased in vertical and random models. However, as N increased over time, CC in RPC and FPC may not increase in single region and oblique models.

Fig. 6

CC in different sensor deployment models. a CC in single region model, b CC in vertical model, c CC in oblique model, d CC in random model

A comparison of CC in different sensor deployment models was listed in Table 3. It showed that K-CCAC was suitable in any kind of sensor deployment model for 100 % of CC. However, the maximal CC in RPC was only 50 % in vertical and random models. The maximal CC in FPC was only 62 % in single region model.

Table 3 CC in different sensor deployment models

4.2 Experimental Results: Number of Deployed Actuators

Since lower N _A with lower CC may not denote the low cost for clustering, N _A in K-CCAC and FPC to provide 100 % of CC was needed. To keep 100 % of CC, K of FPC needed to be set to 1. N _A in FPC was calculated as 625 in each sensor deployment model. The maximal N _A of K-CCAC was 468 in random model, as shown in Fig. 7. It proved that K-CCAC had less N _A than FPC for 100 % of CC. Figure 8 showed that N _A in K-CCAC was always less than N _A in FPC. Moreover, while N was close to 2000, K-CCAC had maximal N _A . It proved that K-CCAC needed more N _A while N was close to the threshold value.

Fig. 7

N _A in different deployment models

Fig. 8

N _A in different number of sensors

5 Conclusions

Recent technological advances have lead to the emergence of WSAN which is composed of many sensors and few actuators, where sensors gather and send the data about the physical phenomenon. Actuators perform the appropriate actions by the sensed data. For clustering in WSAN, each actuator acts as a cluster header in a cluster to ensure that all actuators could receive the sensed data from sensors and all sensors are covered within the coverage of actuators.

Different from the clustering algorithm in WSN, WSAN not only addresses prolonging network lifetime and reducing energy consumption but also considers the coverage problem. In this paper, we focused on the coverage problem for clustering in WSAN. However, most of the clustering algorithms in WSAN were proposed to maximize the coverage among actuators. These literatures addressed nothing for the connectivity of sensor-actuator. In this situation, some orphan sensors may be covered by actuators but had no routing path to transmit data to the actuators. Therefore, we proposed a K-hop coverage and connectivity aware clustering (K-CCAC) to address the coverage and the connectivity problems jointly. Moreover, K-CCAC could guarantee that sensors send a packet to actuators within K hops.

Sensors were all scattered in the past research. However, the different sensor deployment models may affect the coverage and the connectivity for clustering in WSAN. Hence, we evaluated the performance in K-CCAC, RPC, and FPC for different sensor deployment models, such as single region model, vertical model, horizontal model, oblique model, and random model, respectively.

In K-CCAC, each actuator acted as a cluster header and each sensor picked a cluster header in its cluster. Different from other clustering algorithms, such as C²AP and CBC, K-CCAC used fewer actuators to cluster sensors in a distributed manner. To avoid the orphan sensors in the network area, K-CCAC placed the actuators to make each sensor covered by at least one actuator and ensured that no orphan sensor existed. Therefore, K-CCAC ensured C _cov could be up to 100 % without affecting the connectivity of sensor-actuator.

The simulation results demonstrated that K-CCAC provided up to 120 % and 100 % increase for C _cov compared to RPC and FPC. In different sensor deployment models and different N, K-CCAC all provided 100 % of CC. K-CCAC retained at 100 % of N _A and provided up to 30 % of N _A decrease compared to FPC. Moreover, the simulation results showed that K-CCAC had the maximal N _A with 100 % of CC while N was close to a threshold value. It showed that N _A in K-CCAC could be reduced in the lower and higher density of sensors. In the future, we will investigate the efficient technology to reduce more number of actuators. Moreover, we will integrate the power load balance with K-CCAC to save more power energy.