A Cross-Layer-Based Clustered Multipath Routing with QoS-Aware Scheduling for Wireless Multimedia Sensor Networks

Abstract

Wireless multimedia sensor networks (WMSNs) can handle different traffic classes of multimedia content (video, audio streams, and still images) as well as scalar data over the network. To ensure correct delivery of real-time multimedia data and efficient resource utilization, a proposed solution should provide both quality of service (QoS) assurance and energy efficiency. In this paper, we propose a cross-layer-based routing protocol that can utilize MAC-layer QoS-based scheduling for more efficient routing mechanism in WMSNs. Our proposed optimization is based on clustered multipath routing protocol and adaptive QoS-aware scheduling for the different traffic classes in WMSNs. Our design exploits the hierarchical structure of powerful cluster heads and the optimized multiple paths along with the adaptive scheduling to support reliable, high-throughput, and energy-efficient multimedia transmission in WMSNs. Simulation results show a significant performance improvement of our proposed design when compared to other similar routing schemes.

1. Introduction

WMSNs [1, 2] are able to deliver multimedia content due to the availability of inexpensive complementary Metal oxide semiconductor (CMOS) cameras and microphones coupled with the significant progress in distributed signal processing and multimedia source coding techniques. The additional requirements of delivering real-time multimedia data—such as high bandwidth demand, tolerable end-to-end delay, proper jitter, and frame loss rate—along with many resource constraints in WMSNs should be considered probably at different layers of the communication protocol stack. Most of the existing proposed protocols designed for WMSNs follow the classical layered structure of the communication protocol stack without taking into consideration the especial requirements of handling real-time multimedia content over WMSNs. Some of these proposals may achieve a good performance in terms of some metrics related to each of their intended individual layers, but these performance metrics are not jointly optimized to maximize the overall network performance with minimum energy consumption. Nevertheless, the correlation characteristics and interdependencies among the layers of the communication stack in WMSN cannot be neglected and should be exploited for better performance and efficient communication. Therefore, cross-layer optimization can be the solution to meet the especial requirements of WMSN and its design challenges [3] in order to provide enough support for multimedia applications and maximize network performance.

Routing in WMSNs is very challenging and critical because of their characteristics and constraints that make them different from the existing communication and scalar wireless sensor networks [1, 4], such as (1) large number of heterogeneous sensor nodes with different capabilities and functionalities is deployed; (2) careful resource management for multimedia transmissions is required as sensor nodes are tightly constrained in terms of battery energy, processing power, storage capacity, and available bandwidth; (3) also delivering the collected multimedia data in WMSNs (video streaming, still images, and audio) adds more constraints on the design of the routing protocols in order to meet their QoS requirements such as end-to-end delay, SNR (signal-to-noise ratio) level, and packet (frame) loss rate; (4) in addition, the use of densely deployed nodes provides significant redundancy in the collected sensor data, for example, overlapping of FoVs (Field of Views) of camera sensors. Such redundancy needs to be exploited to improve energy and bandwidth utilization, and for more accurate and robust observation results.

In general, two types of WMSNs architecture are widely used [1]: flat and hierarchical (cluster-based) network architecture as shown in Figure 1. In flat architecture, the network is deployed with homogeneous sensor nodes of the same capabilities and functionalities, which can perform any task from image capturing through multimedia processing to packet relaying toward the sink in multihop basis. On the other hand, at cluster-based architecture, the network is divided into clusters. Heterogeneous sensor nodes are deployed in each cluster, where camera, audio, and scalar sensors relay data to a cluster head that has more resources and is able to perform intensive data processing. The cluster head is wirelessly connected with the sink or the gateway either directly or through other cluster heads in multi-hop fashion. For WMSNs, cluster-based network architecture has more advantages than a flat network especially for image processing and transmissions. In the homogeneous flat network, all the nodes should have the same hardware capabilities and functionalities for multimedia processing and transmission, and this leads to increase the energy consumption and the cost of the deployed network. Also, a single-tier flat architecture can cause the sink to overload with the increase in sensors density, which can affect the performance of the network and cause latency in communication and tracking events. Moreover, in cluster-based network, cluster heads can perform data aggregation and filtering to reduce the amount of transmitted data and do better scheduling among the nodes within clusters.

Figure 1

Flat versus hierarchical network architecture.

