Adjusting Sink Location to Reduce End-to-End Delay in Low-Duty-Cycle Wireless Sensor Networks

Yu-Yuan Lin, Kuo-Feng Ssu, and Hau-Yu Chiang

Adjusting Sink Location to Reduce End-to-End Delay in Low-Duty-Cycle Wireless Sensor Networks

Yu-Yuan Lin, Kuo-Feng Ssu, and Hau-Yu Chiang

—Low-duty-cycle mechanisms can reduce the energy consumption significantly in wireless sensor networks (WSNs). Sensors stay dormant most of the time to save their energy and wake up based on their needs. However, such a technique, while prolonging the network lifetime, sets excessive challenges for reducing the end-to-end (E2E) delay within the network. In this paper, the centralized cluster-based location finding (CCLF) algorithm is proposed to reduce the high latency in low-duty-cycle WSNs by finding a suitable position for the sink. The algorithm is mainly composed of three steps: a) the cluster construction, b) the fast look-up table (FLU-table) construction, and c) the sink location decision. The simulation results show that the performance of the CCLF algorithm is significantly similar to that of the optimal algorithm. Moreover, the CCLF algorithm requires less operation time compared with the optimal algorithm.

Index Terms—Duty cycle, latency, sink, wireless sensor networks.

1. Introduction

Wireless sensor networks are the oncoming technology that has a wide range of promising applications including environmental surveillance, scientific exploration, target tracking, and infrastructure protection[1]–[7]. Such a network normally consists of a large number of distributed nodes that organize themselves into a multi-hop wireless network. Each node typically has one or more sensors, embedded processors, and low-power radios. The nodes are normally powered by batteries that have limited energy and usually non-rechargeable. Hence, the reduction of energyconsumption in wireless sensor networks (WSNs) is an important issue. In order to prolong the life time of WSNs, establishing the low-duty-cycle environment with less than 5% duty cycles is considered to diminish the energy consumption effectively. In low-duty-cycle WSNs, every node has its own working schedule. Nodes turn their radios on in limited time and sleep for the rest. When the next hop node is dormant, a node has to buffer the delivered message and waits for the next hop node to become active. The waiting time for mode switching causes high delivery latency. The working schedule of each node cannot be adjusted arbitrarily to reduce the latency. The working schedule is determined by the power management protocol which is designed for application requirements such as the quality of sensing coverage[8],[9]and target tracking[10],[11].

A sink is the pivot in receiving and conducting messages in many applications such as disseminating commands to sensor nodes, configuring sensor setups, querying sensor states, and so on[12]–[17]. The sink transmits packets to each node hop-by-hop. Different sink locations result in various average end-to-end (E2E) delays because of varying transmission sequences and neighbors. The goal of this paper is to determine a suitable location for the sink. Thus, the message can be delivered quickly and the E2E delay can be reduced.

In this paper, the centralized cluster-based location finding (CCLF) algorithm is developed to reduce the high latency in low-duty-cycle WSNs by finding a suitable position for the sink. The main contributions of this paper are as follows: a) to the best of our knowledge, this paper is the first to propose determining a proper sink location to reduce the E2E delay in low-duty-cycle WSNs. b) based on the CCLF algorithm, the proper sink location can be determined very quickly compared with the optimal algorithm. These two characters make the CCLF algorithm practical in many applications.

The rest of the paper is organized as follows: Section 2 discusses the related work. Section 3 introduces the network model and assumptions. Section 4 presents the main design. Section 5 reports the simulation results. Section 6 concludes the work.

2. Related Work

The main purpose of the low-duty-cycle mechanism isto reduce the energy consumption. Yeet al. proposed a sensor medium-access control (S-MAC) protocol, which is designed for wireless sensor networks[18]. In this work, the proposed algorithm only focuses on energy consumption of the active and dormant modes. The consumed energy during switching from the dormant mode to the active mode has not been considered. An energy-aware switching and scheduling (ESS) algorithm was proposed to resolve the above problem[19]. The ESS algorithm achieves the energy consumption which is arbitrarily close to the global minimum solution.

