An Adaptive Aggregation Scheduling Algorithm Based on the Grid Partition in Large-Scale Wireless Sensor Networks

Abstract

Data aggregation algorithm aims to reduce the redundant information by gathering the sensed data, save energy, and prolong the lifetime of the network. However, the data aggregation technology will increase the network transmission delay of wireless sensor networks. Minimum-latency aggregation scheduling is designed to minimize the number of scheduled time slots to perform an aggregation. In this paper, we present an Adaptive Aggregation Scheduling Algorithm based on the Grid Partition (AASA-GP) in large-scale wireless sensor networks. By dividing the network into grids based on the geographical information, we allocate the channels according to the grid coordinates. Nodes with the same grid coordinates use the same channel and the adjacent grids use the different channels, so we can effectively avoid the wireless media transmission interference, increase the parallel transfer rate, and reduce the aggregation latency. Our extensive evaluation results demonstrate the superiority of the AASA-GP. For small-scale networks, the resultant latency is comparable with the best practice, and it is more suitable for large-scale wireless sensor networks.

1. Introduction

In multihop wireless sensor networks, a fundamental task is to gather data from all sensors to a distinguished sink node [1, 2]. It is already noted that adjacent sensor nodes monitoring an environmental feature typically register similar values [3]. This data redundancy of the spatial correlation among sensor observations inspires the research of in-network data aggregation. In general, each intermediate node aggregates its received data with its own record according to some aggregation functions (e.g., taking the maximum or minimum of them) into a single packet with fixed size. This type of application is called data aggregation, and its communication pattern is called convergecast [4]. The naive aggregation approaches which purely rely on medium-access-control layer mechanisms could result in latency that is too high to be practical due to the existence of mutual transmission interference [5, 6]. The goal of our study is to minimize the average data aggregation latency of the convergecast process, and a synchronized aggregation scheduling is necessary, where all transmissions proceed in synchronous time slots. Such an aggregation scheduling is designed under three conditions:

• (1)

Each node transmits at most one packet with the fixed size in its allocated time slot.

(2)

A node cannot transmit until all of its children complete the transmissions to itself.

(3)

The assigned transmissions in the same time slot should be interference-free.

In this paper, the latency is measured by the number of time slots of the whole aggregation convergecast process, and our goal aims to minimize the latency.

2. Background

2.1. Transmission Interference Model

In wireless sensor networks, each node has a given transmission radius $R_t$ and an interference radius ρ. The communication range and the interference range of a node V are illustrated by the two disks centered at V of radius $R_t$ and radius  ρ, respectively (see node $S1$ in Figure 1). A pair of communication edges $S\mathrm{1}\to D\mathrm{1}$ and $S\mathrm{2}\to D\mathrm{2}$ are said to be interference-free; if the two line segments $(S1,D2)$ and $(S2,D1)$ are both longer than ρ, they can be scheduled in the same time slot, as shown in Figure 1. Otherwise, they cannot be scheduled in the same time slot (e.g., $S\mathrm{1}\to D\mathrm{1}$ and $S\mathrm{2}\to D\mathrm{4}$ ). We assume that a node works in half-duplex mode, so it can either send or receive data at one time slot or it can receive data correctly only if exactly one of its neighbors is transmitting at that moment. For example, when $S3$ is transmitting to $D3$ , it cannot simultaneously receive the packet from $S4$ .

Figure 1

Transmission interference model.

2.2. Time Scheduling on a Single Frequency Channel

An example network is shown in Figure 2(a), and the dash lines among nodes denote the communication neighborhood relationship, where node 0 is sink node. A $(\Delta -\mathrm{1})R$ approximation algorithm, Shortest Data Aggregation (SDA), is proposed by Chen et al. [7], where Δ is the maximum degree and R is the radius of the network. SDA constructs shortest spanning tree (SPT) in the first phase. After that, the scheduling is iteratively implemented; each round introduces a schedule of the corresponding aggregation step. In round r, SDA picks sender only from the leaf nodes according to the interference-free principle. The performance of SDA varies greatly, which depends on the SPT's initial provision, and this is illustrated by the example network in Figure 2(b) and 9 time slots are required.

Figure 2

Illustrations of single frequency channel.

GGT [8] algorithm is designed to construct the spanning trees rooted at the sink, and the initial spanning tree contains only the sink node. In each round, all nonleaf nodes of the current spanning tree are the candidates of receivers, and all leaf nodes are the candidates of senders. As for the candidate senders, there are two rules to sort them in a selection sequence: (1) sort all nodes, based on the increasing order of the number of neighbors on the tree, and (2) sort nodes with the same order by the first rule, based on the increasing order of the number of neighbors out of the tree. The scheduling result is shown in Figure 2(c) and 7 time slots are required.

2.3. Time Scheduling on Multiple Frequency Channels