Design of an efficient QoS-aware MAC protocol [5, 6] is another important step for correct delivery of real-time multimedia data and for end-to-end QoS provisioning over WMSNs. It is desirable that the MAC layer provides reliable and error-free data transfer with minimum retransmissions while meeting the QoS requirements with efficient resource utilization. The existing sensory MAC protocols are mostly based on variants of the carrier sense multiple access with collision avoidance (CSMA/CA) [7] and time division Multiple Access (TDMA) [6]. Contention-based approach, such as CSMA/CA, is preferred when network traffic load is not very intensive, and the channel condition is relatively unreliable because the probability of potential collision and congestion is low. However, for heavier traffic loads as the case of WMSNs, contention-based approach leads to increase wasted energy and delays due to idle listening and collisions produced with large preamble and hidden node problems. On the other side, contention-free approach, like TDMA, is more appropriate for multimedia applications with reliable channel conditions and heavier traffic load. However, it suffers from clock synchronization problem, in addition to channel underutilization and fixed time-slot assignments in case of static slotted scheduling.

A quick look into the existing proposals in routing protocols in sensor networks reveals that they are following the standard structure of the communication protocol stack and do not pay attention for the interdependencies and joint functionalities among the layers especially the routing and MAC layers. Therefore, in this paper, a cross-layer design is proposed between the routing and MAC layers where a clustered multipath routing protocol is pursued in conjunction with an adaptive QoS-aware scheduling to optimize the performance of the routing and reliable delivery with minimum resource consumption.

Our proposed routing protocol aims to cluster the nodes using clustering algorithm based on the received signal strength, in a way that keeps strong connections among the nodes with maximum number of multiple paths suitable for the different requirements of handling different traffic classes. In each cluster, powerful cluster heads have the capability to do some intensive multimedia processing and aggregation in order to reduce the transmitted amount of data for saving energy consumption and bandwidth usage. Our proposed scheduling mechanism is based on adaptive QoS-aware TDMA approach used at two levels in the network: within clusters and among cluster heads. Our algorithm uses flexible time-slot assignment where a cluster head is responsible to schedule the traffic toward the sink from the sensor nodes based on the type of data and its availability.

The rest of the paper is organized as the following: Section 2 introduces an overview of existing related works. Section 3 provides network architecture and system model and assumptions. Section 4 describes the cluster-based multipath routing protocol in details. Section 5 presents the adaptive QoS-aware scheduling mechanism. Section 6 presents the performance evaluation. Finally, Section 7 concludes the paper.

2. Related Work

Several cross-layer and communication protocols were developed to address the aforementioned issues for WMSNs and surveyed in [8]. Here in this section, we focus on cross-layer optimization proposals that include routing and scheduling functionalities, and we summarize them in Table 1.

Table 1

Cross-layer design and communication protocols for WMSNs.

Protocol	Network Modality	Operational Layer	Performance Metric
DHCT [9]	Standard	Routing	Transmission-count/delay
COM-MAC [10]	Cross-layer	Routing/MAC	Bandwidth/delay
MCRA [11]	Standard	Routing	hop count/delay
Li et al. [12]	Cross-layer	Application/Routing	Distortion
Chen et al. [13]	Cross-layer	Routing/MAC	Bandwidth/delay/path energy
UWB-based Protocol [14]	Cross-layer	Routing/MAC/ Physical	end-to-end resource reservation
MPMP [15]	Cross-layer	Transport/Routing	Distance/delay/data type
QoS-SDMR [16]	Cross-layer	Application/Routing/MAC	Bandwidth/delay/distortion
CMRP	Cross-layer	Routing/MAC	hop count/RSSI

A routing protocol, DHCT [9], is proposed for WMSNs to support multipath routing and to reduce interferences between close paths by using a performance metric (called Costp), which is product of expected transmission count and the delay. Using Costp metric allows selecting paths with minimum interferences to each other, hence it will increase throughput. Also DHCT reinforces multiple links at the sink to obtain disjoint path from the source for multipath routing. However, this routing protocol does not consider the bandwidth as QoS metric for routing decision or prioritizes the incoming packets to schedule them as the case in CMRP, but it does consider the playout deadline in a sense that the packet arrives after the deadline will be discarded. Also having only disjoint paths means not considering interconnecting paths that can be effectively used along with packet scheduling to utilize the available capacity and increase throughput.