In low-duty-cycle environment, the reduction of the energy consumption also brings big challenge to the design of efficient packet transmission. There are a number of works that focus on the E2E delay reduction in low-duty-cycle WSNs. These works can be separated into two categories by their link assumption: Reliable links and unreliable links. First, the works based on reliable links networks are introduced. Dousseet al. proved that the E2E delay is proportional to the distance between the sensor and the sink[20]. Keshavarzianet al. designed efficient wake-up scheduling schemes for energy constrained sensor nodes that adhered to the bidirectional E2E delay constraints[21]. Lai and Paschalidis proposed a routing protocol which minimizes a weighted sum of these two opposed factors: the expected energy consumption and the exponent of the latency probability[22]. Guet al. proposed a delay maintenance method. This method augments additional active time slots to reduce the E2E delay[23]. Second, the works based on unreliable links networks are also introduced. Duanet al. introduced a dynamic data forwarding (DDF) scheme to reduce the E2E delay and guaranteed the deliver ratio. The manner is to find out a set of candidate nodes and forward packets to the first awake node in this set[24]. Sun and Xu proposed a delay-aware routing algorithm. Every sensor maintains a forwarding sequence set in which potential forwarders are sorted by their wake-up time[25]. Guet al. proposed a dynamic switch-based forwarding (DSF) algorithm. The DSF algorithm uses the forwarding sequence to reduce the transmission time[26]. As mention above, a number of methods are proposed to reduce the E2E delay. In our best knowledge, no previous work has researched into determining the proper location for the sink. In this paper, the CCLF algorithm is proposed to reduce the E2E delay by determining a proper location for the sink.

3. System Model

3.1 Network Model

The network is consisted of a sink andNsensor nodes. A unique ID number is assigned to each node from 1 toN. The ID number of sink is 0. The sink works all the time and has no power restriction. The active state and dormant state are assigned to each sensor node. In the active state, sensor nodes turn their radios on to transmit or receive data packets. In the dormant state, sensor nodes disable all its function modules. The two states change periodically to achieve the conditions of the low-duty-cycle environment. In this paper, the working period of all sensor nodes isTtime slots.Mtime slots are selected randomly as its active states from 0 toT-1. The duty cycle of the network isM/T(M/T≤ 5% means that the duty ratio is extremely small in the low-duty-cycle environment). In this paper, the working periodTis assigned 100 time units.

3.2 Transmission Latency

In the low-duty-cycle environment, when the next hop node is dormant, a node has to buffer the message and wait for the next hop node to become active. In Fig. 1, the node 1 wants to send a message to the node 2. Node 1 wakes up at the time slot 2. Node 1 cannot send the packet out immediately and needs to wait until the node 2 wakes up at the time slot 5. The latency of the node 1 passing the packet to the node 2 is 3 time slots.

Fig. 1. Illustration of transmission latency.

4. Main Design

Average E2E delays are varied due to different sink locations. The goal of this paper is to find a suitable location for the sink to reduce the E2E delay. In this section, the optimal algorithm and the CCLF algorithm will be introduced. The performance of these two algorithms will be evaluated in Section 5.

4.1 Optimal Algorithm

The optimal sink location is found by the optimal algorithm. The entire network is separated into a twodimensional coordinate system. The optimal algorithm will be executed to calculate the average E2E delay on every coordinate. The coordinate with the minimal average E2E delay will be taken as the optimal sink location.

The optimal algorithm is divided into two states. a) Initial state: When the candidate sink is positioned on a coordinate, the transmission latencies of its neighbor nodes are determined by the candidate sink’s transmission time slot and neighbor nodes’ working schedules. b) Recursive state: The transmission latency of nodexis determined by its previous hop node. Nodexwill also check thetransmission latency from its neighbor nodey. If the path throught nodeyto nodexhas the lower transmission latency, the nodeywill become the previous hop node of the nodex. The chain reaction operates until the transmission latencies of all nodes cannot be changed by their neighbors. The E2E delay of the candidate sink is the time that all nodes receive the message. The candidate sink sendsTmessages out from the time slot 0 to the time slotT-1 on every coordinate in order to calculate the average E2E delay.

4.2 CCLF Algorithm

