## 4 Cluster-Based Multipath Routing in WMSN
### Two-Level QoS-Aware Scheduling  
After establishing the network, all group members (sensor nodes) in each cluster are assigned to a cluster head and each cluster head in the network knows now its parents toward the BS (for multiple paths). Before data transmission, we introduce two-level QoS-aware scheduling: low-level scheduling within the cluster among the group members, and scheduling among the cluster heads at higher level in order to increase the packet delivery ratio and throughput for multimedia data. The two-level scheduling is shown in a simple example in Figure 5. 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 under-utilization 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, before GMs start sending their different types of data to their CHs, 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 at receiver side. The low-level scheduling process is initiated by the CH by sending a broadcast message asking each GM in the cluster to send a request message (Req-Msg) informing about  
Figure 4: Examples of Path loop and Path Cycle. 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, based on TDMA (_i.e._, time slot to each node), to each GM in the cluster to send its Req-Msg. The duration of the time slot is enough to any node in the cluster to send its Req-Msg and the time slot is unique for each node 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, called 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 transmission 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 complete, a CH sends again the Assign-Msg to its GMs to send their requests. A cluster time-intervals is in Figure 6 illustrating the scheduling operation. Figure 5: A Simple Example of Two-level Scheduling. 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. For example, as shown in Figure 5, CH1 selects the path through CH4 to send its streaming multimedia data and the path through CH3 to send the other types of data based on the proposed routing algorithm, while CH2 sends all its data to CH3.