COM-MAC [10] is a multichannel multipath MAC protocol with packet scheduling to meet the bandwidth and delay requirements in WMSNs. The routing protocol uses multiple paths, multiple channels, and QoS packet scheduling technique based on the dynamic bandwidth adjustment and path-length-based proportional delay differentiation (PPDD) techniques. These requirements (bandwidth and delay) are adjusted locally at each node based on the path-length and incoming traffic in static flat wireless network where all the nodes are homogeneous multimedia sensor nodes for the same capabilities (video, audio, and scalar data) and equipped with single radio interface and multichannels. However, unlike CMRP, it uses static time slots at control channel and does not propose any mechanism for passive nodes for better channel utilization. CMRP uses adaptive time slots assignment that can be changed dynamically depending on data availability, data type, and number of active nodes.

Another multiconstrained routing algorithm, MCRA [11], is proposed to provide end-to-end delay and packet loss ratio suitable for multimedia content and balance the energy consumption. In MCRA, routing discovery starts at the sink node that floods the network with interest messages. The source node that receives these interest messages and matches the needed query selects the path of minimum hop count to send its data. When receiving data packet, the sink node calculates the coordinates of the source node using the logical coordinates (hop count). MCRA tries to reduce the amount of flooding by either not forwarding the interest messages already received them before, or by merging multiple interests in one message. However, the routing depends on flooding the network with interest messages from sink to sources using all nodes to find the paths, not only using some powerful nodes to discover the routes as in CMRP. Also, the selection of the paths by the sources in MCRA is based only on minimum hop count without considering the quality of the link that can be estimated from the received signal strength as in the case of CMRP.

The cross-layer design described in [12] jointly optimizes the source coding techniques for multimedia processing and compression in the application layer with the network coding along with the routing functions to minimize the distortion with maximum network lifetime following multiple paths. However, this approach does not provide any proposal for controlling node channel access or scheduling process among the nodes based on the data type, and thus interferences and collisions cannot be avoided which leads to degrade network throughput and the quality of received data.

Another cross-layer design for WMSNs is implemented in [13] where an extension of a geographical routing protocol is presented for multipath routing along with path priority scheduling algorithm for efficient communication of real-time video over WMSNs. Using hop-by-hop deviation angle adjustment method, a path can be established using any initial deviation angle specified at the source node, and then other disjoint paths are constructed by changing the value of the deviation angle. If there is no path satisfying the required data rate, video coding parameters are adapted along with using frame skipping, reference frame selecting, and intraframe refreshing techniques in order to lower the bandwidth consumption. To meet the delay constraint of video frames, a path priority scheduling algorithm is used that gives a weight for each path calculated based on the estimated available bandwidth, path delay, and path energy level. Then, by using path weight along with packet priority, shorter delay paths will be used for time-constrained packets, while other paths are used for balancing energy and bandwidth usage for other traffic. However, like most geographical routing protocols, the proposed cross-layer design assumes that nodes are location aware and that the density of nodes is high.

A cross-layer system is presented in [14] to provide QoS for WMSN applications based on the time-hopping impulse radio ultrawideband (TH-IR-UWB) transmission technique. This architecture tries to solve the shortcomings of using CSMA/CA for the MAC layer and to provide QoS for WMSNs. Routing process starts at the source nodes by sending request packets describing their requirements to their neighbors, and among the replies, a source node selects the one who has the most positive advance toward the sink and is able to satisfy the needed requirements, and this continues iteratively until the end-to-end path is established to the sink. The cross-layer system also provides dynamic channel coding and receiver-centric scheduling based on time hopping sequence of impulse radio of ultrawideband MAC and physical layer. This allows for multiple parallel transmissions, prevents collisions at the receiver node (by using unique TH sequence for each receiver), and saves energy by avoiding idle listening and wasteful transmissions (by turning on exactly the incoming transmission). However, this cross-layer system is based on end-to-end resource reservation that causes higher overhead, and it does not consider the source rate adaptation with the network conditions.

In [15], a context-aware cross-layer multipath multipriority (MPMP) transmission scheme is proposed where algorithms in routing and transport layers are used. In this scheme, a multipath geographic routing protocol is used to explore maximum number of node-disjoint routing paths. Also, a context-aware multipath selection algorithm in the transport layer is used to choose the maximum number of paths from all found node-disjoint paths for maximizing the delivery of the important data to the sink. The selection algorithm selects the proper routing paths that are suitable for each type of multimedia content based on two types of priority: end-to-end transmission delay-based priority for constraint real-time video communication and context-aware multimedia-based priority (image versus audio) for the most valuable information to the sink. However, the underlying routing protocol considers only the distance between the nodes and the sink to discover the routes and does not take into account other important parameters such as link quality and bandwidth. Also, this protocol does not support different type of traffic (video and scalar data at the same time).