The CCLF algorithm is mainly composed of three steps: a) cluster construction, b) the fast look-up table (FLU-table) construction, and c) sink location decision. In the CCLF algorithm, the network is separated into multiple clusters, and each cluster has its own candidate sink. The candidate sink with the smallest average E2E delay in the network will be taken as the sink location in the low-duty-cycle WSN.

a) Cluster construction: There is an optimal sink location with the minimal average E2E delay in the network. The main purpose of cluster construction is to reduce the number of candidate sinks. The reduction of candidate sinks also reduces the sink location finding time. The candidate sink with the smallest average E2E delay is always near the optimal sink location because of the same topology and duty cycle schedules. The cluster can be constructed by many parameters such as the residual battery energy, degree, and ID number. This paper presents a simple heuristic cluster construction. The cluster construction sequence is decided by the unique node ID number. The available node is the node which has not been assigned to any cluster. The first cluster is consisted by the smallest available node ID and its neighbors. The cluster ID of the first cluster is 1 and the head node’s ID is 1. The second cluster is consisted by the node with the smallest ID in available nodes and its neighbors in the same way. The cluster ID of the second cluster is 2 and the cluster head node is the node with the smallest ID in the cluster 2. The cluster construction procedure will be terminated until every node belongs to a cluster.

b) The FLU-table construction: The second step of the CCLF algorithm is to establish the FLU-table for each cluster. The gateway node is defined as a node whose neighbors are not all in the same cluster. The path with the minimum transmission latencies from each gateway node to all its cluster members is recorded in the FLU-table. With the help of FLU-table, the transmission latencies within a cluster can be searched efficiently, especially in the case that the transmission latency of gateway node has been modified by the node of different clusters. The FLU-table is constructed by the following mechanism. A gateway node floods a message to all the cluster members. The latencies of the gateway node and its neighbor nodes are determined by gateway node’s message transmission time slot and neighbor nodes’ working schedules. The neighbor nodes of the gateway node also flood the received packets to calculate the transmission latencies. A node may have different transmission latencies because of different previous hop neighbors. The shortest transmission latency is recorded in the FLU-table and used to get the transmission latency of next next hop neighbors. The procedure will be terminated until the transmission latencies of all cluster members have been fixed. The delay from gateway nodes to each node in the same cluster can be recorded precisely in the FLU-table. For example, the nodex, nodeyand nodezare gateway nodes in Fig. 2. The corresponding FLU-table for the cluster 1 is shown in Table 1. Equation (1) is given to calculate the transmission latencies between the gateway node and its cluster members:

whereNi(Am) means that themth active time slot ofNi.Nj(An) denotes the time slot thatNjreceives the message from the previous hop node. min (Ni(Am)-Nj(An)) is the minimum transmission latency from the nodejto the nodei.

Fig. 2. Example of gateway node.

Table 1: FLU-table of cluster 1

c) Sink location decision: The candidate sink in each cluster is set on the location with the most number of neighbors. More available connections to fleetly spread the packets to the entire network can obtain the lower average E2E delay. If more than two locations satisfy the condition mentioned above, the one with the most active time slots will be chosen as the candidate sink. The transmissionlatencies of the candidate sink and its neighbor nodes are determined by the transmission time slot of candidate sink and working schedules of neighbor nodes. The transmission latencies of neighbor nodes also affect the transmission latencies of other related cluster members. A node may have different transmission latencies because of different previous hop neighbors. The shortest transmission latency is recorded and used to get the transmission latencies of next hop neighbors. The procedure will be terminated until the transmission latencies of all cluster members have been fixed. Once the latency of gateway nodes is decided, the transmission latencies of neighbor clusters is determined by the FLU-table efficiently. The chain reaction continues until the E2E delay of network is determined. The FLU-tables can be used repetitively by the candidate sinks to calculate the E2E delay efficiently and avoid transmitting redundant messages.

The message received by different gateway nodes may cause different transmission latencies. The following equation is used to modify the transmission latencies between neighbor clusters:

where min (Ln,m) is the transmission latency fromNntoNm. Once the transmission latency of gateway nodeNnis changed, the equation will check the transmission latency of the passing message fromNntoNmby the FLU-table. The path with the shortest transmission latency is determined by (2). The message transmitting time of sink is variable. The average E2E delay is calculated by an expected value method. The sink knows the working schedules of its neighbors.Ws= {a1,a2,… ,an}is the working schedule set. The average E2E delay is calculated based on (3). The working period of all sensor nodes isTtime slots.

According to the average E2E delay calculated by (3), the candidate sink with the minimal average E2E delay will be selected as the sink location in the network.

5. Simulation Results

In the simulation environment, 144 to 1600 sensor nodes are deployed randomly on 400 m2to 6400 m2square field (randomly-generated network). The network density keeps the same. The node communication range is 3 m. The cluster is constructed by the head node and its 2-hops neighbors. The E2E delay and the operation time with the proposed CCLF algorithm, randomly pick method, and optimal algorithm will be compared in the following. The operation time is the time to find the location for the sink.

5.1 Different Duty Cycle

There are 250 nodes in the network. The duty cycles of the node are 1% to 4%. In Fig. 3, the curve shows that the performance of the proposed CCLF algorithm is consistently better than the randomly pick method and is very close to the optimal algorithm. Fig. 3 also shows that the higher duty cycle follows with the less E2E delay.

Fig. 3. Comparison of average E2E delay versus duty cycle.

5.2 E2E Delay and Operation Time

The performance of the CCLF algorithm in different network size with and without the restricted area is shown in this section. The duty cycle is 3% in the following simulation.

a) Randomly-generated network without restricted area. In Fig. 4, the average E2E delay is increased as the network size is expanded. The CCLF algorithm significantly outperforms the random pick method and the delay is decreased up to 38.54%. The performance of the CCLF algorithm is very close to the optimal algorithm. The difference of the average E2E delay between the CCLF algorithm and the optimal algorithm is around 1%. The relationship of total operation time between the CCLF algorithm and the optimal algorithm is presented in Fig. 5. The CCLF algorithm is obviously faster than the optimal algorithm in all test conditions. The CCLF algorithm achieves 5.32 times faster than the optimal algorithm for network size of 1600 m2.

Fig. 4. Comparison of average E2E delay versus network size.

Fig. 5. Comparison of average operation time versus network size.

b) Randomly-generated network with forbidden area. In this section, the network with a forbidden area is simulated. The sensor nodes would not be deployed in the forbidden area. In Fig. 6, the performance of the CCLF algorithm is nearly the same as compared with the optimal algorithm. However, in Fig. 7, the CCLF algorithm achieves 5.43 times faster on the total operation time than the optimal algorithm in network size of 1600 m2.

Fig. 6. Comparison of E2E delay for WSNs with forbidden area.

Fig. 7. Operation time for WSNs with forbidden area.

5.3 Different Delay Bound and Hit Rate Comparison

The impact of delay bound is shown in Fig. 8. There are 250 nodes in the network and the duty-cycle is 1%. In Fig. 8, the curves of the CCLF algorithm and the optimal algorithm are nearly the same. When the delay bound is above 420 time units, the CCLF algorithm can guarantee a 100% message delivery ratio from the sink to each node. The randomly pick scheme only achieves approximately a 70% message delivery ratio. The cumulative distribution function (CDF) of the CCLF algorithm is consistently larger than the randomly pick scheme in all cases.

Fig. 8. Comparison of CDF versus delay bound.

The hit rate of the CCLF algorithm is shown in Fig. 9. The hit rate represents the rate that the sink location found by the CCLF algorithm is the same as the location found by the optimal algorithm. The CCLF algorithm obtains the average hit rate of 60%. For the 40% miss cases, the resultant performance is also similar to the optimal algorithm.

Fig. 9. Comparison of hit rate versus network size.

6. Conclusions

A low-duty-cycle mechanism has been used to reduce the energy consumption. However, such a technique, while increasing the network lifetime, has challenges to improving E2E delay within the network. This paper introduced a CCLF algorithm for low-duty-cycle WSNs. The CCLF algorithm is a sink positioning solution based on cluster classification and fast look-up tables. The simulation results show that the CCLF algorithm achieves competitiveperformance with the optimal algorithm. The operation time even achieves 5.32 times faster than the optimal algorithm. The extensive simulation also demonstrates the reliability of CCLF scheme under varying conditions of the network environment.

