VGDD: A Virtual Grid Based Data Dissemination Scheme for Wireless Sensor Networks with Mobile Sink

Abstract

Wireless sensor network (WSN) is considered as the enabling technology to bridge the gap between the physical and digital world. Some of the applications environments of WSN require a mobile sink to operate in the sensor field where delayed and/or partial data delivery might lead to inappropriate conclusions and thus require high quality of service in terms of latency and packets delivery ratio. Majority of existing mobile sink based data dissemination schemes aim to prolong network lifetime whereas few schemes improve the data delivery performance by employing multiple mobile sinks which add to the hardware and operating cost. In this paper we propose a virtual grid based data dissemination (VGDD) scheme that aims to optimize the tradeoff between network lifetime and data delivery performance while adhering to the low cost theme of WSN. Using the virtual structure, the proposed VGDD scheme follows a set of rules to disseminate sink's mobility updates in an energy efficient manner thereby maintaining nearly optimal routes. Furthermore, to cope with speed's variation of mobile sink, VGDD makes use of appropriate forwarder nodes for guaranteed data delivery. Simulation results reveal improved data delivery performance in terms of latency and data delivery ratio compared to existing work.

1. Introduction

Wireless sensor network (WSN) is considered as the enabling technology to bridge the gap between the physical and the digital world. In the last decade, WSNs have been successfully used in several monitoring applications and have reduced the human efforts in harsh and hostile environments. In traditional deployment of WSN, sensor nodes cooperatively monitor and report the phenomenon of interest to a static sink where the reported data is further analyzed and corrective measures are taken accordingly. However, the static sink scenarios give rise to hot-spot problem in the sink's vicinity which undermines the network lifetime. In addition, an adversary can easily target a static sink thereby disrupting the network operation [1]. To address the issues pertaining to static sink, the mobile sink concept was introduced in [2, 3] that leads to more balanced energy consumption among sensor nodes and also improves network connectivity in problematic areas. Since its inception, dozens of data dissemination schemes have been proposed that mainly aim to improve network lifetime thereby exploiting one or more mobile sink(s).

Several applications of WSNs require the sensed data to be delivered to the sink with high quality of service in terms of delay and data deliver ratio. Examples of such applications are the rescue operations in a postdisaster management system where a rescuer equipped with a smart-phone can obtain information about any survivor while on the move [4]. Similarly, in a battlefield environment, a commander or an unmanned aerial vehicle (UAV) can obtain real-time information about any intrusion of enemies, scale of attack, suspicious activities, and so forth via field sensors while on the move. In such applications delayed data delivery or low packet delivery ratio might lead to inappropriate conclusions which potentially offset the purpose of such networks.

There is always tradeoff between data delivery latency and nodes’ energy consumption. Unlike static sink scenarios, the network topology becomes dynamic as the sink keeps on changing its location [5]. To cope with the dynamic network topology, nodes need to be aware of the updated location of the mobile sink for efficient data delivery. Network-wide dissemination of sink's location updates helps to improve the data delivery performance to the mobile sink thereby facilitating dynamic routes adjustments. However, subject to sink's speeds the frequent dissemination of sink's location information causes high network control overhead which leads to extensive energy consumption. On the other hand, infrequent propagation of sink's location information leads to long data delivery paths in terms of hop-counts where packets are ultimately dropped due to expiry of time-to-live (TTL) period while chasing a mobile sink over an extended period of time. To optimize the tradeoff between the latency and nodes’ energy consumption, virtual infrastructure based data dissemination is considered as an efficient approach [6]. In the virtual infrastructure based data dissemination schemes, a set of designated nodes scattered in the sensor field are only responsible to keep track of sink's location. Such designated nodes gather the observed data from the nodes in their vicinity and then upon sink's discovery proactively or reactively report data to the mobile sink.

In this paper, a novel scheme called virtual grid based data dissemination (VGDD) is proposed for periodic data collection from WSN. Unlike majority of the existing solutions, VGDD aims to improve the data delivery performance using a single mobile sink while adhering to the low cost theme and self-organized nature of WSN. VGDD introduces several communication rules for dissemination of sink's topological updates that lead to least network control overheads while preserving nearly optimal data delivery routes. Moreover, unlike existing virtual structure based solutions, VGDD performs regular reelections for balanced energy consumption among sensor nodes. The least constraints on network operation and low computational complexity of VGDD make it a viable choice to be adopted in a broad range of applications. In the proposed scheme, initially the sensor field is partitioned into a virtual grid of K equal sized cells and constructs a virtual backbone network comprised of all the cell-headers. Nodes close to the centre of the cells are appointed as cell-headers, which are responsible for data collection from member nodes within the cell and route the data to the mobile sink using the virtual backbone network. The goal behind such virtual structure construction is to minimize the routes readjustment cost and improve the data dissemination performance to the mobile sink. The mobile sink moves along the periphery of the sensor field in circular fashion and communicates with the border-line nodes for data collection. The routes readjustment process is governed by a set of rules to dynamically cope with the sink mobility. Using VGDD, only a subset of the cell-headers need to take part in readjusting their routes to the latest location of the mobile sink thereby reducing the routes reconstruction cost. Using this strategy, nodes preserve nearly optimal routes to the latest location of mobile sink. Simulation results reveal improved data delivery performance of VGDD at different sink's speeds, data generation intervals, and network sizes as compared to other state of the art.

The rest of this paper is organized as follows: Section 2 describes the related work in context of data dissemination to a mobile sink in WSN. Section 3 presents our VGDD scheme in detail. To evaluate the performance of the VGDD scheme, simulation setup and performance evaluation are presented in Section 4. Finally, the paper is concluded in Section 5.

2. Related Work

Several mobile sink(s) based data gathering and data dissemination schemes have been proposed where the primary focus has been to improve the network lifetime. Based on the mobility pattern exhibited by the sink(s) in the sensor field, the schemes can fall in one of the two categories of controlled or uncontrolled mobility. In the former category, the sink's speed and direction is manipulated either by an external observer or in accordance with network dynamics. In uncontrolled mobility schemes, both the speed and direction of the mobile sink are independent of network dynamics and/or external observers. The relevant schemes in each of the aforementioned categories are briefly discussed in the following subsections.

