Institute for Systems Research Technical Reports

When TDMA is used, distributed protocols are needed to generate transmission schedules. An important issue is how to produce a schedule quickly. This is critical when the network is large or the network changes frequently. Here we develop two fully distributed protocols for generating or updating TDMA schedules. Contention is incorporated into the scheduling protocols for them to work independently of the network size. The schedule can be generated at multiple parts of the network simultaneously. In the Five-Phase Reservation Protocol (FPRP), a broadcast schedule is produced when nodes contend among themselves using a new five-phase message exchange mechanism. In the Evolutionary-TDMA scheduling protocol (E-TDMA), schedules are updated when nodes contend to reserve transmission slots of different types (unicast, multicast, broadcast). Both are scalable protocols suitable for large or dynamic networks.

Another issue related to medium access control is transmission power control. Our contribution to power control is to develop a channel probing scheme for networks applying power control, which allows a node to probe a channel and estimate the channel condition. It can be used for dynamic channel allocation in a TDMA or FDMA system, or admission control in a DS/CDMA system. It is a fully distributed scheme which requires little communication overhead. Multiple links can probe a channel simultaneously and each makes individual yet correct decisions.

The last topic is Quality-of-Service routing. An efficient distributed scheme is developed to calculate the end-to-end bandwidth of a route. By incorporating this scheme with the AODV protocol, we developed an on-demand QoS routing protocol which can support CBR sessions by establishing QoS routes with reserved bandwidth. It repairs a route when it breaks.Load balancing and route redundancy are also achieved. It is applicable for small networks or short routes under relatively low mobility.

When TDMA is used, distributed protocols are needed to generate transmission schedules. An important issue is how to produce a schedule quickly. This is critical when the network is large or the network changes frequently. Here we develop two fully distributed protocols for generating or updating TDMA schedules. Contention is incorporated into the scheduling protocols for them to work independently of the network size. The schedule can be generated at multiple parts of the network simultaneously. In the Five-Phase Reservation Protocol (FPRP), a broadcast schedule is produced when nodes contend among themselves using a new five-phase message exchange mechanism. In the Evolutionary-TDMA scheduling protocol (E-TDMA), schedules are updated when nodes contend to reserve transmission slots of different types (unicast, multicast, broadcast). Both are scalable protocols suitable for large or dynamic networks.

Another issue related to medium access control is transmission power control. Our contribution to power control is to develop a channel probing scheme for networks applying power control, which allows a node to probe a channel and estimate the channel condition. It can be used for dynamic channel allocation in a TDMA or FDMA system, or admission control in a DS/CDMA system. It is a fully distributed scheme which requires little communication overhead. Multiple links can probe a channel simultaneously and each makes individual yet correct decisions.

The last topic is Quality-of-Service routing. An efficient distributed scheme is developed to calculate the end-to-end bandwidth of a route. By incorporating this scheme with the AODV protocol, we developed an on-demand QoS routing protocol which can support CBR sessions by establishing QoS routes with reserved bandwidth. It repairs a route when it breaks.Load balancing and route redundancy are also achieved. It is applicable for small networks or short routes under relatively low mobility.

Certain constraints of TDMA transmission in a wireless network requirescareful scheduling among the nodes in order to achieve conflict-free operations. These constraints also make the calculation of the end-to-end bandwidth along a path non-trivial. These calculationsare essential for QoS routing which requires a certain amount of bandwidth available on a route.

We prove the problem of calculating the maximal end-to-end bandwidth along a given a path in a TDMA network is NP-complete, and develop an efficient bandwidth calculation scheme. We also show how the bandwidth calculation scheme can be usedwith the Ad-hoc On-demand Distance Vector protocol (AODV) to perform QoSrouting.