[1] R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson, and D. Culler, “An analysis of a large scale habit monitoring application,” inProc. of ACMConf. on Embedded Networked Sensor Systems, 2004, pp. 214–226.

[2] X. Liu, J. Cao, S. Lai, C. Yang, H. Wu, and Y. Xu, “Energy efficient clustering for WSN-based structural health monitoring,” inProc. of IEEEConf. on Computer Communications, 2011, pp. 2768–2776.

[3] Q. Zhang, G. Sobelman, and T. He, “Gradient-driven target acquisition in mobile wireless sensor networks,” inProc. of Conf. on Mobile Ad-hoc and Sensor Networks, 2006, pp. 365–376.

[4] Y. Zhang, L. Zhang, and X. Shan, “Robust distributed localization with data inference for wireless sensor networks,” inProc. of IEEE Conf. on Communications, 2008, pp. 3125–3129.

[5] N. Xu, S. Rangwala, K. K. Chintalapudi, D. Ganesan, A. Broad, R. Govindan, and D. Estrin, “A wireless sensor network for structural monitoring,” inProc.of ACM Conf. on Embedded Networked SensorSystems, 2004, pp. 13–24.

[6] W.-T. Wang and K.-F. Ssu, “Obstacle detection and estimation in wireless sensor networks,”Computer Networks, vol. 57, no. 4, pp. 858–868, Mar. 2013.

[7] W.-C. Chu and K.-F. Ssu, “Decentralized boundary detection without location information in wireless sensor networks,” inProc. of IEEEConf. on Wireless Communications and Networking, 2012, pp. 1720–1724.

[8] G. Wang, G. Cao, P. Berman, and T. F. La Porta, “Bidding protocols for deploying mobile sensors,”IEEE Trans. on Mobile Computing, vol. 6, no. 5, pp. 563–576, May 2007.

[9] D. Wang, B. Xie, and D. P. Agrawal, “Coverage and lifetime optimization of wireless sensor networks with gaussian distribution,”IEEE Trans. onMobile Computing, vol. 7, no. 12, pp. 1444–1458, Dec. 2008.

[10] S. Subramaniam, V. Kalogeraki, and T. Palpanas,“Distributed real-time detection and tracking of homogeneous regions in sensor networks,” inProc.of IEEE Symposium on Real-Time Systems, 2006, pp. 401–411.

[11] L. Lazos, R. Poovendran, and J. A. Ritcey, “Probabilistic detection of mobile targets in heterogeneous sensor networks,” inProc. IEEESymposium on Information Processing in Sensor Networks, 2007, pp. 519–528.

[12] D. Lymberopoulos, A. Bamis, and A. Savvides, “A methodology for extracting temporal properties from sensor network data streams,” inProc. of ACM Conf. on Mobile Systems, Applications, and Services, 2009, pp. 193–206.

[13] K. Romer, “Discovery of frequent distributed event patterns in sensor networks,” inProc. of European Conf. on Wireless Sensor Networks, 2008, pp. 106–124.

[14] S. R. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, “TinyDB: An acquisitional query processing system for sensor networks,”ACM Trans.on Database Systems, vol. 30, no. 1, pp. 122–173, Mar. 2005.

[15] C.-T. Huang, T.-H. Lin, L.-J. Chen, and P. Huang, “XD: A cross-layer designed data collection mechanism for mission-critical WSNs in urban buildings,” inProc. of IEEE Conf. on Mobile Data Management:Systems, Services, and Middleware, 2009, pp. 399–404.

[16] R. Mangharam, A. Rowe, R. Rajkumar, and R. Suzuki,“Voice over sensor networks,” inProc. of IEEE Symposium on Real-TimeSystems, 2006, pp. 291–302.

[17] M. Y. Nam, C. G. Lee, K. Kim, and M. Caccamo,“Time-parameterized sensing task model for real-time tracking,” inProc. of IEEESymposium on Real-Time Systems, 2005, pp. 245–255.