A cross-layer framework is presented in [16] for QoS support in WMSNs, which optimizes the functionalities of communication protocols to maximize the number of video stream requests to be delivered without affecting their quality. The proposed design uses a source-directed multipath routing (SDMR) protocol that interacts with enhanced IEEE 802.11e MAC standard for QoS scheduling, and data link layer for multirate transmission modes. Also the cross-layer design is capable of interacting with the application layer to choose an appropriate group of picture (GoP) size according to network conditions and the feedbacks received from the sink. However, the SDMR routing protocol assumes a flat network with dense deployment for sensor nodes for estimating the upper bound number of hops in order to calculate the required end-to-end delay. Also SDMR establishes only disjoint paths (maximum three noninterfering paths) from a source to the sink.

3. System Model

The network is divided into clusters using our proposed routing protocol, called CMRP, where each cluster is deployed with heterogeneous sensors (camera, audio, and scalar sensors) that communicate directly in a certain schedule with a cluster head and relay their sensed data to it. However, these heterogeneous sensor nodes have the same radio interface and propagation range. A cluster head has more resources, and it is able to perform intensive data processing. These powerful nodes, cluster heads, are deployed uniformly in the network, and they are wirelessly connected with the sink either directly (in case of 1st-level cluster heads) or through other cluster heads in multihop fashion.

CMRP is based on hop count and received signal strength index (RSSI) of the sensory message as an indication of the link quality and distance between the nodes. RSSI can be calculated in a large-scale wireless sensor network using the following propagation model:

$P_r=P_t{G}_t{G}_r{\left(h_t{h}_r\right)}^2{d}^{-4}{L}^{-1},$

(1)

where $P_t$ and $P_r$ are the power level of transmitted and received message, respectively, $G_t$ and $G_r$ are the transmitter (Tx) and receiver (Rx) antenna gain, respectively, $h_t$ and $h_r$ are antenna height for the Tx and Rx, respectively, d is the distance between the Tx and the Rx, and L is system loss factor. Then,

$\text{RSS}=\frac{P_r}{P_t}⟶\text{RSS}=G_t{G}_r{\left(h_t{h}_r\right)}^2{d}^{-4}{L}^{-1}.$

(2)

If we assumed that antenna gain of the Tx and Rx is equal to 1, antenna height of the Tx and Rx is equal to 1, and L also equals 1, then RSSI can be approximated as a function of distance between the Tx and Rx as a dominating factor affecting its value $\text{RSS}\approx 1/d^4$ .

For more accurate propagation model, signal-to-noise ratio (SNR) and bit error rate (BER) should be taken into account along with the received signal strength in order to consider noises (from receiver and environment) and interferences from other packets arrived simultaneously:

$\begin{array}{c}\text{SNR}=10\log \left(\frac{P_r}{N_p+{\sum }_i^{n-1}{P}_r}\right),\\ \text{BER}=0.5\times \mathrm{erfc}\left(\sqrt{\frac{P_r\times \text{BW}}{N_p\times R}}\right),\end{array}$

(3)

where BW is the channel bandwidth, $N_p$ is noise power, n is number of interfering packets, and R is data rate.

4. Cluster-Based Multipath Routing in WMSN

This section describes the routing operation of our proposed clustered multipath routing protocol for WMSNs, CMRP, which is based on the hierarchical structure of multiple paths established depending on hop count and received signal strength (along with measured SNR and BER) as an indication of the link quality and distance between the nodes. CMRP depends on the local information exchanged among the nodes to establish the routes to the sink and does not require any coordination measurement equipments or position message exchange.

4.1. Route Discovery

Here, we explain our proposed clustered multipath routing protocol, CMRP, and then we demonstrate the scheduling algorithm in the next section. We are using two performance metrics: hop count (as indication for distance from the sink and delay) and received signal strength index RSSI (combined with SNR & BER) as indication for link quality (interference and noise level) and distance from the sender. Two thresholds (upper and lower) are used to compare with the packet's RSSI.

The selection of the values of the two thresholds is very critical in clustering the network and connecting them together. The upper threshold is used to determine the 1st-level cluster heads and group member nodes (as described below). The upper threshold should be adjusted in a way that it should not be very large value (close to the max value) so that you will not find any node receives your message in this power level or only a few nodes. In this case, the cluster size will be very small with many chances of having only singleton clusters, and the load will be high on few 1st-level cluster heads for serving many paths passing through them. Also if the upper threshold is low (below the midvalue close to the lower threshold), the cluster size will be very high and cause cluster heads to overload with many group members and suffer high interferences in both inside clusters and at the sink side. The lower threshold is used to establish the links between cluster heads. Having a relatively high value of the lower threshold (close to the midvalue) may prevent connecting the cluster heads in different levels and this leads to have a weak network connectivity. Also if the lower threshold is very low (close to the midvalue), then the network can have low link quality links between cluster heads with high possibility of packet drops.

