Evaluating an (<italic>m, k</italic>)-firm Deadline Real-time Stream Based on a Reliable Transport Protocol in Wireless Sensor Networks
Evaluating an (m, k)-firm Deadline Real-time Stream Based on a Reliable Transport Protocol in Wireless Sensor Networks
Journal of Information and Communication Convergence Engineering. 2012. Jun, 10(2): 129-134
Copyright ©2012, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License ( 3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : March 12, 2012
  • Accepted : April 20, 2012
  • Published : June 30, 2012
Export by style
Cited by
About the Authors
Ki-Il Kim

As application-specific requirements for wireless sensor networks emerge, both real-time and reliable communications become major research challenges in wireless sensor networks due to the many constraints on nodes and wireless links. To support these services, several protocols have been proposed. However, since most of them were designed as well as developed for general purpose applications, it is not recommended that they be directly adapted to applications with special requirements. In this paper, we propose a way to extend the current reliable transport protocol to cover a special real-time service, the ( m,k )-firm deadline stream, in wireless sensor networks. While the proposed scheme is basically built on the PSFQ protocol for reliability, some features have been newly developed to support the ( m,k )-firm stream efficiently. Finally, simulation results are given to demonstrate the feasibility of the proposed scheme in high traffic and with failed links.
In recent years, significant developments in wireless and electronics communications have enabled the expansion of limited-power and small-sized sensor nodes. A large number of these sensor nodes are deployed in a single geographic area and are utilized in a wide range of applications including monitoring physical and artificial environmental phenomena, events, and vehicle tracking [1] . This kind of network is called a wireless sensor network (WSN).
A sensor node is a small device that is able to perform essential functions such as environmental monitoring, mobile target tracking, smart space, and ubiquitous computing. The most noteworthy drawback of the wireless sensor network is that each sensor node is capable only of low-rate, short-range wireless communication. This feature inherently hinders reliability, which implies messages sent by a sender should be delivered to the destination without errors during transmission. Moreover, since reliability is generally influenced by many different factors such as channel loss, interference, bandwidth limitations, traffic peaks, and node resource constraints, a complementary scheme needs to be implemented in each layer in order to cover unreliable and resource-constrained networks. On one hand, to guarantee reliability, several fundamental mechanisms and tunable parameters have been proposed to be applied to wireless sensor networks in conjunction with well-known existing schemes. They include rate control, scheduling policy, drop policy, explicit notification, acknowledgments, MAC backoff, and next-hop selection. In parallel with research efforts in the transport layer, several routing protocols have been proposed to address the reliability problem.
In addition to reliability issues, real-time service has attracted researchers’ interests as many applications have emerged in wireless sensor networks such as monitoring and tracking. Current research works on real-time delivery are mainly focused on a network layer approach since most of the delivery time is consumed in this layer. In this layer, two kinds of approaches have been proposed to provide real-time service. One is real-time scheduling based on priority since queuing delay is the biggest component of end-to-end delay. The other scheme for real-time communication is real time routing, which is designed to find an adequate path guaranteeing end-to-end delay.
Since reliability has been closely related to real-time service, both issues should be explored together. However, few studies have been conducted that have addressed the above problem. The main example is known as VIGILNET, which is network architecture for real-time delivery. Its main mission is tracking operations and it was developed at the University of Virginia [2] . Military operations, including real-time tracking and observation, are major targets of VIGILNET. A mathematical model and threshold partition method were proposed to meet deadlines for end-to-end delay.
Based on the results of previous research, many schemes have been proposed by adapting existing approaches to WSNs to provide both services. Their major contributions are to modify existing schemes in order to meet the constraints of sensor nodes as well as the requirements of specific applications. As a result, current approaches for real-time and reliable delivery can be considered as approaches to extending existing schemes. Therefore, they naturally have several drawbacks to be mentioned because sensor networks have specific requirements as opposed to the general requirements of previous network designs.
Motivated by the above needs, we take the ( m,k )-firm deadline model [3] for WSNs. A real-time stream with the ( m,k )-firm guarantee requirement demands that at least m out of any k consecutive packets in this stream must meet their respective deadlines. Two well-known examples of the ( m,k )-firm stream model are video and audio streams because they are tolerant of some packet loss but sensitive to real-time delivery. The concept of ( m,k )-firm is appropriate for WSNs due to the minimum throughput requirements and due to the poor wireless connectivity and bandwidth constraints on WSNs. Despite the apparent suitability of the model, to the best of the authors' knowledge, one only research work [4] has addressed this possibility before other than schemes developed by our own research group [5 , 6] .
Thus, building on our previous work, the author proposes an approach to combining reliable and real-time services to support an ( m,k )-firm stream in wireless multimedia sensor networks. In the proposed scheme, we combine the plum slowly fetch quickly (PSFQ) [7] approach to reliability due to its simplicity of operation and multiple operations. For real-time service using an ( m,k )-firm deadline stream, the distance based priority (DBP) approach is used with real-time requirements. According to the requirements, each node determines the number of segments lost and corresponding retransmission of lost segments.
The rest of this paper is organized as follows. In section II, several studies are briefly explained. The proposed scheme will be described in section III. The performance evaluation through simulation will then be given in section IV. Finally, we draw a conclusion in section V.
In this section, the research work on reliable and real-time delivery is overviewed. First, PSFQ and the reliable multi-segment transport (RMST) mechanism [8] were proposed to guarantee reliability in the transport layer. In PSFQ, a segment is divided into smaller multiple segments while providing sufficient time to detect a loss over an intermediate node. Another approach, referred to as RMST, includes several reliability schemes based on automatic repeat request (ARQ) and not acknowledge (NACK). On the other hand, schemes such as adaptive rate control (ARC) [9] and event-to-sink reliable transport (ESRT) [10] have been proposed to control congestion in the transport layer. In the ESRT scheme, the domain for reliability is sectoring into four regions, which consist of uncongested subthreshold, uncongested overthreshold, congested overthreshold, and congested subthreshold. Depending on the current region, a sink provides feedback to the source directly to control congestion. The hybrid reliable routing (HRR) technique [11] is designed as to construct a hierarchical network architecture rather than a flat one under the assumption that a cluster architecture can guarantee reliability by communicating between cluster headers having more power and a higher data rate on wireless communication radio. Another receiver-oriented load-balancing and reliable routing (RLRR) [12] protocol has been proposed to achieve both load balancing and reliability for large-scale WSNs. Other approaches have been proposed for developing routing protocols, which make use of either a multipath approach or a new metric suitable for reliability in wireless sensor networks. The authors in [13] presented the directed transmission routing protocol (DTRP), introducing parametric and probabilistic approaches. DTRP is a multipath proactive routing protocol specially designed for WSNs to provide improved scalability and reliability. Different from typical routing protocols, DTRP uses the beacon packet not to resolve the next hop node for the destination but to provide only the hop-count distance value between the sink and other sensor nodes.As for an approach with a new metric, the MintRoute protocol was proposed in [14] . To estimate the link quality, the average packet reception ratio is measured through periodic beacon messages and the link cost is set to this value.
SPEED [15] and Multi-Path and Multi-SPEED (MMSPEED) [16] are quality of service (QoS) based routing protocols that provide soft end-to-end deadline guarantees for real-time packets in sensor networks. Both use a geographic forwarding mechanism to route packets to the sink. SPEED ensures a network-wide speed of packet delivery for a real-time guarantee, i.e., it calculates the end-to-end delay by dividing the distance to the sink by the speed of packet delivery before making any admission decision. SPEED can also provide congestion avoidance when the network is congested. MMSPEED is an extension of SPEED; therefore, MMSPEED generalized the single network-wide speed approach of SPEED by replicating and using multiple SPEED layers that run independently of each other. For delivery timeliness, MMSPEED provides multiple network-wide packet delivery speed options for different traffic types according to their end-to-end deadlines. For QoS reliability, multipath forwarding is used to control the number of delivery paths based on the probability of reaching end-to-end. However, neither SPEED nor MMSPEED consider an energy consumption metric or the lifetime of the WSN.
In related work on the ( m,k )-firm deadline stream, Ramanathan and Hamdaoui [3] proposed a scheduling policy called distance-based priority (DBP) to better service multiple real-time streams, each with its own ( m,k )-firm guarantee requirement. Instead of assuming that all messages reach their destination in one hop, DBP-M [4] is extended to deal with streams in which the messages traverse more than one hop to reach their destinations, by providing a local-deadline to exploit the ability of many streams to tolerate occasional deadline misses. Although these schemes present both a scheduling and routing algorithm to guarantee real-time delivery for the ( m,k )-firm stream model, to the best of our knowledge, they have only been adapted to WSNs without considering the inherent timeliness relationships between packets of multimedia streams.
In this section, we explain the proposed scheme through the following algorithms. The proposed algorithm is based on the following assumption: that the ( m,k )-firm stream requirement is achieved by guaranteeing the ( m,k )-firm requirement over the respective link along the path between the source and the sink.
Procedures at the intermediate node
PPT Slide
Lager Image
Procedures at the intermediate node
  • Step 1:When an intermediate node receives a packet, it checks the deadline for real-time service. If the elapsed time is over the deadline, a packet is dropped. Otherwise, several variables carried on this packet are extracted.
  • Step 2:Based on PSFQ, a packet is divided into sub-segments as much ask, the requirement.
  • Step 3:If the current stream status is considered to be sufficient, the number of segments that should be delivered to next hop is set tok, the original requirement. This means that the minimum number of segments will be considered for the (m,k)-firm stream. Otherwise, if a stream does not meet the requirement, this packet is very critical for the requirement. Thus, a stronger and stricter requirement is given by considering the current DBP value. The smaller the DBP value a stream has, the more packets should be delivered to next hop within the deadline. The maximum number of packets cannot exceed m packets.
  • Step 4:All of the segments are transmitted to the next hop over the link.
Deciding on retransmission
PPT Slide
Lager Image
Deciding on retransmission
Based on the basic operational functions in PSFQ, a segment will be recovered in a hop-by-hop manner. Algorithm 2 shows how a NACK message is dealt with for the lost segment. Since the sequence number of the NACK message is accumulative, the variable increases by the lost sequence number.
The main function of ( m,k )-firm is accomplished by Step 2. If the sequence number is larger than the required packets for node i , all messages with a sequence number less than nackNof are removed from the buffer. Also, the messages with the next sequence number are transmitted rather than S nackNof . Since this case indicates that the ( m,k )- firm requirement is already met by the messages already sent, the lost segment is not retransmitted. Instead, the next segment with sequence number S f+1 is transmitted. Otherwise, if the number of packets is not sufficient for the ( m,k )-firm requirement, the lost segment is immediately retransmitted to meet the requirement.
- A. Simulation Model and Environment
In order to evaluate the performance of our proposed algorithm, we conducted simulations in Qualnet. We implemented our code in the Qualnet simulator [17] for diverse simulations. The simulation parameters and each protocol variable are described as follows. Our simulation modeled a network of 100 nodes placed randomly within a 1,000 m × 1,000 m area. The radio propagation range for each node was 100 meters and the channel capacity was 250 kbps. General carrier sense multiple access (CSMA) was used for medium access control (MAC) protocols and the two-ray model was used for propagation models to reduce the effect of the MAC and physical protocol. The application used for the proposed simulation was SURGE, which reports the sensing information at a predetermined rate. Unless otherwise specified, the mean period of a stream is 50 ms inter-arrival time between packets. The simulation parameters were derived from the sQualnet model [18] , which was obtained from a datasheet in the MICA2 motes. The MICA2 has a CC2420 radio chip, which is made by ChipCon (Oslo, Norway) and is ZigBee compliant. It operates in the 2.4 GHz band and has a link capacity of 250 kbps using a spread spectrum and offset quadrature phase-shift keying (OQPSK) modulation for tolerance to interference. The CC2420 has a maximum outdoor range of 125 m with a maximum current draw of 17.4 mA (0 dBm). These ranges are based on the reception strength threshold. In this way, the simulation model is compliant to the actual sensor network model.
Each simulation was executed for 20,000 seconds. Multiple runs with different seed numbers were conducted for each scenario and the data obtained was averaged over those runs. Furthermore, the 95% confidence intervals of the mean were computed. A simulation was conducted to determine whether the proposed scheme could guarantee the ( m,k )-firm requirement due to quick packet recovery and decision for retransmission with a given traffic status.
The deadline for the real-time packet on each node is set to average-link-delay × number of shortest hops, respectively. The average-link-delay was computed by conducting several simulation scenarios. The first experiment evaluated the performance of a proposed scheme in the point of dynamic failure probability. Dynamic failure is said to the case when fewer than m out of any k packets meet their deadline. Thus, dynamic failure probability is represented as what percent of packets are delivered while meeting the ( m,k ) requirement. For this comparison, we adapt two different applications with (2,2)-firm and (2,4)-firm streams.
- B. Simulation Results and Analysis
In Fig. 1 , we evaluated the performance, specifically, how much real-time traffic was delivered within the deadline. The x-axis represents the amount of background SURGE traffic and the y-axis, the dynamic failure probability, while the 22 indicates the (2,2)-firm stream and the 24, the (2,4)-firm one. As shown in Fig. 1 , the proposed scheme derives the acceptable performance from the dynamic failure probability. However, the failure probability increases as the amount of background traffic increases. In particular, the (2,2)-firm stream shows a higher failure probability because any lost packet affects the dynamic failure probability. On the other hand, the (2,4)-firm stream is tolerant of some lost packets.
PPT Slide
Lager Image
The percentage of packets within deadline as a function of increased traffic.
The main reason for the acceptable performance results from two properties, hop-by-hop recovery and decisions using the current DBP value. First, hop-by-hop recovery can reduce the failure of passing the deadline. Like current network systems, if the reliability is guaranteed by an end-to-end approach, a long delay is too likely. Moreover, this long delay is not suitable for real-time service so a hop-by-hop approach in PSFQ is a good solution for real-time service. Secondly, the DBP value can contribute to preventing congestion by selecting the segment that should be retransmitted or ignored according to the current status. This feature makes additional control of the traffic so it can improve the dynamic failure probability compared to current traffic features.
PPT Slide
Lager Image
The percentage of packets within deadline as a function of the failure of links.
Another simulation was conducted to evaluate the performance of the proposed scheme as a function of number of link failures. In Fig. 2 , the x-axis indicates the number of links in a failing state. The dynamic failure probability increases as the number of failed links increases. A failed link can hinder successful packet delivery in the middle of transmission. However, hop-by-hop recovery as well as operation with the DBP value contributes to maintaining an acceptable failure probability. If the proposed scheme were to be developed without any basis on previous work, the simulation results would be very different. However, the recovery scheme in PSFQ is very resistant to failure, and the ( m,k )-firm stream also benefits by this property.
In order to support real-time service in wireless sensor networks, several solutions have been proposed in the research literature. However, due to high complexity, it has not been easy to employ them in real environments. Also, there has been no consideration for an application-specific requirement. In this paper, we developed a new real-time protocol based on a scheme for reliability under the basic assumption that real-time service is greatly affected by reliability. For the application-specific model, we introduced the ( m,k )-firm deadline stream, which is regarded as a very appropriate model for wireless sensor networks.
Based on basic operation and hop-by-hop recovery, we extend with the application of the ( m,k )-firm stream to wireless sensor networks. The requirements are dynamically adjusted according to the current traffic status. This strategy can control the retransmission so eventually traffic is managed accordingly. Simulation results demonstrate that the proposed scheme results in lower dynamic failure probability.
Related to this work, the dynamic scheduling algorithm will be applied to produce better performance. Also, more studies of real-time service will be carried out through various topologies as well as adjustable parameters to determine the strengths and weaknesses of the proposed protocol.
This research was supported by Basic Science Research Program through the National Research Foundation (NRF) of Korea funded by the Ministry of Education, Science and Technology (2012-0001761) and the Ministry of Knowledge Economy (MKE), Korea, under the Information Technology Research Center (ITRC) support program supervised by the National IT Industry Promotion Agency (NIPA; NIPA-2012- H0301-12-3003).
Bulut E. , Korpeoglu I. 2011 "Sleep scheduling with expected common coverage in wireless sensor networks," Wireless Networks vol. 17 (no. 1) 19 - 40
He T. , Krishnamurthy S. , Luo L. , Yan T. , Gu L. , Stoleru R. , Zhou G. , Cao Q. , Vicaire P. , Stankovic J. A. , Abdelzaher T. F. , Krogh J. H. B. 2006 "VigilNet: an integrated sensor network system for energy-efficient surveillance," ACM Transactions on Sensor vol. 2 (no. 1) 1 - 38
Ramanathan P. , Hamdaoui M. 1995 "A dynamic priority assignment echnique for streams with (m, k)-firm deadline," IEEE Transactions on Computers vol. 44 (no. 12) 1443 - 1451
Striegel A. , Manimaran G. 2000 "Best-effort scheduling of (m,k)- firm real-time streams in multihop networks," Computer Communications vol. 23 (no. 13) 1292 - 1300
Kim K. I. 2010 "A novel scheduling for (m, k)-firm streams in wireless sensor networks," Proceedings of the 6th International Conference on Networked Computing and Advanced Information Management Seoul, Korea 553 - 556
Kim K. I. , Sung T. E. 2010 "Network layer approaches for (m,k)-firm stream in wireless sensor networks," IEICE Transactions on Communications vol. 93B (no. 11) 3165 - 3168
Wan C. Y. , Campbell A. T. , Krishnamurthy L. 2002 "PSFQ: a reliable transport protocol for wireless sensor networks," Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications Atlanta, GA 1 - 11
Stann F. , Heidemann J. 2003 "RMST: reliable data transport in sensor networks," Proceedings of the 1st IEEE International Workshop on Sensor Network Protocols and Applications Anchorage, AK 102 - 112
Woo A. , Culler D. E. 2001 "A transmission control scheme for media access in sensor networks," Proceedings of the 7th Annual International Conference on Mobile Computing and Networking Rome, Italy 221 - 235
Sankarasubramaniam Y. , Akan O. B. , Akyildiz I. F. 2003 "ESRT: event-to-sink reliable transport in wireless sensor networks," Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing Annapolis, MD 177 - 188
Kavitha C. , Viswanatha K. V. 2009 "A hybrid reliable routing technique (HRR) for wireless sensor network," International Journal of Computer Science and Network Security vol. 9 (no. 3) 35 - 39
Chen M. , Leung V. C. M. , Mao S. , Kwon T. 2009 "Receiveroriented load-balancing and reliable routing in wireless sensor networks," Wireless Communications & Mobile Computing vol. 9 (no. 3) 405 - 416
Nassr M. S. , Jun J. , Eidenbenz S. J. , Hansson A. A. , Mielke A. M. 2007 "Scalable and reliable sensor network routing: performance study from field deployment," Proceedings of the 26th IEEE International Conference on Computer Communications Anchorage, AK 670 - 678
Woo A. , Tong T. , Culler D. 2003 "Taming the underlying challenges of reliable multihop routing in sensor networks," Proceedings of the 1st International Conference on Embedded Networked Sensor Systems Los Angeles, CA 14 - 27
He T. , Stankovic J. A. , Lu C. , Abdelzaher T. 2003 "SPEED: a stateless protocol for real-time communication in sensor networks," Proceedings of the 23rd International Conference on Distributed Computing Systems Providence, RI 46 -
Felemban E. , Lee C. G. , Ekici E. , Boder R. , Vural S. 2005 "Probabilistic QoS guarantee in reliability and timeliness domains in wireless sensor networks," Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies Miami, FL 2646 - 2657
Scalable Network Technology Inc. Available: [Internet]
Networked & Embedded Systems Laboratory. sQualnet: a scalable simulation framework for sensor networks [Internet]. Available: