Scheduling links for heavy traffic on interfering routes in wireless mesh networks

作     者：Vieira, Fabio R. J. de Rezende, Jose F. Barbosa, Valmir C. Fdida, Serge 

作者机构：Univ Fed Rio de Janeiro Programa Engn Sistemas & Comp COPPE BR-21941972 Rio De Janeiro RJ Brazil Lab Informat Paris 6 F-75252 Paris 05 France Univ Fed Rio de Janeiro Programa Engn Eletr COPPE BR-21941972 Rio De Janeiro RJ Brazil 

出 版 物：《COMPUTER NETWORKS》 (计算机网络)

年 卷 期：2012年第56卷第5期

页      面：1584-1598页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：CNPq CAPES FAPERJ BBP Universite Pierre et Marie Curie CNRS RENATER 

主　　题：Wireless mesh networks Link scheduling Node multicolorings Scheduling by edge reversal 

摘      要：We consider wireless mesh networks and the problem of scheduling the links of a given set of routes under the assumption of a heavy-traffic pattern. We assume some TDMA protocol provides a background of synchronized time slots and seek to schedule the routes links to maximize the number of packets that get delivered to their destinations per time slot. Our approach is to construct an undirected graph G and to heuristically obtain node multicolorings for G that can be turned into efficient link schedules. In G each node represents a link to be scheduled and the edges are set up to represent every possible interference for any given set of interference assumptions. We present two multicoloring-based heuristics and study their performance through extensive simulations. One of the two heuristics is based on relaxing the notion of a node multicoloring by dynamically exploiting the availability of communication opportunities that would otherwise be wasted. We have found that, as a consequence, its performance is significantly superior to the other s. (C) 2012 Elsevier B.V. All rights reserved.