[18] W. Ye, J. Heidemann, and D. Estrin, “Medium access control with coordinated adaptive sleeping for wireless sensor networks,”IEEE/ACM Trans. onNetworking, vol. 12, no. 3, pp. 493–506, Jun. 2004.

[19] N. Aydin, M. Karaca, and O. Ercetin, “Energy-optimal scheduling in low duty cycle sensor networks,” inProc. IEEE Symposium on Performance Evaluation of Computer & Telecommunication Systems, 2011, pp. 119–126.

[20] O. Dousse, P. Mannersalo, and P. Thiran, “Latency of wireless sensor networks with uncoordinated power saving mechanisms,” inProc. of ACM Symposium on Mobile Ad Hoc Networking and Computing, 2004, pp. 109–120.

[21] A. Keshavarzian, H. Lee, and L. Venkatraman, “Wakeup scheduling in wireless sensor networks,” inProc. of ACM Symposium on MobileAd Hoc Networking and Computing, 2006, pp. 322–333.

[22] W. Lai and I. C. Paschalidis, “Sensor network minimal energy routing with latency guarantees,” inProc. of ACM Symposium on MobileAd Hoc Networking and Computing, 2007, pp. 199–208.

[23] Y. Gu and T. He, “Bounding communication delay in energy harvesting sensor networks,” inProc. of IEEE Conf. on DistributedComputing Systems, 2010, pp. 837–847.

[24] Y. Duan, X. Wu, F. Wu, and G. Chen, “Dynamic data forwarding in low-duty-cycle sensor networks,” inProc. of IEEE Conf. on Parallel and Distributed Systems, 2011, pp. 505–511.

[25] G. Sun and B. Xu, “Delay-aware routing in low duty-cycle wireless sensor networks,” inProc. of IEEE Conf. on WirelessCommunications Networking and Mobile Computing, 2010, pp. 1–4.

[26] Y. Gu and T. He, “Dynamic switching-based data forwarding for low-duty-cycle wireless sensor networks,”IEEE Trans. on Mobile Computing, vol. 10, no. 12, pp. 1741–1754, Dec. 2011.

Yu-Yuan Lin received the B.S. degree in computer and information science from Soochow University, Soochow and the M.S. degree in computer and communication engineering from National Cheng Kung University, Tainan. He is currently a Ph.D. student with the Institute of Computer and Communication Engineering, National Cheng Kung University. His research interests include mobile computing and wireless sensor networks.

Kuo-Feng Ssu received the B.S. degree in computer science and information engineering from National Chiao Tung University, Hsinchu and the Ph.D. degree in computer science from the University of Illinois, Urbana-Champaign. He is currently a professor with the Department of Electrical Engineering, National Cheng Kung University, Tainan. He is also a visiting scholar with the Department of Computer and Information Sciences, University of Delaware, Newark, Delaware. He was a visiting associate professor with the School of Electrical and Computer Engineering, Cornell University, Ithaca, New York. His research interests include mobile computing, distributed systems, and dependable computing. His research awards include the Ta-You Wu Memorial Award, the K.T. Li Research Award, and the Lam Research Thesis Award. He is a member of IEEE, ACM, and the Phi Tau Phi Honor Scholastic Society.

Hau-Yu Chiang received the B.S. in computer and information science from Soochow University, Soochow and the M.S. degree in computer and communication engineering from National Cheng Kung University, Tainan. His research interests include mobile ad hoc networks and wireless sensor networks.

Manuscript received December 28, 2013; revised March 18, 2014. This work was supported in part by NSC under Grant No. NSC 100-2628-E-006-028-MY3, 100-2221-E-006-136-MY2, and 101-2221-E-006-247-MY3.

Y.-Y. Lin is with the Institute of Computer and Communication Engineering, National Cheng Kung University, Tainan 701 (e-mail: bao@dcl.ee.ncku.edu.tw).

K.-F. Ssu is with the Department of Electrical Engineering, National Cheng Kung University, Tainan 701 (Corresponding author e-mail: ssu@ee.ncku.edu.tw).

H.-Y. Chiang is with the Data Systems Consulting Co., Ltd, Taipei 106 (e-mail: healmax@gmail.com).

Digital Object Identifier: 10.3969/j.issn.1674-862X.2015.01.005