Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks
Novel scheduling algorithms for concurrent transmit/receive wireless mesh networks
复制标题
DOI：
10.1016/j.comnet.2011.12.001
复制
发表时间：
2012-03
期刊：
影响因子：
--
通讯作者：
Kwan-Wu Chin;S. Soh;Chen Meng
中科院分区：
文献类型：
--
作者：
Kwan-Wu Chin;S. Soh;Chen Meng
最近，为了增加无线网状网络（WMN）的容量，研究人员已经开始为路由器配备多个接口/无线电，并将每个接口/无线电连接到定向或智能天线。这些路由器的一个关键特性是它们能够同时从多个邻居发送或接收。因此，它们具有比全方位对应物高几个数量级的容量。然而，这种显著的容量增加是基于在任何给定时间点最大化活动链路数量的链路调度算法。本文提出了一些链接激活算法，从一般的拓扑结构中获得最大二部图。这些算法在计算时间和最优性方面提供了不同的权衡。一个关键的亮点是一个贪婪算法，其时间复杂度为O（V），其中V是路由器的集合。除此之外，我们概述了两个算法，使用近似的众所周知的最大切割问题，也是一个蛮力算法，这是能够得出一个最佳的链路激活时间表。从我们的算法的输出，然后可以使用的空间时分多址（TDMA）介质访问控制（MAC）协议调度并发发送和接收链路。我们已经验证了我们的算法在不同的拓扑结构，增加节点度以及节点数。从大量的仿真研究中，我们发现，我们的算法有良好的性能方面的链接激活的数量，长度，和端到端的数据包延迟。
Recently, in an effort to increase the capacity of Wireless Mesh Networks (WMNs), researchers have begun equipping routers with multiple interfaces/radios, and connecting each one to a directional or smart antenna. A key feature of these routers is their ability to transmit or receive from multiple neighbors simultaneously. Hence, they have orders of magnitude higher capacity than their omni-directional counterparts. This significant capacity increase, however, is predicated upon a link scheduling algorithm that maximizes the number of active links at any given point in time. This paper proposes a number of link activation algorithms that derive maximal bipartite graphs from general topologies. These algorithms provide different trade-offs in terms of computation time and optimality. A key highlight is a greedy algorithm that has a time complexity of O(∣V∣2), where V is the set of routers. Apart from that, we outline two algorithms that use an approximation to the well known maximum cut problem, and also a brute force algorithm, which is capable of deriving an optimal link activation schedule. The output from our algorithms can then be used by a spatial Time Division Multiple Access (TDMA) Medium Access Control (MAC) protocol to schedule concurrent transmitting and receiving links. We have verified our algorithms on various topologies with increasing node degrees as well as node numbers. From extensive simulation studies, we find that our algorithms have good performance in terms of number of links activated, superframe length, and end-to-end packet delay.