In the transmission interference model [9], there exist two constraints: (1) adjacency constraint is due to the half-duplex transceiver on each node which prevents it from simultaneous transmission and reception, as shown in Figure 1; $S\mathrm{3}\to D\mathrm{3}$ and $S\mathrm{4}\to S\mathrm{3}$ cannot be scheduled in the same time slot as this constraint. (2) There is a wireless media transmission interference constraint. $S\mathrm{1}\to D\mathrm{1}$ and $S\mathrm{2}\to D\mathrm{4}$ cannot be scheduled in the same time slot. Multichannel communication is an efficient method for eliminating the second constraint by enabling concurrent transmissions over different frequencies.

In Figure 3(a), there is a network with 6 sensor nodes and the solid lines represent the tree edges, and the dashed lines represent the interfering links. JFTSS [10] schedules a network starting from the link that has the largest number of packets (load) to be transmitted. When the load of the adjacent links is equal, such as in aggregated convergecast, the most constrained link is considered first, that is, the link for which the number of other links violating the interfering and adjacency constraints when scheduled simultaneously is the maximum. Figure 3(b) shows the aggregated tree, which is scheduled by JFTSS. In JFTSS, the link (2, sink) is firstly assigned with frequency $F1$ and then the link (4,1) is scheduled to frequency $F2$ in the first slot. It is hard to have a distributed solution since the interference relationship between all the links must be known.

Figure 3

Illustrations of multiple frequency channels.

TMCP [11] partitions the network into multiple subtrees and minimizes the intratree interference by assigning different channels to the nodes residing on different branches starting from the top to the bottom of the tree. Figure 3(c) shows the same tree which is scheduled by TMCP to collect the aggregated data. Here, the nodes on the leftmost branch are assigned with frequency $F1$ , the nodes on the middle branch are assigned with frequency $F2$ , and the nodes on the rightmost branch are assigned with frequency $F3$ . After the channel assignments, time slots are assigned to the nodes according to the BFS-Time Slot Assignment algorithm.

At present, many tree-based topology control and routing algorithms are designed to aggregate and collect the sensing data; these are appropriate for the small-scale, short communication radius networks [12]. Multichannel communication is an efficient method to eliminate interference by enabling concurrent transmissions over different frequencies. But it is very difficult to assign channels to the tree network structure. Motivated by grid partition induction [13], we propose AASA-GP to schedule the aggregation process. In our algorithm, we firstly divide the network into grids based on the geography information and then allocate channels to the links based on grid coordinates. Nodes with the same grid coordinate using the same channel, adjacent grids using the other channels, which can effectively avoid the transmission interference thereby reduce the aggregate delay. To the best of our knowledge, it is the first time to use grid-based routing topology to solve aggregation latency.

The following lists our key findings and contributions:

• (1)

Use the tree-based topology to route and solve aggregation latency.

(2)

Allocate channel based on grid coordinates.

(3)

Algorithm is appropriate for large-scale wireless sensor networks with the large communication range.

3. Protocol Description

3.1. Basic Idea

By dividing the network into grids and assigning different channels to adjacent grids, the wireless transmission medium interference constraint is avoided, and the data from other source nodes in the same grid can be collected and aggregated on the selected cluster head and then proceed to the sink.

3.2. Meshing

In our scheme, we randomly select N wireless sensor nodes to construct wireless sensor networks in $S\times S$ square region. Sink (deployed at the right side of the network) broadcasts grid side length l to the wireless sensor networks, as shown in Figure 4; all nodes receive the message according to the location information and the grid side length to calculate its grid coordinates:

$$\begin{array}{cc}& Gx=⌊\frac{x}{l}⌋,\\ Gy=⌊\frac{y}{l}⌋,\end{array}$$

(1)

where $(Gx,Gy)$ indicates the grid coordinates, $(x,y)$ indicates the location coordinates of the nodes, and $⌊x/l⌋$ indicates the largest integer less than $x/l$ . The network is divided into $m=x^{\mathrm{2}}/l^{\mathrm{2}}$ grids, and the average number of nodes in each grid is $N\ast l^{\mathrm{2}}/x^{\mathrm{2}}$ .

Figure 4

Network mesh.

Each node broadcasts its grid coordinates, and the nodes with the same grid coordinates will form a cluster, in which the highest-energy node serves as the cluster head and receives the data from other members in this grid and then aggregates the data into a fixed-size packet.

Due to the limitations of half-duplex mode, nodes with the same grid coordinates cannot communicate with the cluster head at the same time, but nodes with the different grid coordinates can communicate through multiple channels to avoid wireless media transmission interference and increase the parallel transmission.

3.3. Channel Assignment

