Article Preview
Top1. Introduction
We have witnessed the rapid growth of wireless access networks during the recent years. It has been driven by the increasing numbers of smartphone and Wireless Sensor Networks (WSNs) applications (Brar, 2001). The debate between two types of access methods, one using centralized control method and the other using a distributed approach, remains largely unsettled as new evidences arrives from both sides.
Broadband wireless access networks have historically favoured centralized access methods due to the method’s ability to provide guaranteed Quality of Service (QoS). However, hybrid access schemes are commonly used in the third/fourth generation systems, which allow the access providers to support a seamless integration of different types of data services.
For both broadband access network and wireless sensor networks, a fundamental challenge is to mitigate the co-channel interference, which is the limiting cause to the throughput of the networks beyond certain scale. To increase the system capacity, multiple frequency channels/carriers are often deployed to achieve maximum signal isolation in space, time and frequency domains (Jordan, 1996). In such a network, wireless devices could transmit at different frequency channels based on specific channel allocation strategy. Channel access control is particularly important in the third- and fourth-generation broadband networks, due to the aggressive physical layer techniques such as OFDM modulation technique. Although not mandatory in the 4G technical specification, dynamic channel allocation is one of the key mechanisms to maximize the spectrum efficiency and achieve high bandwidth. Such is our motivation to study a novel distributed channel allocation method from the perspective of minimizing interference violation.
On the other side, most infrastructure-less wireless networks (such as conventional 802.11 networks and WSNs) use a shared-channel model within the cell boundary. Channel arbitration falls to the users in a distributed manner. Such assumption should attribute partially to the physical complexity of multi-channel transceiver, but more on the fact that channel allocation problem is NP-hard by nature (Krumke, 2000) especially the distributed ones.
Figure 1 shows a graphic representation of a conventional channel allocation model in a multi-cell configuration, subject to the different interference rules. For illustration, a cell is represented by a vertex, and the network has a regular hexagon structure. On the left side, the interference range is defined as one hop of a uniform radius, which results in a 6-node neighborhood for all nodes. On the right-hand graph, the interference range is two hop of a uniform radius, and the neighborhood from any node now contains 19 nodes. For a collision-free channel allocation, the former case will require 7 channels and the later need 19 channels. One centralized algorithm to do this involves fan-rotation (Misra, 1992) and cd-path inverting.
Figure 1. Cells in a regular hexagon topology (a) interference radius = one hop, requires 7 channels for collision free allocation. (b) interference radius= two hops requires 19 channels