Graph coloring based channel assignment framework for rural wireless mesh networks

IEEE 802.11 based wireless mesh networks with directional antennas are expected to be a new promising technology and an economic approach for providing wireless broadband services in rural areas. In this paper, we discuss interference models and address how they can affect the design of channel assignment in rural mesh networks. We present a new channel assignment framework based on graph coloring for rural wireless mesh networks. The goal of the framework is to allow synchronously transmitting or receiving data from multiple neighbor links at the same time, and continuously doing full-duplex data transfer on every link, creating an efficient rural mesh network without interference. Channel assignment is shown to be NP-hard. We frame this channel allocation problem in terms of Adjacent Vertex Distinguishing Edge Coloring （AVDEC）. Detailed assignment results on grid topology are presented and discussed. Furthermore, we design an algorithm. Finally, we evaluate the perform- ance of the proposed algorithm through extensive simulations and show the algorithm is effective to the regular grid topologies, and the number of colors used by the algorithm is upper bounded by A ~ 1. Hence the algorithm guarantees that the number of channels available in standards such as IEEE 802.11a is sufficient to have a valid AVDEC for many grid topologies. We also evaluate the proposed algorithm for arbitrary graphs. The algorithm provides a lower upper bound on the minimum number of channels to the AVDEC index channel assignment problem.     

Minimum latency joint scheduling and routing in wireless sensor networks

Wireless sensor networks are expected to be used in a wide range of applications from environment monitoring to event detection. The key challenge is to provide energy efficient communication; however, latency remains an important concern for many applications that require fast response. In this paper, we address the important problem of minimizing average communication latency for the active flows while providing energy-efficiency in wireless sensor networks. As the flows in some wireless sensor network can be long-lived and predictable, it is possible to design schedules for sensor nodes so that nodes can wake up only when it is necessary and asleep during other times. Clearly, the routing layer decision is closely coupled to the wakeup/sleep schedule of the sensor nodes. We formulate a joint scheduling and routing problem with the objective of finding the schedules and routes for current active flows with minimum average latency. By constructing a novel delay graph, the problem can be solved optimally by employing the M node-disjoint paths algorithm under FDMA channel model. We further present extensions of the algorithm to handle dynamic traffic changes and topology changes in wireless sensor networks.     

TDMA scheduling algorithms for wireless sensor networks

Algorithms for scheduling TDMA transmissions in multi-hop networks usually determine the smallest length conflict-free assignment of slots in which each link or node is activated at least once. This is based on the assumption that there are many independent point-to-point flows in the network. In sensor networks however often data are transferred from the sensor nodes to a few central data collectors. The scheduling problem is therefore to determine the smallest length conflict-free assignment of slots during which the packets generated at each node reach their destination. The conflicting node transmissions are determined based on an interference graph, which may be different from connectivity graph due to the broadcast nature of wireless transmissions. We show that this problem is NP-complete. We first propose two centralized heuristic algorithms: one based on direct scheduling of the nodes or node-based scheduling, which is adapted from classical multi-hop scheduling algorithms for general ad hoc networks, and the other based on scheduling the levels in the routing tree before scheduling the nodes or level-based scheduling, which is a novel scheduling algorithm for many-to-one communication in sensor networks. The performance of these algorithms depends on the distribution of the nodes across the levels. We then propose a distributed algorithm based on the distributed coloring of the nodes, that increases the delay by a factor of 10–70 over centralized algorithms for 1000 nodes. We also obtain upper bound for these schedules as a function of the total number of packets generated in the network.     

MR-MC无线传感器网络最小延迟数据聚集调度研究

单radio单信道无线传感器网络的最小延迟聚集调度是一个NPC问题,已提出许多解决方案。在多radio多信道网络中,节点可以同时接收多个不同节点传输的数据,降低延迟。基于上述特点,考虑树结构约束,时槽、信道和radio分配等约束条件,将多radio多信道无线传感器网络最小延迟聚集调度问题定义为一个优化问题,并分解为建立聚集树和节点调度2个子问题,针对这2个子问题分别提出启发式算法。实验结果表明,提出的算法具有良好的性能。     

CBLA:多信道无线网状网络负载感知的分簇式信道分配

多信道技术能够显著提升无线网状网络的容量,合理高效的信道分配方案是多信道网状网络的核心问题。本文提出了一种分布式的信道分配方法CBLA（Cluster-Based Load-Aware）,结合了静态信道分配简单和动态信道分配灵活的特点;借助簇结构降低了问题的规模;根据统计开销小的局部信息监测链路负载;自适应的动态分配有效减轻了链路负载;采用了一种新的结合跳步数、信道分布情况和簇信息的选路指标。实验结果表明CBLA有效降低了数据包的平均延迟,并显著提升了网络吞吐量。     