We assign different channels to adjacent grids, and the scheme of the channel assignment of the network is shown in Figure 5, in which ch1 indicates channel 1. According to this allocation, we assign 9 different channels to the entire network so that nodes in the different grid can transmit data at the same time. For example, in Figure 5, red grid is allocated channel 9 and its channel number is different from the adjacent grids. In this way, when nodes in the red grid communicate with cluster head, it is interference-free with the adjacent 24 grids, in which red dashed line passes through. The total number of grids in network is $x\ast x/l\ast l$ , and the number of channels is F, so the computational complexity of the channel assignment is $O(x^{\mathrm{2}}\ast F/l^{\mathrm{2}})$ .

Figure 5

Illustrations of channel assignment.

At the same time, we can adjust the size of the grid (grid side length l) in order to guarantee nodes in red grid and in green grid to transmit data in parallel, so that nodes that belong to different grids can transmit data without interference. After the in-grid data collection, cluster head can forward the sensed data across the other grids to sink.

3.4. Routing between Grids

Routing across the grids mainly involves the communication between cluster heads, and our routing scheme can be analyzed by following two cases according to the location of the sink.

In Figure 6, the example network is divided into a $8\ast 8$ grid. When sink locates at the center of the network, the route scheme of this grid is shown as the directed arrows in Figure 6(a). The number of the same channels indicates the number of the time slots; the same number indicates data in the two grids can be transmitted in parallel mode.

Figure 6

Illustrations of data forwarding between grids.

When sink is located in the center of the network, the route structure between grids is shown in Figure 6(b).

3.5. The Connectivity of the Network

Because of the limitation of communication capabilities of wireless sensor nodes, we assume that communication radius is $R_t$ ; the grid side length is L. To obtain a better network connectivity, the candidate cluster head must lie in the circular region whose center is the grid center and radius is R as shown in Figure 7.

Figure 7

Cluster head selection area.

3.5.1. Connectivity within the Grid

As shown in Figure 7, we suppose node A is the cluster head; if any node in the grid could communicate with A, we should make the $L_{\mathrm{1}}$ satisfy $L_{\mathrm{1}}\le R_t$ ; in other words, the following inequation should be satisfied. Consider

$$\begin{array}{cc}& R+\frac{\sqrt{\mathrm{2}}}{\mathrm{2}}L\le R_t.\end{array}$$

(2)

3.5.2. Connectivity between the Grids

In order to guarantee the adjacent cluster heads can communicate with each other, the maximum distance between two cluster heads should be less than the node communication radius $R_t$ . In Figure 8(a), $L_{\mathrm{2}}\le R_t$ (sink is in the center) or $L_{\mathrm{3}}\le R_t$ (sink is in the corner). That is,

$$\begin{array}{cc}& \mathrm{2}R+L\le R_t,\end{array}$$

(3)

$\begin{array}{cc}& \mathrm{2}R+\sqrt{\mathrm{2}}L\le R_t.\end{array}$

(4)

Figure 8

Connectivity between the grids.

However, as shown in Figure 8(b), node G and node H use the same channel 1; if they want to transmit the data in parallel mode, the grid side length L should be satisfied as in the following inequality:

$$\begin{array}{cc}& \mathrm{2}R\le R_t.\end{array}$$

(5)

When L and R are required to satisfy (3) or (4), they must satisfy (2).

In summary, when sink lies at the center or edge of the network, if the network connectivity is to be ensured, R, L, and $R_t$ should satisfy the following constraints:

$$\begin{array}{cc}& \mathrm{2}R+L\le R_t,\\ \mathrm{2}L\ge R_t.\end{array}$$

(6)

When sink is in the corner of the network, R, L, and $R_t$ should satisfy the following constraints:

$$\begin{array}{cc}& \mathrm{2}R+\sqrt{\mathrm{2}}L\le R_t,\\ \mathrm{2}L\ge R_t.\end{array}$$

(7)

In (6) and (7), node's communication radius $R_t$ is a constant, L and R are adjustable, and the greater the L is, the smaller the R is. Thus the number of cluster heads to choose is less; there may even be a grid that could not elect a cluster head, so it should make R as large as possible, so that there will be plenty of nodes you can choose to be cluster head and cluster head's energy consumption can be balanced. For example, when $R_t=\mathrm{30}$ , (6) can take $L=\mathrm{15}$ , $R=\mathrm{7.5}$ , as shown in Figure 8(c), and the nodes are located in the inscribed circle of this grid. When sink is located at the center or edge of the network, we make $L=\mathrm{0.5}{R}_t$ , $R=\mathrm{0.25}{R}_t$ . When sink is located in the corner of the network, we make $L=\mathrm{0.45}{R}_t$ , $R=\mathrm{0.2}{R}_t$ .

3.6. Network Topology of the Algorithm

According to the above algorithm description, we simulate a network in which the edge length is 200, the number of nodes is 800, the communication radius of node is 30, topology is shown in Figure 9, the red dots in each grid are cluster heads, the blue dot is sink, and the other dots are ordinary sensor nodes.

