Clustering Scheme for (m,k)-Firm Streams in Wireless Sensor Networks

  • cc icon

    As good example of potential application-specific requirement, (m,k)-firm real-time streams have been recently introduced to deliver multimedia data efficiently in wireless sensor networks. In addition to stream model, communication protocols to meet specific (m,k)-firm real-time streams have been newly developed or extended from existing protocols. However, since the existing schemes for an (m,k)-firm stream have been proposed under typical flat architecture, the scalability problem remains unsolved when the number of real-time flows increases in the networks. To solve this problem, in this paper, we propose a new clustering scheme for an (m,k)-firm stream. The two different clustering algorithms are performed according to either the (m,k)-firm requirement or the deadline. Simulation results are presented to demonstrate the suitability of the proposed scheme under hierarchical architecture by showing that its performance is acceptable irrespective of the increase in the number of flows.


    Clustering , (m,k)-firm , Real-time , Wireless sensor networks


    When it comes to data delivery in wireless sensor networks, real-time communication becomes an important requirement because of the time sensitivity of the sensing data. However, because of the diverse constraints of a node, such as low-power computing, battery operation, and low-data-rate wireless communication within a short range, it is difficult to ensure data delivery within the specified deadline in these networks.

    To solve the abovementioned problem, some well-known routing protocols have been proposed to meet the real-time communication requirement. Among them, SPEED [1] and its variants, such as MMSPEED [2] and the real-time fault-tolerant routing protocol called FT-SPEED [3], are the well-known soft real-time routing protocols. These protocols estimate the transmission speed between the current node and the candidate nodes and then, attempt to establish a transmission path with all the relay nodes in order to maintain the desired delivery speed.

    In addition to these approaches, recently, new routing protocols that consider both the abovementioned real-time communication requirement and other properties have been proposed. For instance, the real-time power-aware (RTPA) [4] routing protocol supports a real-time application in an energy-efficient manner. Opportunistic real-time routing (ORTR) [5] also takes into account the delivery of data under time constraints with efficient power consumption. Further, the simultaneous attentive energy routing protocol (SAERP) [6], real-time and robust routing protocol (RTRR) [7], and potential-based real-time routing (PRTR) [8] address energy efficiency and other metrics such as robustness. In addition to the abovementioned routing protocols, more research work has been introduced and analyzed in [9]. However, since these routing protocols assume a general requirement for real-time communication, they lack adaptability in a real deployment case since a sensor network is generally deployed to support a specific application. This indicates that a specific routing protocol is desirable to meet each real-time communication requirement.

    To solve this problem, application-specific approaches have been proposed.

    Good examples for a realistic application in wireless sensor networks are discussed in [10]. In [10], research challenges and issues related to operations are presented. Since the communication protocols are mostly dependent on the application, we need to define the traffic model in advance. However, there has been little research addressing both the traffic model and the communication protocol.

    In this paper, we propose various routing protocols for an (m,k)-firm stream with a geographic routing protocol and a priority-based scheduling algorithm with the deadline, distance, and remaining slack time similar to those in [10]. The concept of the (m,k) firm can be defined as follows: a real-time message stream is considered to have an (m,k)-firm guarantee requirement that states that at least m out of any k consecutive messages from the stream must meet their deadlines, in order to ensure adequate quality of service (QoS) [11]. On the basis of this concept, a priority assignment technology called distance-based priority (DBP) was developed to arbitrate between the streams in a system. Further, several variant protocols have been proposed in [12]. However, despite these research efforts, the scalability problem still remains unsolved. This indicates that the existing scheme suffers from performance degradation when the number of flows increases.

    To solve the abovementioned problem, we present a clustering scheme for an (m,k)-firm stream in wireless sensor networks. After deciding the cluster header (CH) with the relevant algorithm and parameters, each node transmits a real-time packet to the corresponding CH. These packets are aggregated and forwarded to the destination by the existing (m,k)-firm routing protocol. Finally, we evaluate the performance of the proposed scheme from the viewpoint of the real-time requirement as a function of the number of flows and the traffic load through a simulation.

    The rest of this paper is organized as follows: in the following section, we describe the system and traffic models. The clustering scheme is explained in Section III. The simulation results are presented and analyzed in Section IV. Finally, we present the conclusion and briefly discuss the future work in Section V.


      >  A. Real-Time Flow Model

    A real-time flow, denoted by Fi , is a set of periodic message streams from a source node i to a sink node. For the sake of simplicity, we assume that there is only one flow between a source and the sink. The message deadline is denoted by Di. Both mi and ki are determined by the application requirement for a stream. The QoS level for an (m,k)-firm stream is represented by DBPi. Consequently, a new real-time stream is defined as Fi = ((mi, ki), Di, DBPi). A source node sends a data packet by carrying the Fi information in the header. The DBPi value is evaluated and reported to each source, i, in a roundabout manner. Therefore, any packet in the jth round in this model carries the following information: ((mij, kij), Dij, DBPij) after the quality level is set by the proposed scheme. However, for the sake of simplicity, we use Fi instead of Fij for the explanation in the remaining part.

      >  B. Network Model

    We consider a wireless sensor network that consists of randomly deployed sensor nodes over a finite, two-dimensional planar region. We consider that all sensor nodes including a sink are static. Several CHs can be chosen in one geographical area. If the CHs are determined, the corresponding flows are aggregated into one stream and their parameters are configured according to the requirements. A CH is periodically chosen and announced to all nodes in the geographical area.


      >  A. CH Selection

    In order to determine the CH in a distributed manner, a node uses a timer to identify the other node’s value. For the clustering, we consider two new parameters, namely, deadline and (m,k)-requirement. This leads to the aggregation of flows with similar values at the node. The detailed procedure for determining the CH is as follows:


    Fig. 1 illustrates the procedure for determining the CH when nodes s and t have the same DBPi value. In this case, these two nodes compute the clustering area in the form of a rectangle by considering themselves as the center.

    Then, they flood the advertisement message in the area. Thereafter, node x, located in both the geocast areas, sends a join message to t according to Step 3 even though two independent messages are delivered.

      >  B. (m,k)-Firm Stream Aggregation

    When the CH is determined using the previous steps, the stream aggregation scheme for the (m,k)-firm streams is performed using a compositional model with a hierarchical scheduling framework. In this model, if one composed stream is guaranteed to meet (m,k)-firm requirement, it iteratively ensures that the respective requirements of the composing stream will be met.


    On the basis of this model, multiple flows are aggregated as a new stream. To build a new composed stream, we need to define a new stream by considering the parameters in each flow. The proposed procedure is performed with two flows. If there are more flows to be aggregated, repeated aggregation is required. For example, if two separate streams, Fi and Fj, are given, a new stream is denoted by setting each parameter for the flow to decide a new (m,k)-firm stream is as shown in Eq. (4).

    In other words, as the new aggregated flow should not violate the requirement of the two composing streams, m is a more important parameter than k. k is simply defined by adding the two k values in the flows. On the other hand, m is considered to have min (kimi, kjmj). Therefore, any drop packet in the new stream does not violate the original two streams’ (m,k)-firm requirements. In the case of priority, we take the minimum value to guarantee a real-time delivery. Further, the earlier of the two deadlines is chosen as the new deadline for the aggregated flow. This procedure makes the aggregated stream stricter with respect to the above-mentioned requirement.

    Upon completing the aggregation, for the delivery of the (m,k)-firm stream, we use the (m,k)-firm specific routing protocol, which was proposed in [12]. In the proposed scheme, a velocity-balanced and energy-balanced real-time routing approach is used for ensuring positive DBP values.


    The performance of the proposed scheme is proven by the simulation scenarios. We use ns-2 as the simulator. The simulation terrain is set as a field measuring 200 m × 200 m. The sink is located at the lower-right corner of the field so that the end-to-end hop count ranges from 4 to 9 hops with an average of 6 hops. Each node has a radio range of 40 m. The propagation model is set to a two-ray ground protocol for a physical connection and is set to be wireless-phy in ns-2.

    For the application, the deadline for a real-time packet on each node is set to varying values by considering the average link delay and the number of shortest hops. The comparative protocols are presented in my previous work in [12]. For the (m,k)-firm stream, (4,5), (3,4), (2,3)-firm streams are used where the initial period of the sensing of (4,5) is set to 250 ms, and the other two streams are set to 500 ms and 1 s, respectively. Further, we evaluate the clustering parameter by using the deadline by setting α as 0.1 in Eq. (2).

    The evaluation result is presented as the stream dynamic failure ratio (SDFR). It refers to the timeliness of an individual packet, which is considered to be the most important feature in a real-time application. For the abovementioned performance parameters, we use two scenarios. First, we increase the number of source nodes with a fixed event period. Second, we have the decreasing event period with a fixed number of source nodes. In both scenarios, we compute the SDFR of all flows and calculate their average.

    As shown in Fig. 2, SDFR generally increases with an increase in the number of source nodes where New represents the proposed clustering scheme. A more considerable difference between the two approaches is observed in the case of a large number of source nodes. Since two protocols use the same routing protocol, the difference is mainly attributed to the clustering scheme. As the number of source nodes increases, there is a high probability of cluster formation in the proposed scheme. Therefore, more clusters are created and the aggregated flows reduce the failure probability discussed in my previous work. However, because of the overhead caused by the clustering, a relatively long delay is measured in each round.

    A similar pattern is observed in Fig. 3, which illustrates SDFR according to event period. In the short period, more flows are transmitted by aggregation. Therefore, the failure probability is reduced. However, during the configuration time required to form a cluster, real-time delivery is not available. Therefore, many packets cannot meet the real-time requirement as compared to those in the long message period.

    Another simulation result is for the network lifetime, which is defined as the elapsed time until any area is not covered by a sensor node. In other words, it is referred to as the moment when the first hole is created. As the energy model, we adopt the MICAz IEEE 802.15.4 specification model.

    As shown in Fig. 4, the network lifetime is largely dependent on the number of sources. However, the network lifetime decreases with an increase in the number of sources. Because of the battery consumption for each flow, the previous scheme is not appropriate for a long operation. However, since the proposed scheme does not take energy consumption into account to determine CH, its network lifetime has to be extended. Further, since aggregation is only accomplished when the (m,k)-firm streams in the geocast area have similar properties. These two conditions lead to a small gap between the new and the previous scheme.


    In this paper, we proposed a clustering scheme for an (m,k)-firm stream in wireless sensor networks. We explained how CH was formed while considering the (m,k)-firm requirement. The aggregated flow at the CH contributed to the solution of the scalability problem discussed in a previous research work. Finally, the simulation results demonstrated that the clustering could improve the failure probability for real-time traffic.

    In the future, I intend to consider the energy consumption in order to prevent a specific node from serving CH sequentially when the header is decided. To this end, I intend to develop a more feasible procedure with additional parameters.

  • 1. He T., Stankovic J. A., Lu C., Abdelzaher T. 2003 “SPEED: a stateless protocol for real-time communication in sensor networks,” [in Proceedings of 23rd International Conference on Distributed Computing Systems] P.46-55 google
  • 2. Felemban E., Lee C. G., Ekici E. 2006 “MMSPEED: Multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks,” [IEEE Transactions on Mobile Computing] Vol.5 P.738-754 google doi
  • 3. Zhao L., Kan B., Xu Y., Li X. 2007 “FT-SPEED: a fault-tolerant, real-time routing protocol for wireless sensor networks,” [in Proceedings of International Conference on Wireless Communications, Networking and Mobile Computing] P.2531-2534 google
  • 4. Al-Jarrah O., Salhieh A., Qaroush A. 2010 “Real-time power-aware routing protocol for wireless sensor network,” [in Proceedings of International Conference on Information Systems, Technology and Management (ICISTM)] P.156-166 google
  • 5. Kim J., Ravindran B. 2009 “Opportunistic real-time routing in multi-hop wireless sensor networks,” [in Proceedings of the 2009 ACM Symposium on Applied Computing] P.2197-2201 google
  • 6. Kaebeh Yaeghoobi S. B., Tyagi S. S., Soni M. K., Omid Mahdi Ebadati E. 2014 “SAERP: an energy efficiency real-time routing protocol in WSNs,” [in Proceedings of International Conference on Optimization, Reliability, and Information Technology (ICROIT)] P.249-254 google
  • 7. Zeng Y., Sreenan C. J., Sitanayah L. 2010 “A real-time and robust routing protocol for building fire emergency applications using wireless sensor networks,” [in Proceedings of 8th IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops)] P.358-363 google
  • 8. Xu Y., Ren F., He T., Lin C., Chen C., Das S. K. 2013 “Real-time routing in wireless sensor networks: a potential field approach,” [ACM Transactions on Sensor Networks] Vol.9 google doi
  • 9. Rachamalla S., Kancharla A. S. 2013 “A survey of real-time routing protocols for wireless sensor networks,” [International Journal of Computer Science & Engineering Survey] Vol.4 P.35-43 google doi
  • 10. Kim K. I., Sung T. E. 2010 “Network layer approaches for (m,k)-firm stream in wireless sensor networks,” [IEICE Transactions on Communications] Vol.93 P.3165-3168 google doi
  • 11. Hamdaoui M., Ramanathan P. 1995 “A dynamic priority assignment technique for streams with (m,k)-firm deadlines,” [IEEE Transactions on Computers] Vol.44 P.1443-1451 google doi
  • 12. Kim K. I., Sung T. E. 20 “Modeling and routing scheme for (m, k)-firm streams in wireless multimedia sensor networks,” [Wireless Communications and Mobile Computing] Vol.15 P.475-483 google doi
  • [] 
  • [] 
  • [] 
  • [Fig. 1.] Example of clustering.
    Example of clustering.
  • [] 
  • [Fig. 2.] SDFR as a function of source nodes.
    SDFR as a function of source nodes.
  • [Fig. 3.] SDFR as a function of the message period.
    SDFR as a function of the message period.
  • [Fig. 4.] Network lifetime as a function of source nodes.
    Network lifetime as a function of source nodes.