In the initializing phase of CMRP, the base station starts sending periodic broadcast messages, called BS-Msg, to the surrounding powerful nodes. The nodes that receive BS-Msgs compare the RSSI with the upper threshold (Thr-High). If RSSI is greater than Thr-High, these nodes respond to the base station by sending back acknowledgment messages informing their joining the base station as their parent. Then, they start acting as 1st-level cluster heads (1st CH)—as shown in an example in Figure 2—and broadcast periodically control messages called CH-Msg to their neighboring nodes. CH-Msg contains the ID of the CH, number of hops between the CH and the sink in the current found path, and IDs of the nodes joining this path up to the current CH. For each CH-Msg received by the surrounding nodes of the 1st CHs, RSSI is measured and compared with the two thresholds, Thr-High and Thr-Low.

Figure 2

An example of clustered multipath WMSN.

If the signal strength of the received CH-Msg is greater than Thr-High, the receiving node will start behaving as a group member (GM) and send back an acknowledgment message informing its joining to the corresponding CH. Receiving a CH-Msg with RSSI greater than Thr-High indicates that the sender (CH) is in near region and the quality of the link is good, and thus, this CH can better serve the communication toward the base station. In case a node receives more than one message from different CHs with RSSI larger than Thr-High, the node selects the cluster head of the highest RSSI value, as shown in pseudocode of CMRP in Algorithm 1.

Algorithm 1: The pseudocode of the main routing process of CMRP.

(1) Broadcasting authenticated BS-Msg periodically

(2) For each node i receives BS-Msg→Calculate RSSI

     if RSSI > Thr-High

    act as (1st-level) CH

    send authenticated CH-Msg periodically

    else

     ignore BS-Msg

       End if

    End for

( $3)$ For each node i receives CH-Msg →Calculate RSSI

    if RSSI > Thr-High

    act as GM

    add sender to CH-table

    start selectMyCH_timer

    else

    if RSSI > Thr-Low

    act as CH

    add sender to parent_table & add path to available_paths_table

    start selectMyParent_timer

    else

   ignore CH-Msg

    End if

     End for

(4) After selectMyCH_timer or selectMyParent_timer expired:

  For each CH →select parent from parent_table &

         select corresponding path from available_paths_table

         suitable for each traffic class

  For each GM → select CH from CH-table with max RSSI

The powerful nodes that only receive messages with RSSI between Thr-High and Thr-Low will start acting as new cluster heads, in this case 2nd-level CHs, and respond back to the sender informing their selection of him as one of their possible parents toward the base station. New CHs may receive different CH-Msgs from previous-level CHs. In this case, new CHs consider these messages in order to construct multiple paths toward base station and sort these paths based on certain criterions (such as link quality, end-to-end delay, bandwidth, or number of hops in the path). Paths with good conditions, like high link quality, short end-to-end delay, enough bandwidth, or less number of hops, are reserved for multimedia communication that requires certain level of quality of service requirements. Other paths will be used for other types of data that does not require strict QoS requirements such as scalar data. If the RSSI is less than Thr-Low, the message is considered as lost or ignored. This process continues in the same manner to build the network until all nodes join the network and determine their roles, that is, cluster head or group member, and all possible paths are found.

In case that cluster heads do not receive any message from other nodes informing joining them as group members (i.e., singleton clusters), then these cluster heads will behave either as (1) forwarder nodes to relay data toward the sink, if they receive messages from other powerful nodes informing their joining as next-level cluster heads, or (2) temporarily normal nodes, group members, and join any other closer clusters based on RSSI. These nodes can create later on their own clusters when new group members nodes are deployed in their vicinity.

After the network is established and all possible routes are found, base station and cluster heads will reduce the rate of sending broadcast control messages (BS-Msg, CH-Msg) in order to save channel capacity and energy. We keep sending these broadcast messages even with lower rate, which has a negligible effect on the network performance, for the sake of adding new nodes to the network.

4.2. Route Optimization

