Discrete-Event-Dynamic-System-Based Approaches for Scheduling Transmissions in Multihop Packet Radio Networks
Annual rept. Oct 1991-Sep 1992
MASSACHUSETTS UNIV AMHERST DEPT OF ELECTRICAL AND COMPUTER ENGINEERING
Pagination or Media Count:
In the classic transmission scheduling problem, the nodes of a Packed Radio Network PRN broadcast fixed-length packets over a common resource the channel. Packet transmissions are subject to interference constraints for example, if a node is transmitting a packet, then all adjacent neighboring nodes must refrain from transmission. One then adopts a slotted time model where every slot is allocated to a set of nodes which can simultaneously transmit without conflict. Thus, a node is generally belongs to one or more of these setscalled transmission sets. Our approach is based on viewing the transmission scheduling problem as a single server multiclass polling problem with simultaneous resource possession. Here, a class corresponds to a transmission set. The server corresponds to a channel operating with deterministic service times a service time is equal to one time slot required for transmitting a packet. The scheduling problem is then equivalent to assigning the server equivalently, each time slot to a particular transmissions set. The simultaneous resource possession feature arises because the server is assigned to a transmission set, i.e. it can simultaneously provide service to packets from all nodes which belong to that set. The construction of the transmission set is dependent upon the topology and connectivity of the PRN and is equivalent to a graph partitioning problem. For our purposes, we assume M transmission sets have been specified. Finally, we allow for overlapping transmission sets, i.e. a node can belong to two or more difference transmission sets.
- Radio Communications