Transmission Scheduling in Packet Radio Networks using Graph Coloring Algorithm

Author

Walczak, Zbigniew ; Wojciechowski, Jacek M.

Author_Institution

Warsaw Univ. of Technol., Warsaw

fYear

2006

fDate

29-31 July 2006

Firstpage

46

Lastpage

46

Abstract

The paper deals with a conflict-free scheduling in multihop packet radio networks. A method for establishing communication channels between the given set of pairs of nodes is proposed. The delays for all channels are constant and requested network resources minimized. For each channel a virtual path is determined and optimal scheduling found using DSATUR graph coloring algorithm. The paper combines the MAC and routing layer in a single algorithm. Such an approach applied to wireless networks, leads to communication time shorter than the one described in the literature.

Keywords

access protocols; graph colouring; packet radio networks; routing protocols; scheduling; telecommunication channels; DSATUR graph coloring algorithm; MAC layer; communication channels; conflict-free scheduling; multihop packet radio networks; routing layer; transmission scheduling; virtual path; Broadcasting; Communication channels; Frequency; Optimal scheduling; Packet radio networks; Paper technology; Routing; Scheduling algorithm; Time division multiple access; Wireless networks;

fLanguage

English

Publisher

ieee

Conference_Titel

Wireless and Mobile Communications, 2006. ICWMC '06. International Conference on

Conference_Location

Bucharest

Print_ISBN

0-7695-2629-2

Electronic_ISBN

0-7695-2629-2

Type

conf

DOI

10.1109/ICWMC.2006.91

Filename

4124195