In order to optimize the found routes in route discovery phase, path loops and path cycles should be prevented. For path loops, each CH that receives CH-Msg from other nodes checks first the IDs of the nodes joining the path to know whether it already joined this path before or not. If a CH receives CH-Msg belongs to one of the paths already found before, it checks the conditions and the status of the given path in order to update its routing information about this path and reflects these changes (if any) on its decision of selecting the proper path for each type of data. Moreover, for path optimization with minimum number of hops, a CH checks for every given path whether it is a child for any participating node in this path (except of course its direct parent in this path). In this case, it is better for the CH to communicate directly to that parent instead of making a path cycle. Thus, if a path cycle is found, the cluster head deletes this path from its routing information and keeps the shorter path.

4.3. Local Repair

The acknowledgment system is critical for WMSNs to achieve a low frame loss rate that affects the quality of video perception and to detect any node or link failure. After receiving a certain number of data packets, a CH sends an acknowledgment message (Ack-Msg) to the sender (lower-level CH or GM) and in the same manner waits an Ack-Msg from its parent (higher-level CH or sink) confirming receiving the data packets. So, if a node did not receive an Ack-Msg from its parent, it will assume that there is a node failure or link failure, and it will select another parent (i.e., another path)—depending on its routing information tables—suitable with the current type of data. There is no need to initialize the entire network for establishing the routes again in order to overcome the existing failure; it just affects the nodes along the failed path and because of that it is called local repair. If the parent is the sink, and there is no response from its side, then the node should communicate with other reachable 1st-level CHs, based on RSSI, to deliver data packets through them. If this node cannot communicate with any 1st-level CH, then it should send negative Ack-Msg to its children nodes (lower-level CHs and GMs) informing about this link failure. Then children nodes will have to select another parent CH according to their routing information table.

The same procedure is used with GMs to check their CH. After sending a certain number of data packets, a GM waits an Ack-Msg from its CH confirming receiving those packets. If the GM did not receive Ack-Msg, then it assumes that there is a link failure or node failure and joins another CH based on its routing information table.

4.4. CMRP Life Time Analysis

In this subsection, we are interested in analyzing the effect of multipath routing in the expected life time of a link between a CH and BS. According to CMRP, a link (P) consists of multiple paths where each path ( $p_i$ ) contains a certain number of intermediate CHs (n). A path will be broken once the battery energy ( $E_i$ ) of any intermediate node residing on it depleted. $E_i$ is independent random variable distributed uniformly between 0 and $E_{\max \hspace{0.17em}}$ (full battery energy), and for simplification, we can express $C_i=E_i/E_{\max \hspace{0.17em}}$ where $C_i$ now is an independent random variable uniformly distributed between 0 and 1. Then, we can define the following parameters.

Path life time:

$p_i=\min \left(C_1,C_2,\dots ,C_{n_i}\right).$

(4)

Link life time:

$P={{\displaystyle \sum }}_{i=1}^N\left(p_i\right),$

(5)

where n is the number of nodes in the path i, and N is the number of paths in the link P.

Then the expected (average) life time of the link (P) is

$\mathbb{E}\left\{P\right\}=\mathrm{\hspace{0.17em}\hspace{0.17em}}{{\displaystyle \sum }}_{i=1}^N\mathbb{E}\left(p_i\right).$

(6)

Since all node energy indexes ( $C_i$ ) are random variables uniformly distributed between 0 and 1, then the minimum random variable along one path $p_i$ follows a Beta distribution with parameters 1 and n. The probability density function of Beta distribution is as follows:

$f(x;\alpha ,\beta )=\frac{x^{\alpha -1}{\left(1-x\right)}^{\beta -1}}{B\left(\alpha ,\beta \right)},$

(7)

where $B(\alpha ,\beta )$ is the beta function:

$B\left(\alpha ,\beta \right)={{\displaystyle \int }}_0^1{t}^{\alpha -1}{\left(1-t\right)}^{\beta -1}dt.$

(8)

Then substituting $\alpha =1$ and $\beta =n$ gives us the probability density function of the path life time:

$\mathbb{P}\left\{p_i=x\right\}=n\cdot {\left(1-x\right)}^{n-1}.$

(9)

As the mean value of the Beta distribution is $\{X\}=\alpha /(\alpha +\beta )$ , then the expected path life time of this probability function can be expressed as

$\mathbb{E}\left\{p_i\right\}=\frac{1}{n+1}.$

(10)

Finally, the average link life time can be calculated as:

$\mathbb{E}\left\{P\right\}=\frac{N}{n+1}.$

(11)

5. Two-Level QoS-Aware Scheduling

After establishing the network and before data transmission, we introduce two-level QoS-aware scheduling as shown in Figure 3: low-level scheduling within each cluster among the GMs and high-level scheduling among the cluster heads in order to increase the packet delivery ratio and throughput for multimedia data.