2.1. Controlled Mobility Based Schemes

The primary focus of schemes in this category is to reduce the multihop communication and thus the energy consumption of the nodes in long-haul communication. In this category, one or more mobile sinks (also known as mobile data collectors) visit different segments of the network thereby enabling the sensor nodes to upload the sensed data directly on to one of the mobile sinks. The schemes in this category make maximum energy savings and largely improve the network lifetime; however the data delivery latency and packet delivery ratio is greatly compromised. The speed attained by a sink is extremely slow compared to electromagnetic propagation and in case of high rate of event generation, the ratio of successful data delivery to the mobile sink is greatly reduced as the buffered data is overridden by freshly sensed data [4].

Inspired by nonuniform nodes deployment where few pockets (high nodes density areas) exist in the sensor field, Kinalis et al. [1] introduced biased sink mobility based data collection with adaptive stop times. It aims to address the short contact time between the mobile sink and the source node thereby adapting the pause time of the mobile sink in accordance with the local data traffic. In the initialization phase, it constructs a lattice graph overlayed in the network area for network traversal. During sink's traversal, the sink stays relatively more at regions with high nodes density. To maintain fair network coverage, the sink maintains record of all the vertices and thus at the end of every pause interval, it favors its next move towards less frequently visited region. It maintains a good balance of energy efficiency and data delivery latency by making use of the adaptive pause intervals. Adjusting the pause interval in accordance with the nodes density reduces the latency for the nodes in neighborhood of the mobile sink, however may cause longer delays for nodes belonging to other network pockets.

Aioffi et al. [7] proposed an integrated clustering based virtual infrastructure and routing scheme to optimize the tradeoff between nodes’ energy consumption and data delivery latency. It employs multiple mobile sinks scheduled in different directions with the aim of reduce long-haul communication and the delivery latency. The cluster-head (CH) nodes collect data from its one hop neighbors and upload the buffered data upon discovering a sink in its communication range. All the mobile sinks share a common depot or gateway where the collected data is downloaded from time to time. It reduces the latency by scheduling the tours of multiple mobile sinks in different network segments thereby minimizing the waiting time of sensor nodes to upload their sensed data. The scheme improves network lifetime; however the data delivery latency is not significantly reduced as the speed of electromagnetic propagation is extremely fast compared to the physical speed of a mobile entity. In addition, the tight collaboration among multiple sinks in certain application environments, for example, battlefield, might not be feasible.

Mobile Sink based Routing Protocol (MSRP) is another clustered based protocol proposed by Nazir and Hasbullah in [8] that primarily aims to prolong the network lifetime. In MSRP, the mobile sink visits the set of CH nodes for data collection. MSRP aims to achieve balanced energy dissipation of sensor nodes and for that purpose the sink makes its next move towards the CH with relatively more residual energy. Although it improves the network lifetime thereby alleviating the hot-spot problem, however, it does not take into consideration the poor data delivery performance in terms of latency and packet loss ratio caused by the biased mobility. Using the residual energy based mobility strategy, it causes high data delivery latency for those network's segments where the event generation rate is relatively high as those network segments will be neglected due to low residual energy level.

To meet the real-time communication requirements of some of the applications, Banerjee et al. [9] proposed a scheme that makes use of multiple mobile CHs. The mobile CHs cooperatively operate to cover different network segments simultaneously and deliver the collected data to a single static base-station located at the centre of the sensor field. Furthermore, in order to reduce the multihop communication and the nodes energy consumption, it makes use of a hybrid strategy to move the individual CHs in the sensor field. Using the proposed strategy, CHs are first moved towards the event source and en-route nodes with relatively high residual energy are preferred. The hybrid strategy maintains a good balance between network lifetime and data delivery latency for few event sources. In situations where events occur simultaneously in different network segments, high packet losses and delivery latency are inevitable.

In order to reduce the data delivery latency and nodes’ energy consumption in readjusting the routes caused by sink mobility, Basagni et al. [10] proposed a scheme that is based on the heuristic called Greedy Maximum Residual Energy (GMRE). According to GMRE, the sink moves towards an energy rich site while taking into account the cost of data routes release and establishment associated with the sink mobility to that site. If all the conditions are favorable, the sink greedily moves to the new site; otherwise it will reside at its current site. The residual energy of nodes within a site is determined by a sentinel node appointed by the sink which on demand collects and provides such information to the mobile sink. This scheme improves network lifetime; however, nodes belonging to low residual energy sites are always neglected which causes high packet loss ratio and extremely large data delivery latency.

To harvest data from sensor nodes in short amount of time using single hop communication, Sugihara and Gupta proposed a controllable data mule based scheme in [11]. Similar data mule based approaches can be found in [12], where the data mule is considered as an alternative solution for multihop communication. The proposed scheme first determines a schedule of the data mule using the Travelling Salesman Problem (TSP) tour T. Next it makes use of approximation algorithm to apply shortcutting to T that results in shortest label-covering tour. The proposed scheme yields good results in small size networks where nodes are sparsely distributed; however, for large size networks or denser nodes deployment traversing all nodes without redundant paths becomes infeasible. In case of large scale networks, nodes would suffer from high data delivery latency as well as high packet loss ratio.

2.2. Uncontrolled Mobility Schemes

Uncontrolled sink mobility is characterized by the fact that the sink's movement is independent of the network dynamics. In the following lines, we briefly describe some of the relevant schemes belonging to this category.

Chen et al. [13] presented a converge-cast tree algorithm called Virtual Circle Combined Straight Routing (VCCSR) that constructs a virtual structure comprised of virtual circles and straight lines. A set of nodes are appointed as CH nodes along these virtual circles and straight lines. Together the set of CHs form a virtual backbone network. The sink circulates the sensor field and maintains communication with the border CHs for data collection. The CHs in VCCSR follow a set of communication rules to minimize the routes readjustment cost in propagating the sink's latest location information. VCCSR also defines a set of reference points which whenever crossed by the mobile sink triggers the routes readjustment process. A large number of CH nodes take part in the routes readjustment process which generates extensive network overhead. The high network overhead caused by sink mobility adversely affects the data packets in transit and thus remarkably drops the successful data delivery ratio.