Joint Channel Assignment and Routing for Throughput Optimization in Multiradio Wireless Mesh Networks

Multihop infrastructure wireless mesh networks offer increased reliability, coverage, and reduced equipment costs over their single-hop counterpart, wireless local area networks. Equipping wireless routers with multiple radios further improves the capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing is essential for throughput optimization of mesh clients. Efficient channel assignment schemes can greatly relieve the interference effect of close-by transmissions; effective routing schemes can alleviate potential congestion on any gateways to the Internet, thereby improving per-client throughput. Unlike previous heuristic approaches, we mathematically formulate the joint channel assignment and routing problem, taking into account the interference constraints, the number of channels in the network, and the number of radios available at each mesh router. We then use this formulation to develop a solution for our problem that optimizes the overall network throughput subject to fairness constraints on allocation of scarce wireless capacity among mobile clients. We show that the performance of our algorithms is within a constant factor of that of any optimal algorithm for the joint channel assignment and routing problem. Our evaluation demonstrates that our algorithm can effectively exploit the increased number of channels and radios, and it performs much better than the theoretical worst case bounds     

无线mesh网络中的信道分配问题研究

在多接口无线mesh网络中使用多信道可以减少碰撞和干扰,提高系统吞吐量。因此,合理的信道分配是无线mesh网络中多信道技术的关键。用图论理论建立信道分配数学模型以及用图着色理论研究信道分配问题是无线网络中解决信道分配问题的有效方法。因此针对无线mesh网络中多接口多信道(multi-radio and multi-channel)的特点,重点介绍了无线mesh网络中信道分配的基本理论、主要约束和图论模型等,最后提出应用图着色理论解决信道分配问题的一般途径。     

Channel assignment for cellular radio using extended dynamic programming

The channel assignment is an important aspect of cellular radio networks. Because of the limitations on the frequency spectrum, the optimal or near-optimal channel assignment has become an essential part of the network operations of wireless personal communication systems. We formulate a new strategy for the channel assignment problem in agreement with the electromagnetic compatibility constraints. We introduce and formulate the extended dynamic programming (EDP), as an extension of dynamic programming for solving the channel assignment problem in a cellular system. Using EDP an algorithm is developed for fixed channel assignment problem and it is tested and compared with other existing methods by solving different problems. In agreement with electromagnetic compatibility constraints, solution strategy based on EDP algorithm finds many valid solutions with minimum possible bandwidth.     

Tree‐based channel assignment schemes for multi‐channel wireless sensor networks

Many sensor node platforms used for establishing wireless sensor networks (WSNs) can support multiple radio channels for wireless communication. Therefore, rather than using a single radio channel for whole network, multiple channels can be utilized in a sensor network simultaneously to decrease overall network interference, which may help increase the aggregate network throughput and decrease packet collisions and delays. This method, however, requires appropriate schemes to be used for assigning channels to nodes for multi‐channel communication in the network. Because data generated by sensor nodes are usually delivered to the sink node using routing trees, a tree‐based channel assignment scheme is a natural approach for assigning channels in a WSN. We present two fast tree‐based channel assignment schemes (called bottom up channel assignment and neighbor count‐based channel assignment) for multi‐channel WSNs. We also propose a new interference metric that is used by our algorithms in making decisions. We validated and evaluated our proposed schemes via extensive simulation experiments. Our simulation results show that our algorithms can decrease interference in a network, thereby increasing performance, and that our algorithms are good alternatives for static channel assignment in WSNs. Copyright © 2015 John Wiley & Sons, Ltd.     

DRAND: Distributed Randomized TDMA Scheduling for Wireless Ad Hoc Networks

This paper presents a distributed implementation of RAND, a randomized time slot scheduling algorithm, called DRAND. DRAND runs in O(delta ) time and message complexity where delta is the maximum size of a two-hop neighborhood in a wireless network while message complexity remains O(delta ), assuming that message delays can be bounded by an unknown constant. DRAND is the first fully distributed version of RAND. The algorithm is suitable for a wireless network where most nodes do not move, such as wireless mesh networks and wireless sensor networks. We implement the algorithm in TinyOS and demonstrate its performance in a real testbed of Mica2 nodes. The algorithm does not require any time synchronization and is shown to be effective in adapting to local topology changes without incurring global overhead in the scheduling. Because of these features, it can also be used even for other scheduling problems such as frequency or code scheduling (for FDMA or CDMA) or local identifier assignment for wireless networks where time synchronization is not enforced. We further evaluate the effect of the time-varying nature of wireless links on the conflict-free property of DRAND-assigned time slots. This experiment is conducted on a 55-node testbed consisting of the more recent MicaZ sensor nodes.