Figure 3

A simple example of two-level scheduling.

Besides their low energy efficiency, most contention-based protocols are generally not designed for sending real-time multimedia data and are not suitable for delay-sensitive WMSNs because each node has to contend for medium access to send every packet; thus, the delay for data delivery could be potentially unbounded. The needed time required to resolve collision is based on the load condition of the network and number of nodes in clusters, which makes it very difficult to guarantee a bounded delay. Therefore, we prefer to adopt TDMA protocol to access the channel as it has a natural advantage of collision-free medium access, and it is more appropriate for transmitting multimedia applications with QoS at reliable channel conditions and heavier traffic load. In order to avoid channel underutilization and to decrease the delay, dynamic time slot is assigned to the nodes depending on the amount of data to be transmitted and the time for sending Ack-Msgs if needed.

At low level, each CH should schedule the data transmissions among its GMs within the cluster in order to give higher priority to the nodes that demand higher or strict QoS requirements for their data and to avoid collisions and interferences.

The low-level scheduling process is initiated by the CH by sending a broadcast message asking each GM in the cluster to send their requests informing about the type of data to be transmitted, its amount, and its requirements (such as playout deadline, BW, etc.). This broadcast message, Assign-Msg, contains the control slot assignment (i.e., time slot to each GM) in the cluster. The duration of the control slot is enough to any node in the cluster to send its request message (Req-Msg), and the time slot is unique for each GM to avoid collisions. During the request phase, each GM sends a Req-Msg to its CH at the allocated time slot informing about the data to be sent (if available) and its QoS requirements.

Then based on the collected information from the request phase, each CH generates a transmission schedule for the active GMs and distributes it in the cluster. The resulting schedule is sent to all GMs by broadcasting a scheduling message, Sched-Msg, to inform each GM with the specified time schedule for sending each type of data. The duration of the time slot depends on the amount and type of data to be transmitted as requested by each GM.

By this way, multimedia streaming and time-critical data can be transmitted first, then less priority data such as still images and then scalar data can be sent later. Moreover, for better energy efficiency, GMs can turn off their radio transceiver when the schedule has been received until the time slot for transmitting a certain data type approaches or to the end of the data transmission phase if they are passive nodes. After receiving the schedule, each GM will transmit its data during the assigned time slots for each data type and the CH sends, after receiving a certain number of data packets, an Ack-Msg to the sender as described before. When the data transmission phase completes, a CH sends again the Assign-Msg to its GMs to send their requests. The time intervals of the scheduling operation in a cluster are shown in Figure 4.

Figure 4

A cluster time intervals for scheduling process.

At higher level, each intermediate cluster head—in the same manner done at low level—schedules the traffic toward the sink from other cluster heads (its children) based on the type of the data and its QoS requirements.

6. Performance Evaluation

We simulate our proposal using NS-2 v2.34 [17] for over 100 experiments with various random topologies. The network size is 500 m × 500 m deployed with number of nodes ranging from 50 to 175 in randomized grid for duration of 1000 s. The sink is located in the center of the network. The traffic is CBR of 600  packet/second, and the packet size is 316 bytes. We adopt IEEE802.11 for the MAC layer as shown in Table 2, which lists the parameters we used in our simulation. We used “Salvat Cluster” that has the features shown in Table 3 to run our simulation.

Table 2

Simulation environment and used parameters.

Simulation parameter	Value
Simulation time	1000 s
Network size	$500\times 500$  m2
Node number	50–175
Link layer	LL
MAC layer	IEEE802.11
IFQ type	Queue/DropTail/PriQueue
IFQ length	10
Antenna type	Antenna/OmniAntenna
Physical type	Phy/WirelessPhy
Channel type	Channel/WirelessChannel
Energy model	EnergyModel
Bandwidth	2 MB

Table 3

Features of Salvat Cluster and its picture.

Features	Salvat Cluster
* USP 73 nodes Xeon Dual-Core 5148
* Motherboard Intel S5000VCL
* Intel SR1530 chassis
* Intel 5000 V
* 2 Dual-Core Intel Xeon 2.333 GHz, 1333 MHz FSB, 4 MB Cache
* 12 GB RAM in 6 modules of 2 GB
* Hard Drive Seagate Barracuda 320 GB S-ATA-2
* 2 Intel PRO/1000 Gigabit Ethernet network cards

In the simulations, we focus on measuring the performance metrics after the network has set up to exclude the communication overhead of the most exchanged control messages. Control messages include broadcast messages (BS-Msg, CH-Msg) sent at very low rate and acknowledgment messages (Ack-Msg) used for data receiving notification and local repair. However, these control messages are considered in measuring the energy consumption during simulation time.

Figure 5 shows the end-to-end delay, which is one of the important QoS parameters as the real-time multimedia packets have strict playout deadlines. We compare the average end-to-end delay of our proposed routing protocol combined with the two-level scheduling technique (CMRP+2_level scheduling) with the proposed routing protocol only (CMRP only) and the other protocols (DHCT and MCRA). We select these protocols to compare with to show how our proposed cross-layer design methodology will outperform the other recent protocols that are based on the classical layered structure of the communication stack.

Figure 5

End-to-end delay performance of our protocol.

It is shown clearly that our cross-layer design has the minimum end-to-end delay and outperforms the other protocols because it depends on selecting the path of better link quality and minimum hop count through powerful cluster heads. Notice that CMRP only performs well at low node density, but with dense deployment end-to-end delay increases significantly due to the interferences and collisions within the clusters and among cluster heads which cause retransmission lost packets again.

Our proposed cross-layer protocol achieves higher throughput, as shown in Figure 6, than the other protocols by efficiently utilizing the wireless spectrum and distributing the load via adopting adaptive TDMA-based scheduling and selecting multiple paths of better link quality and minimum delay, respectively. Without implementing the scheduling scheme, we notice that CMRP-only's performance is degrading with increasing the number of nodes due to the time wasted for retransmitting lost packets and changing paths to overcome the interferences and collisions and hence lead to decrease number of received packets at the sink during the simulation time.

Figure 6

Throughput performance of Our Protocol.

Average packet delivery ratio (PDR) is shown in Figure 7 where our proposed cross-layer design outperforms the other protocols, which confirms the previous result. We obtain this result due to the use of the two-level scheduling that prevents collisions and minimizes interference, besides the selection of paths with better link quality based on the received signal strength (along with SNR and BER). Also, the use of the fast mechanism of local repair through the acknowledgment system minimizes the effects of any node failure or link break and hence decreases the number of lost packets.

Figure 7

PDR of our protocol compared with other protocols.

With respect to the average energy consumption, our proposed design has less energy consumption than the other protocols as shown in Figure 8 with different node numbers. Both CMRP-only and CMRP+2_level scheduling protocols have good energy efficiency at low node density because of the many benefits that they get from the clustered network architecture. First, they have less communication overhead as most of the nodes in the network are group members and need only to communicate directly with their cluster heads regardless of the number of nodes in the cluster. Also, minimum number of packet forwarding from a source to the sink is needed as the paths found by CMRP routing protocol are optimized in terms of number of hops along with preventing path loops and path cycles. In addition, the aggregation process and data fusion done at cluster heads level reduce the size of correlated data within a cluster and thus decrease the needed amount of energy consumption to deliver them. However, at higher node densities, we notice that CMRP-only suffers from packet collisions and interferences and consumes more energy for retransmitting lost packets, while our cross-layer design exploits the benefits from the adaptive two-level scheduling to prevent such problem and hence has less energy consumption.

Figure 8

Energy consumption of our protocol and other protocols.

7. Conclusions

In this paper, we presented a cross-layer communication architecture for WMSNs between the routing and MAC layers, where a cluster-based multipath routing protocol has been pursued in conjunction with an adaptive QoS-aware scheduling. Our design aims to exploit correlation characteristics and functionalities between the two layers to maximize the overall network performance with minimum energy consumption in order to handle the additional requirements of delivering reliable multimedia data. Our proposed routing protocol provides load balancing by establishing multiple paths based on the hop count and received signal strength as an indication of the link quality, delay, and distance between the nodes. Our proposed scheduling protocol is based on TDMA approach with flexible time slot assignment that adaptively assigns slots to various traffics from active nodes. It maintains minimum end-to-end delay suitable for different traffic classes to meet their playout deadline and achieves high throughput and packet delivery ratio by selecting the paths with better link quality and avoiding collisions and interferences. The simulation results demonstrate that our cross-layer design can achieve better performance than the preexisting ones (CMRP only, DHCT, and MCRA) in terms of average end-to-end delay, throughput, packet delivery ratio, and battery power consumption. In future work, we will focus on optimizing the threshold values based on network configuration both in mathematical representation and in simulation. This will result in better cluster distribution and network connectivity. Also, studying in more details the effect of the communication overhead and synchronization problem in our scheduling protocol is planned.