Data-Driven Routing Protocol (DDRP) proposed by Shi et al. [14] aims to improve data delivery performance to a mobile sink while minimizing the network control overhead. DDRP avoids direct propagation of sink's location updates where the sink periodically informs its direct neighbors only. Each data packet carries an extra field signaling the hop-count to the mobile sink. In case of data delivery to the mobile sink by its single-hop neighbors, the data packet is also overheard by the neighbor nodes which accordingly adjust their routing entries. DDRP greatly reduces network control overheads caused by sink mobility. The data delivery performance is greatly affected by the duty-cycle of sensor nodes as it requires the nodes to be in idle listening mode for overhearing the sink's location update. Furthermore, the data packets experience considerable end-to-end delay as data delivery paths need to be established first due to the sink mobility. Overall the data delivery performance is severely affected by sink's speed whereas high sink's speed invalidates existing data delivery paths thereby resulting in high packet losses.

Elastic routing introduced by Yu et al. [15] aims to minimize control traffic and provide guaranteed data delivery to a mobile sink. It assumes the nodes to be location-aware and initially the source nodes determine the sink's location through some mechanism. For data forwarding to the mobile sink, it adopts greedy forwarding approach. To address the sink mobility in the middle of data delivery, the sink through beacon messages not only informs its new neighbors but also the nodes from which it received the last packets. Furthermore, for necessary routes adjustments, it exploits the overhearing mechanism for informing the nodes along the reverse geographic routing path back to the source nodes about the sink's location updates. Elastic routing minimizes network control overhead caused by sink mobility; however, the overhearing feature itself is a major consumer of node's energy reserve. Moreover, the only mechanism for the farter source nodes to converge to the new location of the sink is through the step-by-step overhearing feature, thereby causing huge data delivery latency.

In the scheme proposed by Lee et al. [16] data delivery is ensured by exploiting the knowledge of the possible trajectories of the mobile sinks. It is based on the fact that in certain scenarios, motion patterns like trails, roads, and hallways define the future trajectories of a mobile sink and therefore, in the protocol initialization phase, a set of likely trajectories are broadcasted to the entire network. Using this scheme, nodes do not report data directly to mobile sinks but rather route the sensed data to a set of relays which are located along the mobile sink's trajectories. The forwarded data is stashed at the relays till it is uploaded to a mobile sink upon coming in contact with. To ensure guaranteed data delivery, sensed data is routed to multiple stashing points where each trajectory must have at least one stashing point. However, the guaranteed data delivery to mobile sinks comes at the expense of multiple redundant transmissions destined for different trajectories.

Based on the literature review, it is revealed that majority of the existing schemes exploit sink mobility for prolonging network's lifetime thereby minimizing the chances of hot-spot formation. However, there are various mission critical applications such as emergency relief operations after a catastrophic incident and battlefield environments which require the sensory data to be promptly propagated to the mobile sink. In such applications, delayed and/or partial data delivery may lead to inappropriate conclusions about the event(s) thereby compromising the potential benefits of such networks. Some of the existing schemes mitigate data delivery latency and packet loss ratio by employing multiple mobile sinks which not only add to the hardware and operating cost but also cannot be realized in several operating environments such as battlefields and forests. In addition, multiple mobile sinks also require tight collaboration and time-synchronization in order to avoid redundant coverage of overlapped network segments. Few of the schemes improve data delivery performance using a single mobile sink; however the imposed constraints on nodes placement and sink mobility limit the widespread applicability of such schemes. In addition, the controlled sink mobility based schemes yield great energy savings thereby reducing long-haul communications; however, the long waiting time in large network sizes adds to high delivery latency and packet loss ratio. The main contribution of this paper is to propose a virtual grid based data dissemination scheme that improves the data delivery performance using a single mobile sink without demanding specialized resources on part of the sensor nodes. It optimizes the tradeoff between the nodes energy consumption and data delivery performance by enabling the sensor nodes to maintain nearly optimal routes to the latest location of mobile sink at the cost of little network control overhead. We extend the algorithms presented in a preliminary version of this paper [17] thereby evaluating the performance of the proposed scheme at different traffic generates rates, speed's variation of mobile sink, and different network's sizes.

3. The VGDD Scheme

This section presents detailed description of our VGDD scheme, including how to construct and maintain the virtual infrastructure for efficient data dissemination to the mobile sink. Initially, based on the total number of nodes, the sensor field is partitioned into various equal sized cells. The rationale behind such partitioning is to facilitate efficient load balancing which consequently improves the network's lifetime and data delivery performance. This criterion of network partitioning results in a dynamic virtual infrastructure that is scaled in accordance with the network size. In addition, partitioning the sensor field on the basis of total number of deployed nodes also helps to reduce contention for the wireless medium access in the data dissemination phase which has a great influence on data delivery latency and delivery success ratio. In each cell, node closed to the centre of the cell is elected as cell-header. After cell-headers election in each cell, the rest of the nodes based on their spatial location join the nearest cell as member nodes. The member nodes forward the sensory data to their respective cell-headers. The neighboring cell-headers exchange information via gateway nodes. The elected cell-headers along with the gateway nodes form a virtual infrastructure for exchanging the sink's location updates as well as data dissemination to the mobile sink. Together the set of cell-headers maintain location updates of the mobile sink thereby relieving the rest of the sensor nodes from keeping track of the mobile sink. Furthermore, following a set of communication rules, only a limited number of cell-headers take part in the routes readjustment process thereby reducing the network control overhead. The partial routes readjustment strategy not only helps to conserve nodes energy but also maintains nearly optimal routes for the subsequent data dissemination to the mobile sink.

3.1. Network Characteristics

The following network characteristics are assumed for the operation of VGDD scheme. (i)

Nodes after random deployment remain static and acquire location information.

(ii)

Transmission power of the nodes can be adapted in accordance with distance to destination pair.

