Discrete-Event-Dynamic-System-Based Approaches for Scheduling Transmissions inMultihop Packet Radio Networks

摘要

In the classic transmission scheduling problem, the nodes of a Packed RadioNetwork (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 generally belongs to one or more of these sets(called 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.