Figure 9

Network topology.

4. Simulation and Performance Analysis

4.1. Experiment Setup

We use C++ to simulate the following algorithms. Multichannel algorithms are JFTSS-channel: 2 (2 channels of JFTSS algorithm), JFTSS-channel: 16 (16 channels of JFTSS algorithm), TMCP-channel: 2 (2 channels of TMCP algorithm), TMCP-channel: 16 (16 channels of TMCP algorithm), our algorithm (9 channels). Single-channel algorithms are SDA and GGT. The routing architecture of our algorithm is based on grid, suitable for large-scale and large communication radius ( $R_t=\mathrm{30,40,50}$ ) wireless sensor networks. The topology structure of other algorithms is mainly based on the tree, and the node's communication radius of these algorithms is small ( $R_t=\mathrm{10,20,30}$ ). Due to differences in the application background, when our algorithm compared with other algorithms, we take $R_t=\mathrm{30}$ .

We randomly arrange N sensor nodes in a square area with the side length S; the average node density is $N/S^{\mathrm{2}}$ . For a randomly generated network topology, we use average node degree Φ to indicate the strength of the interference. Here, The greater the average degree of nodes is, the stronger the interference is.

4.2. Comparison with Other Algorithms

In our simulation, we set the average node density as $N/S^{\mathrm{2}}=\mathrm{0.02}$ . For $S=\mathrm{50,100,150,200,250}$ , we set $N=\mathrm{50,200,450,800,1250}$ , respectively. When the communication radius is set as $R_t=\mathrm{10,20,30,40,50}$ , the changes of Φ are shown in Figure 10.

Figure 10

Average degree of the network.

With the increase of node communication radius, the average degree of nodes also increases, so the network transmission interference also increases; this results in the increase of the aggregation delay.

Figure 11 shows the number of time slots needed when the number of nodes N varies from 50 to 1250 (i.e., S from 50 to 250), with the $R_t$ value of 10, 20, and 30. In Figure 11(a), sink is located in the center of the network, the grid side length of AASA-GP is $L=\mathrm{0.5}$ ,   $R_t=\mathrm{15}$ , and the average number of nodes in each grid is about 5. Due to the random arrangement, the distribution of nodes in each grid is not uniform which lead to the AASA-GP aggregate delay in the actual simulation process that is higher than the theoretical analysis. As shown in Figure 11(a), AASA-GP reduces the aggregation delay by 20 percent compared to that by TMCP-16 channels and 40 percent compared to GGT.

Figure 11

Performance comparison with fixed node density ( $R_t=\mathrm{30}$ , $\Phi \approx \mathrm{40}$ ).

In Figure 11(b), sink is located at the corner of the network; the grid side length of AASA-GP is $L=\mathrm{0.45}$ , $R_t=\mathrm{13.5}$ . The aggregate delay of each algorithm has increased to some extent; this is due to the increase of the distance between sink and the other nodes. AASA-GP is still significantly better than other algorithms; this reveals that AASA-GP is applicable to the different topologies and has a better performance in a wide range of applications.

4.3. Simulation of Large-Scale Wireless Sensor Networks

We simulate large-scale wireless sensor networks. S varies from 100 to 1000, with $R_t$ value of 30, 40, and 50, and the average node density is set constant as 0.02. In Figure 12(a), sink is located at the center of the network; when the network size increases, the aggregation delay of AASA-GP increases. According to the three curves in Figure 12(a), we find that the transmission interference increases when the node communication radius increases; the transmission interference also increases. But when the network size increases to a certain extent, the aggregate delay of $R_t=\mathrm{40}$ and $R_t=\mathrm{50}$ is less than the aggregate delay of $R_t=\mathrm{30}$ . This is due to the fact that the larger the node communication radius is, the greater the grid edge length is, which leads to the increasing of aggregate delay within the grid. However, at the same time, the number of grids decreases; the aggregate delay between grids reduces. When the network size increases, this decrease is more significant.

Figure 12

Performance for large-scale wireless sensor networks.

From Figure 12(b), we conclude that the variation trend of the aggregation network delay is similar to that shown in Figure 12(a), which indicates that AASA-GP can be applied to different network topologies.

5. Conclusions

This paper presents an adaptive aggregation scheduling algorithm based on the grid partition in large-scale wireless sensor networks (AASA-GP). By dividing the network into grids based on geographical information, when we assign the different channels to the adjacent grids, the wireless transmission interference can be avoided. By selecting the cluster head in each grid, the network load can be effectively balanced. Simulation results show that aggregation delay by AASA-GP is significantly less than that by the other algorithms. In wireless sensor networks, when the network scale and the node's communication radius are larger, the advantages of AASA-GP are more obvious.