(iii)

All the sensor nodes except the sink have the same energy level and throughout remain static whereas the mobile sink does not have any resource constraints.

(iv)

A single mobile sink moves counterclockwise around the sensor field and performs periodic data collection using nodes along its trajectory.

(v)

Nodes have no knowledge about the speed or schedule of mobile sink.

3.2. Construction of Virtual Infrastructure

In the initialization phase of VGDD, the sensor field is partitioned into several uniform sized cells where the total number of cells is a function of the nodes density. The aim behind such partitioning is efficient load balancing which consequently improves network lifetime and data delivery performance.

In order to determine the optimal number of cells, we adopt the heuristics used in LEACH [18], TEEN [19], and APTEEN [20] which consider 5% of the total number of sensor nodes as the cluster-heads. Unlike fixed partitioning of the sensor field (as in [13]), our VGDD scheme performs dynamic network's partitioning on the basis of density of deployed nodes. Partitioning the network into fixed number of cells irrespective of nodes’ density greatly deteriorates the data delivery performance and network's lifetime. In dense nodes deployment, having few large sized cells overwhelms the cell-header thereby requiring frequent reelections. In addition, nodes in disseminating data to the mobile sink via the cell-header would experience more delays and packet losses due to high congestion. On contrary, having large number of small sized cells would trigger frequent dissemination of sink's topological updates thereby increasing network's control overheads. Therefore, to further optimize the tradeoff between network's lifetime and data delivery performance, our VGDD scheme dynamically partitions the network into various equal sized cells on the basis of total number of nodes. Given N number of nodes deployed in a sensor field, first our VGDD scheme partitions the sensor field into K uniform sized cells using (1), where K is a squared number. Figures 1(a), 1(b), and 1(c) show network partitioning into various uniform sized cells for $N = 100$ , 200, 300, respectively:

\begin{matrix} K = \{\begin{cases} 4 & N \times 0.05 \leq 6 \\ 9 & 6 < N \times 0.05 \leq 12 \\ 16 & 12 < N \times 0.05 \leq 20 \\ 25 & 20 < N \times 0.05 \leq 30 \\ ⋮ & ⋮ \end{cases} \end{matrix}

(1)

Figure 1

Network partitioning on the basis of total number of nodes.

After partitioning the network, the VGDD scheme performs cell-header election in each cell. Initially, considering uniform energy level of all the nodes, priority is given to the node which is relatively close to the mid-point of the cell in the cell-header election process. Nodes compute the mid-points of all the cells by making use of the knowledge of sensor field's dimension and total number of nodes. To reduce the communication cost and elect the node at the most appropriate position within the cell as the cell-header, only those nodes participate in the election process whose distance to the mid-point of the cell is less than a certain threshold. In case if no suitable candidate node can be found inside the search zone around the mid-point of the cell, the threshold distance is progressively increased. Each elected cell-header floods the local cell with its status information in a controlled manner by broadcasting a notification-alert message. The notification-alert contains information such as ID of the elected cell-header, location information, and Cell-ID in which it resides. Nodes upon receiving this message set the sender as their next-hop node and further share this information with their neighbors till all the nodes in the cell are informed about the cell-header notification within the cell. The notification-alert message is discarded by nodes incase if their Cell-ID is different. After electing the cell-headers in each cell, next the neighboring cell-headers form adjacencies with each other via the gateway nodes. Each cell-header exploiting the location information of its neighbor member nodes together with knowing the central-points of adjacent cells chooses appropriate gateway nodes. The maximum number of adjacent cell-headers for a border-line cell-header is 3 whereas for an inside cell-header is 4. The set of cell-header nodes together with the gateway nodes constructs a chain-like virtual infrastructure as shown in Figure 2.

Figure 2

Example of virtual infrastructure after establishing adjacencies.

Next after the virtual infrastructure construction, data dissemination routes are set up considering the mobile sink is positioned in the premises of cell 1. As a result of the initial routes setup, all the cell-headers adjust their routes to the initial position of the mobile sink. In addition, the information of all the cell-headers is forwarded to the mobile sink for future correspondence. Figure 3 shows an example of the virtual infrastructure after the initial routes setup when the sensor field is partitioned into 16 cells.

Figure 3

Example of virtual infrastructure after initial routes setup.

3.3. Dynamic Routes Adjustment

In order to ensure prompt and reliable data dissemination to a mobile sink, nodes need to keep track of the latest location of the mobile sink. For periodic data collection from sensor field, the mobile sink moves counterclockwise around the sensor field and periodically broadcasts beacon messages to the nodes along its trajectory. Upon receiving the beacon messages from sink, nodes inform their respective cell-headers; however multiple beacon messages received within certain time-frame ( $Δ t$ ) are discarded. Once the mobile sink is discovered via the beacon message either directly from the mobile sink or through member nodes; the closest cell-header becomes the originating cell-header (OCH) and assumes the responsibility of exchanging sink's location information with other cell-headers in a controller manner. To minimize network control overhead and thus conserve nodes energy, a virtual grid based dynamic routes adjustment (VGDRA) scheme is used that follows a set of rules for disseminating sink's location updates. Using these rules, cell-headers constituting only a partial segment of the virtual infrastructure participate in the routes readjustment process. The rationale behind the partial routes adjustments is to pick only those cell-headers which can potentially shorten the data delivery route. The communication rules for disseminating sink's topological updates are described as follows.

Rule 1.

Nodes upon receiving beacon messages from mobile sink update their respective cell-headers; however multiple copies received within a predefined time-interval are discarded to avoid unnecessary communications.

Rule 2.

Upon discovering the mobile sink, the cell-header does not further share the sink's location update in case if its status is already set to OCH. Otherwise, it changes its status to OCH and executes Rule 3.

Rule 3.

The current OCH sends updates to the previous OCH and its immediate downstream cell-header about the sink's location information.

Rule 4.

The previous OCH upon receiving the sink's location update from current OCH adjusts its data delivery route by setting the current OCH as its next-hop cell-header towards the mobile sink.

Rule 5.

Upon receiving the location update, the immediate downstream cell-header first verifies whether its previous next-hop cell-header towards the mobile sink is the same as the source cell-header or not. In case of a match, the packet is dropped; otherwise, it sets the source cell-header as its next-hop cell-header towards the mobile sink and further informs its immediate downstream cell-header. Each immediate downstream cell-header follows the same procedure until all the downstream cell-headers update their routes in accordance with current position of mobile sink.

Figure 4(a) shows an example of the data delivery routes when the mobile sink is located in premises of cell 2. When the mobile sink moves from cell 2 to cell 3, the cell-header at cell 3 becomes OCH and exercises Rules 3 and 4 to update the cell-header at cell 2, followed by Rule 5 to update its downstream cell-headers, that is, 7, 11, and 15 as shown in Figure 4(b). Using this strategy, nearly optimal data delivery routes are maintained to the latest location of mobile sink while only a limited number of nodes take part in routes maintenance process thereby reducing the overall network control overhead.

Figure 4

Example of routes readjustments along sink mobility.

Similarly, Figure 5 illustrates how the cell-header in cell 4 avoids unnecessary dissemination of sink's location updates by exercising Rules 1 and 2 when a mobile sink changes its position from point A to B within the same cell. Using Rules 1 and 2, it helps to cope with speed's variation of mobile sink and avoid advertisements of frequent topological updates. By avoiding the unnecessary dissemination of sink's location updates, it helps to improve network lifetime and reduce network congestion.

Figure 5

Example of avoiding undesired dissemination of sink's location updates.

The algorithm that governs the routes adjustment process along the sink mobility is described in detail in Algorithm 1 whereas a graphical depiction is given in Figure 6.

Algorithm 1: Sink discovery and routes readjustment using VGDRA scheme.

(1) Mobile Sink (MS) periodically broadcasts beacon message

(2) if beacon message is received before expiry of timer

(3) drop the packet

(4) else

(5) {

(6) if receiving node is not a Cell-Header (CH)

(7) {

(8) set MS as the Next_Hop

(9) send location update packet to respective CH

(10) }

(11) if CH is already Originating Cell-Header (OCH)

(12) {

(13) set Sender of the packet as Next_Hop

(14) drop the packet

(15) }

(16) else

(17) {

(18) CH becomes Originating Cell-Header (OCH)

(19) The new OCH sends a route update packet to previous OCH

(20) Previous OCH sets the new OCH as its Next_Hop towards MS

(21) The new OCH also sends a route update packet to its immediate downstream CH

(22) foreach downstream CH upon receiving route update packet

(23) {

(24) if the previous Next_Hop of CH towards MS is not the Current Sender

(25) {

(26) set the Sender of the packet as Next_Hop of CH towards MS

(27) if next downstream CH is not NULL

(28) Current CH sends route update packet to its immediate downstream CH

(29) else

(30) drop the packet

(31) }

(32) else

(33) drop the packet

(34) }

(35) }

(36) }

Figure 6

Flowchart of VGDRA scheme.

3.4. Data Forwarding

Nodes upon sensing the event in their proximity greedily forwards the data packets to mobile sink if directly reachable using default radio settings. However, if the mobile sink is outside the radio coverage area, nodes adopt single-hop or multihop communication (depending upon their placement) to forward the sensory data to the respective cell-headers. From that point onwards it makes use of the VGDRA algorithm for routes determination to the mobile sink and accordingly forwards the data to next-hop node learned through VGDRA algorithm. Finally, when the data packets reach the destination cell-header, the network topology is reassessed. The destination cell-header first checks whether the mobile sink is currently in its coverage range and greedily forwards the data to the mobile sink if directly reachable. It might be the case that the mobile sink has not moved to another cell but is outside the radio coverage range of the source cell-header. In such situation, the source cell-header exploits the geographical location information of the member nodes and chooses appropriate forwarder node along the trajectory of the mobile sink for data delivery. The forwarder node upon receiving the data packets from its cell-header accordingly delivers the data to the mobile sink. Figure 7 illustrates data dissemination through the forwarder node shown in red color. Finally, the mobile sink might be far away in the premises of another cell other than the source cell-header, in such case the data packets are forwarded to the next-hop cell-headers learnt through the VGDRA algorithm. Algorithm 2 is used to carry out data dissemination to a mobile sink using the VGDD scheme whereas the graphical illustration of VGDD scheme is given in Figure 8.

Algorithm 2: Data dissemination using VGDD scheme.

(1) Source node upon sensing the event, generates data packets

(2) if mobile sink (MS) is directly reachable

(3) send data packets directly to MS;

(4) else

(5) {

(6) Source node forwards data packets to closest cell-header (CH)

(7) Each CH learns route to MS using VGDRA algorithm

(8) foreach source CH

(9) {

(10) if MS is within radio coverage range

(11) send data packets directly to MS;

(12) else if MS is still in the same cell but not directly reachable

(13) {

(14) if MS has not yet approached

(15) set forwarder node in reverse direction of MS trajectory;

(16) else

(17) set forwarder node along MS trajectory;

(18) send data packets to forwarder node;

(19) }

(20) else

(21) {

(22) send data packets to next-hop CH learnt through VGDRA algorithm;

(22) }

(24) }

(25) }

Figure 7

Example of data forwarding using forwarder node.

Figure 8

Flowchart of data dissemination process.

3.5. Cell-Header Role Rotation

An integral part of the virtual infrastructure based data dissemination scheme is rotating the role of the cell-header in every cell. The cell-header being the local data collector and actively taking part in routes readjustment process is vulnerable to high energy dissipation and therefore its role needs to be progressively shifted to other nodes within the cell. In order to achieve uniform energy dissipation, the VGDD scheme keeps track of the residual energy level of the current cell-header. A new cell-header election is initiated under the supervision of the current cell-header in the case if its residual energy level gets below a certain threshold (e.g., 20% of the residual energy level by the time the cell-header is elected). The current cell-header floods its cell asking the nodes to respond with their residual energy level (Res_ $E_{node_i}$ ) as well as their relative distance to the central-point of the cell (D). Accordingly, the nodes respond with the requested information. For the new cell-header election, a multiobjective optimization technique similar to lexicographic optimization (LO) [21] is used which takes into account the nodes’ residual energy and their distances to the central-point of the cell. In the reelection process, residual energy of the candidate nodes is given higher priority as compared to their relative position in the cell. The current cell-header first selects a set of nodes (LQN[ ]) whose residual energy is above the threshold level and then selects that node as the new cell-header that is relatively more close to the central-point of the cell. It might happen that with the passage of time no node can be found qualifying the default residual energy level. In such situations, the residual energy threshold is slightly decreased. Upon electing the new cell-header, the current cell-header before stepping down shares the information of the new cell-header with all the member nodes for membership adjustments. The reelection process is governed by following Algorithm 3. The graphical illustration of the steps undertaken in cell-header reelection process is presented in Figure 9.

Algorithm 3: Cell-header reelection.

(1) Current CH initiates re-election by broadcasting a request packet

(2) foreach node upon receiving CH's request packet

(3) do

(4) if (node's Cell-ID $= =$ CH's Cell-ID) AND (next-hop $= =$ CH node)

(5) send response (residual energy and distance to central-point) directly;

(6) send the CH's request packet to neighbor nodes;

(7) else if (node's Cell-ID $= =$ CH's Cell-ID) AND (next- hop != CH node)

(8) send response via next-hop node to the CH;

(9) send the CH's request packet to neighbor nodes;

(10) else if (node's Cell-ID != CH's Cell-ID)

(11) drop the packet and do not further propagate;

(12) end if

(13) end for

(14) /^* After collecting nodes information, select appropriate new cell-header. ^*/

(15) Let the response is collected from M number of nodes.

(16) $K = 0$ ;

(17) foreach node $i \in [1 : M]$

(18) do

(19) if (Res_ $E_{node_i}$ > Res_ $E_{Threshold}$ )

(20) $K = K + 1$ ;

(21) LQN[K] = node_i;

(22) end if

(23) end for

(24) if (LQN $[]$ != NULL)

(25) Min_ $D_{CP}$ = distance between central-point and LQN $[1]$ ;

(26) foreach node $j \in [2 : K]$

(27) do

(28) D = distance between $j th$ node i.e., LQN $[j]$ and central-point;

(29) if ( $D < Min_D_{CP}$ )

(30) Min_ $D_{CP}$ = D;

(31) New-CH = LQN $[j]$ ;

(32) end if

(33) end for

(34) else

(35) Res_ $E_{Threshold}$ = Res_ $E_{Threshold}$ − (Res_ $E_{Threshold}$ /10);

(36) Repeat the process from Step no. (16)

(37) end if

Figure 9

Flowchart of cell-header reelection process.

4. Performance Evaluation

This section presents the simulation setup and results. In order to evaluate the performance of the proposed VGDD scheme, simulations were carried out using NS-2.35. We compared the performance of our VGDD against VCCSR and DDRP. A common point among all of them is the uncontrolled sink mobility feature where the sink moves independently of the network dynamics.

4.1. Simulation Setup and Performance Metrics

In all our experiments, we considered a squared-sized sensor field of 200 × 200 m² dimension where nodes are randomly deployed. We changed the number of nodes from 100 to 400 for scalability testing purposes. All the nodes transmit and receive packets using IEEE 802.15.4 MAC protocol. All the sensor nodes have uniform communication range of 30 m. We assumed the two-ray ground propagation model which represents a relatively practical channel model. A single mobile sink circles the sensor field in counterclockwise fashion and generates hello packets every one second. Neighboring nodes discover the mobile sink through hello packets. Nodes periodically generate data packets at regular intervals and report to the mobile sink using the respective routing scheme. We used the energy model used in [19] with one exception of $d^{4}$ path loss instead of $d^{2}$ . We ran the simulation for 1000 s, where the first 10 s was allocated to virtual backbone structure construction phase. Nodes stopped generating data at 980 s.

In our experiments, we used three different metrics to evaluate the performance of the VGDD against the other schemes: data delivery ratio, latency, and average energy consumption. The data delivery ratio is termed as the ratio of the total number of successfully received data packets at the sink to the total number of generated packets by the source nodes. It is a measure of the routing efficiency of a data dissemination scheme. Data delivery latency is a measure of the end-to-end delay when the data packets are generated at the sensor nodes till they are received at the sink. The average energy consumption is a measure of the total energy consumed by all the nodes divided by the total number of nodes till the simulation lasts its configured time.

4.2. Simulation Results

The following subsections describe the performance of VGDD in terms of the three metrics under different network dynamics.

4.2.1. Impact of Traffic Generation Rate

This subsection presents the performance of VGDD and the other protocols at different data generation rates. We varied the data interval from 5 to 30 s and kept the velocity of the mobile sink constant at 10 m/s. Figure 10 shows the performance in terms of data delivery ratio for a network of 300 nodes. Due to the least control overheads in VGDD, the packets loss ratio is significantly low even at data generation intervals of 10 s and less. The VCCSR performance rapidly decreases at such intervals due to high number of both control and data packets which results in network congestion and packet losses. On the other hand, the data delivery ratio of DDRP improves at high data generation rates as shown in Figure 10 mainly because of the data-driven feature of the forwarding strategy. However, compared to our VGDD and VCCSR, the overall success ratio of DDRP is very low as a high number of packets are ultimately dropped due to expiry of TTL field while chasing the mobile sink.

Figure 10

Data delivery ratio versus data generation interval.

Figure 11 shows the data delivery latency of a network of 300 nodes at different data intervals. The VGDD outperforms DDRP due to the prompt propagation of sink's location updates. In terms of latency, VCCSR closely follows VGDD as both the schemes perform continuous routes readjustments and maintain fresh routes towards the latest location of the mobile sink. Unlike fixed network partitioning of VCCSR, the VGDD results in a scalable virtual infrastructure which consequently poses less network's congestion thereby reducing the medium access delay. In DDRP, due to its data-driven nature, nodes progressively come to know about the location information of the mobile sink and thus due to long convergence time, the data delivery latency is significantly increased.

Figure 11

End-to-end delay versus data generation interval.

Similarly, Figure 12 illustrates the average energy consumption of nodes in disseminating data to the mobile sink. Using the set of communication rules proposed by VGDD, only a limited number of cell-headers take part in routes readjustment process thereby reducing the overall energy consumption cost. Furthermore, due to the continuous routes readjustment strategy of VGDD, nodes make use of nearly optimal routes in the data dissemination phase. Together these two strategies help to reduce overall energy consumption of nodes in disseminating data to the mobile sink. In VCCSR, a high proportion of cluster-heads take part in routes readjustment process thereby increasing the overall energy consumption. The DDRP performs better as compared to VGDD and VCCSR, mainly because it avoids active propagation of sink's topological updates and exploits the overhearing feature of wireless medium. The DDRP saves nodes energy consumption by avoiding active propagation of sink's location information; however, to observe the tradeoff, it pays for the high data delivery latency and packet loss ratio.

Figure 12

Average energy consumption versus data generation interval.

4.2.2. Impact of Sink's Speed

This subsection describes how VGDD reacts at different sink's speeds. In this experiment, the sink's speed was varied from 2 to 15 m/s. The network size was chosen as 300 nodes where the nodes’ data generation interval was kept at 10 s. In terms of data delivery ratio, at different sink's speeds, the performance of VGDD against other schemes has been shown in Figure 13. It can be seen that the data delivery ratio of VGDD remains consistent even at higher sink's speeds whereas the performance of VCCSR and DDRP deteriorates at 10 m/s and above. The relatively better performance of VGDD can be attributed to least control overheads caused by sink mobility and active route readjustments resulting in high packet delivery ratio. Compared to our VGDD, the data delivery ratio of VCCSR significantly reduces at higher sink's speed due to high number of control packets and network congestion. The DDRP badly performs at higher sink's speed where most of the data packets are ultimately dropped due to expiry of TTL value while chasing a fast moving sink.

Figure 13

delivery success ratio versus speed of mobile sink.

Figure 14 shows the data delivery latency of VGDD compared to other schemes at different sink's speeds. Due to fast convergence time of disseminating sink's mobility updates, the subsequent data delivery latency is greatly reduced using VGDD. Similarly, the VCCSR produces comparable results due to active routes maintenance. On the other hand, data packets using DDRP suffer from high latency while chasing the sink at higher speeds mainly due to its slow convergence time in notifying the sink's latest mobility update to the sensor nodes.

Figure 14

End-to-end delay versus speed of mobile sink.

In terms of average energy consumption, DDRP yields better results at different sink's speeds compared to VGDD and VCCSR as shown in Figure 15. Unlike DDRP, both VGDD and VCCSR actively keep track of sink's mobility updates and perform regular routes readjustments at the cost of more communications. In VCCSR, frequent relocation of sink causes high network control overheads where a major proportion of cluster-heads takes part in routes readjustments. On the other hand, DDRP avoids explicit propagation of sink mobility updates and employs the overhearing mechanism for sink discovery, thereby conserving nodes energy. The VGDD despite the active routes maintenance along sink mobility closely follows the DDRP in overall energy consumption due to least network control overheads.

Figure 15

Average energy consumption versus speed of mobile sink.

4.2.3. Impact of Network Size

This subsection evaluates the scalability feature of VGDD when exposed to different network sizes. In this experiment, the sink's speed was kept at 10 m/s and the nodes generate sensory data at 10 s interval. Figure 16 shows the performance of VGDD in terms of data delivery ratio where the total numbers of nodes are varied from 100 to 400. It can be seen that unlike others, our VGDD maintains relatively high data delivery ratio as the number of nodes are increased. The reason is the philosophy of constructing the virtual structure on the basis of total number of nodes where the number of cells is increased as the network size grows. The data delivery ratio of VCCSR gradually decreases as the network size increases mainly because it uses fixed number of cluster-heads irrespective of the number of nodes and as a result network congestion increases in accordance with the network size. Similarly, the DDRP demonstrates very poor performance where the packets drop ratio is increased in accordance with the number of nodes due to the long traversal time of the data packets, increased contention for wireless medium access, and more hop-counts.

Figure 16

Delivery success ratio versus number of nodes.

Figure 17 illustrates the data delivery latency of the various schemes at different network sizes. The latency of VGDD gradually increases as the network size grows. The reason is as the network size grows, the data packets traverse more hop-counts. The VCCSR demonstrates similar performance where its data delivery latency is slightly higher than our VGDD due to network congestion and medium access delay when more nodes are added under the administration of the same cluster-heads. Unlike fixed network partitioning in VCCSR, the VGDD partitions the network into cells on the basis of number of nodes. On the other hand, the DDRP gives very poor performance in terms of data delivery latency mainly due to the long convergence time and more hop-counts as the network size grows.

Figure 17

End-to-end delay versus number of nodes.

In terms of overall energy consumption at different network sizes, the DDRP performs better than VGDD and VCCSR, as shown in Figure 18. Unlike DDRP, both the VGDD and VCCSR actively keep track of sink's mobility and perform regular routes readjustment according to latest location of the mobile sink. The routes readjustment strategy of VGDD and VCCSR improves the data delivery performance but at the expense of more communications and thus consume relatively high energy compared to DDRP. On contrary, DDRP relies on overhearing feature for sink discovery thereby avoiding direct propagation of sink's topological updates. However, the passive manner of sink's discovery causes nodes to experience more latency and packets loss as compared to VGDD when reporting data to mobile sink.

Figure 18

Average energy consumption versus number of nodes.

5. Conclusion

In this paper, we proposed a novel scheme called virtual grid based data dissemination (VGDD) for periodic data collection from sensor network. Initially, it partitions the sensor field into a virtual grid of uniform sized cells where the total number of cells is determined in accordance with the number of nodes. It dynamically elects a cell-header in each cell and together the set of cell-headers forms a virtual infrastructure for dissemination of both sink's location updates as well as data packets. After the virtual structure construction, a mobile sink circles the sensor field counterclockwise and maintains communication with nodes along its trajectory for data collection. To keep with dynamic network topology caused by sink mobility, VGDD proposes a set of communication rules. Following the proposed communication rules, only a limited number of cell-headers take part in routes readjustment process thereby causing minimal network control overhead while preserving near optimal data delivery routes. Furthermore, to cope with speed's variation of mobile sink, VGDD selects appropriate forwarder nodes along trajectory of mobile sink for guaranteed data delivery. Simulation results demonstrate improved data delivery performance of VGDD at different sink's speeds, data generation intervals, and network sizes as compared to existing work.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

The authors would like to extend their sincere appreciation to the Deanship of Scientific Research at King Saud University for funding this research.

References

Kinalis

Nikoletseas

Patroumpa

Rolim

Biased sink mobility with adaptive stop times for low latency data collection in sensor networks

Information Fusion 2014 15 1 56 63

10.1016/j.inffus.2012.04.003

2-s2.0-84885949027

Chakrabarti

Sabharwal

Aazhang

Using predictable observer mobility for power efficient design of sensor networks

Proceedings of the 2nd International Conference on Information Processing in Sensor Networks (IPSN '03)

2003

Palo Alto, Calif, USA

129 145

Shah

R. C.

Roy

Jain

Brunette

Data MULEs: modeling and analysis of a three-tier architecture for sparse sensor networks

Ad Hoc Networks 2003 1 2-3 215 233

10.1016/s1570-8705(03)00003-9

2-s2.0-3242765057

Khan

A. W.

Abdullah

A. H.

Anisi

M. H.

Bangash

J. I.

A comprehensive study of data collection schemes using mobile sinks in wireless sensor networks

Sensors 2014 14 2 2510 2548

10.3390/s140202510

2-s2.0-84893671245

di Francesco

Das

S. K.

Anastasi

Data collection in wireless sensor networks with mobile elements: a survey

ACM Transactions on Sensor Networks 2011 8 1, article 7

10.1145/1993042.1993049

2-s2.0-80052978346

Hamida

E. B.

Chelius

Strategies for data dissemination to mobile sinks in wireless sensor networks

IEEE Wireless Communications 2008 15 6 31 37

10.1109/mwc.2008.4749745

2-s2.0-70350277836

Aioffi

W. M.

Valle

C. A.

Mateus

G. R.

Da Cunha

A. S.

Balancing message delivery latency and network lifetime through an integrated model for clustering and routing in wireless sensor networks

Computer Networks 2011 55 13 2803 2820

2-s2.0-79961022143

10.1016/j.comnet.2011.05.023

Nazir

Hasbullah

Mobile Sink based Routing Protocol (MSRP) for Prolonging Network Lifetime in Clustered Wireless Sensor Network

Proceedings of the International Conference on Computer Applications and Industrial Electronics (ICCAIE '10)

December 2010

Kuala Lumpur, Malaysia

624 629

10.1109/iccaie.2010.5735010

2-s2.0-79953840377

Banerjee

Xie

Jun

J. H.

Agrawal

D. P.

Increasing lifetime of wireless sensor networks using controllable mobile cluster heads

Wireless Communications and Mobile Computing 2010 10 3 313 336

10.1002/wcm.763

2-s2.0-77449150602

10.

Basagni

Carosi

Melachrinoudis

Petrioli

Wang

Z. M.

Controlled sink mobility for prolonging wireless sensor networks lifetime

Wireless Networks 2008 14 6 831 858

10.1007/s11276-007-0017-x

2-s2.0-54149084958

11.

Sugihara

Gupta

R. K.

Improving the data delivery latency in sensor networks with controlled mobility

Distributed Computing in Sensor Systems 2008 386 399

12.

Rahman

Naznin

Shortening the tour-length of a mobile data collector in the WSN by the method of linear shortcut

Web Technologies and Applications 2013 7808

Berlin, Germany

Springer

674 685 Lecture Notes in Computer Science

13.

Chen

T.-S.

Tsai

H.-W.

Chang

Y.-H.

Chen

T.-C.

Geographic convergecast using mobile sink in wireless sensor networks

Computer Communications 2013 36 4 445 458

10.1016/j.comcom.2012.11.008

2-s2.0-84872924831

14.

Shi

Zhang

Mouftah

H. T.

DDRP: an efficient data-driven routing protocol for wireless sensor networks with mobile sinks

International Journal of Communication Systems 2012 26 10 1341 1355

10.1002/dac.2315

15.

Park

Lee

Kim

S.-H.

Elastic routing: a novel geographic routing for mobile sinks in wireless sensor networks

IET Communications 2010 4 6 716 727

10.1049/iet-com.2009.0197

2-s2.0-77953510263

16.

Lee

Wicke

Kusy

Gnawali

Guibas

Data Stashing: energy-efficient information delivery to mobile sinks through trajectory prediction

Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks

2010

291 302

17.

Khan

A. W.

Abdullah

A. H.

Razzaque

M. A.

Bangash

J. I.

VGDRA: a virtual grid-based dynamic routes adjustment scheme for mobile sink-based wireless sensor networks

IEEE Xplore: Sensors Journal 2015 15 1 526 534

10.1109/jsen.2014.2347137

18.

Heinzelman

W. B.

Chandrakasan

A. P.

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks

IEEE Transactions on Wireless Communications 2002 1 4 660 670

10.1109/TWC.2002.804190

2-s2.0-33646589837

19.

Manjeshwar

Agrawal

D. P.

TEEN: a routing protocol for enhanced efficiency in wireless sensor networks

Proceedings 15th International Parallel and Distributed Processing Symposium (IPDPS '01)

2001

San Francisco, Calif, USA

2009 2015

10.1109/ipdps.2001.925197

20.

Manjeshwar

Agrawal

D. P.

APTEEN: a hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks

Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS '02)

2002

Ft. Lauderdale, Fla, USA

10.1109/ipdps.2002.1016600

21.

Zykina

A. V.

A lexicographic optimization algorithm

Automation and Remote Control 2004 65 3 363 368

10.1023/b:aurc.0000019366.84601.8e