Abstract :
Concurrent transmissions at different links can interfere with each other in single channel wireless networks. A scheduling algorithm is needed to select a subset of links for data transmission to improve system performance. Optimal connection scheduling discipline throughput is usually an NP-hard issue. We use the concept of line graph in this paper and extend it to line multi graph to deal with the complexity issue of the algorithm of maximum weight scheduling (MWS). The required and sufficient conditions are derived in terms of network topology to reduce the complexity of MWS. We prove that eLehot's complexity is polynomial time as long as there are no seven derived prohibited graphs as induced sub graphs in the conflict graph. We also propose an eLehot algorithm to detect if a graph is a line multigraph and to output its root graph. The findings of this paper introduce a new approach to regulation of wireless topology where the aim is to reduce complexity.
Keyword :
Wireless network scheduling; line graph; line multigraph; root graph; dispute graph; topology command.