In Both multi-interface and dynamicchannel adjustment are prevailingly used to improve thecapacity and the flexibility of wireless mesh networks(WMNs). The System over heads that are generated by uncontrolled interface switching adversely decrease the performance of WMNs. To find a reasonable tradeoff between flexibility and switching overheads, we propose ahybrid channelassignment protocol (HCAP) for multiinterface WMNs. The HCAP adopts a static interfaceassignment strategy for nodes that have the heaviest loads to avoid frequent interface switching, whereas it adopts a hybrid interfaceassignment strategy for other nodes to improve the ability of adapting to flow change. In our implementation, we present a slotbased coordination policy. Extensive NS2 simulations demonstrate that the HCAP improves network capacity, enhances flexibility, and guarantees interflow fairness.
Keywords |
Channel assignment, coordination, interface switching, multiple interfaces, wireless mesh network (WMN). |
INTRODUCTION |
In deployment of wireless mesh networks (WMNs) has quickly increased recently due to their significant advantages over
other wireless networks. A typical WMN application consists of three levels: wired networks, the WMN backbone, and
mesh clients. Wired networks contain most resources in WMNs, such as file servers, file transfer protocol servers, etc. The
WMN backbone is a collection of static wireless mesh routers. Traffic loads between the wired network and mobile users in
mesh clients are transmitted by the WMN backbone in a multihop manner. Mesh clients can connect to the WMN backbone
by establishing either wired or wireless links with mesh routers. Most wireless networks, such as wireless local area
networks, wireless metropolitan area net-works, wireless wide area networks, wireless sensor networks, wireless personal
area networks, and cellular networks, can act as mesh clients. One example of WMN architecture is shown in Fig. 1, where
solid and dashed lines indicate wired and wireless Link respectively an rapid transmission of the data in network Through
multihop transmissions, mobile terminals in mesh clients can easily access the resources that reside in the wired networks.
Traffic loads in WMNs are usually aggregated from different systems, which require WMNs to provide high capacity and
flexibility. On the other hand, aggregated traffic loads aggravate the problem of interference in WMNs, which adversely
decreases the network throughput. Dynamic channel adjustment and equipping each mesh router with multiple interfaces
are prevailingly performed to improve the capacity and the flexibility of WMNs. Advantages of both multiple interfaces
and dynamic interface (DI) switching have been long acknowledged. However, uncontrolled interface switching may
induce two kinds of dependence problems. It induces connection dependence if a node
cannot communicate with another node within its transmission range since they switch to different channels. Also, it is
channeldependent when changing the channel of a particular link results in a series of changing channels of other links.
Furthermore, frequent interface switching may result in the problem of broadcasting due to absence of permanent
communication links. Moreover, interface switching also brings additional delay, which may impact the decision of other
protocols or applications. |
We put forward a channelassignment protocol, which is denoted as the hybrid channelassignment protocol (HCAP), for
multi-interface WMNs. On considering the impacts of frequent interface switching, the proposed protocol adopts a static
interface assignment for nodes that have the heaviest loads, whereas it adopts a hybrid channel assignment for other nodes
to quickly adapt to traffic flow change. Our aim is to find a reasonable The tradeoff between flexibility and switching
overheads in improving the network capacity by adopting interface switching. The performance of a channel assignment
protocol in multichannel multiinterface wireless networks can be characterized by both the data rate and delay transmitted
to the gateway nodes (GNs). We then theoretically analyze the performance of the proposed protocol using a simple model
and evaluate the performance of the proposed protocol by simulations. |
• We propose a novel channelassignment protocol for multi-interface WMNs. The proposed protocol does not need
prior knowledge of loads. Nevertheless, it can automatically adapt to load change. |
Wireless Mesh Routers are classified intothree types According to their positions. Gateway (GA):Mesh Routers that
Connect to wired Networks viaWired links. Super Node (SN): Mesh Routers that arewithin the Transmission angeof GAs.
General Node(GN): Mesh Routers that are Beyond theTransmission Range of GAs. |
• The proposed protocol adopts such interface assignment strategies that combine advantages of both static and
hybrid interface assignment strategies to find a feasible tradeoff between flexibility and switching overheads. |
• The proposed protocol takes a slot based coordina tion strategy, which does not need additional broadcast
interfaces channels. Results show that it keeps both interface switching overheads and coordination complexity
under a tolerable range. |
RELATED WORKS |
Many studies have been done on multiinterface wireless networks . Since uncontrolled channel switching may
induce challenging problems, researchers have to balance the tradeoff between flexibility and feasibility in utilizing the
interface switching strategy. Generally, there are two kinds of
typical approaches. |
A. Periodic Channel Reassignment |
All interfaces of each node ad- just channels every after a relatively long time period, such as several hours or
days. During the period, no interface can switch channels. |
In both communication links and traffic loads on wireless mesh nodes are known. During the channelassignment procedure, it first queues the links
according to their traffic information and then assigns
channels for links in the decreasing order of their loads. |
The channelassignment procedure is executed every several hours/days. several links may share one interface due
to the very limited number of interfaces that are equipped on nodes. However, this strategy does not avoid the
channeldependence problem. Assume that the routing path between each node and the GN is established. To resolve
channel dependence, the algorithm classifies the two wireless interfaces that are equipped on each wireless mesh node
(except the gateways) into two types: One is used to communicate with its parent node, and the other is used to
communicate with its children nodes. Both interfaces are used to communicate with their children nodes since they are the
roots of every routing path. Starting from the GA, every node just decides the channel of the interface that is used to
communicate with its children nodes. Apparently, the channel of the other interface is decided by its parent node according
to this algorithm. |
B. Hybrid Channel Assignment |
Only several interfaces of a wireless node can dynamically change channels after the channel assignment. These interfaces
switch their channels on a per-packet or several-packets basis. |
The proposed protocol called dynamic channel
assignment (DCA) that assigns channels dynamically in an on demand style. The overall bandwidth is divided into one
control channel and n data channels according to DCA. DCA assumes that every node is equipped with two wireless
interfaces: One is used to transfer control packets, and the other is used to transfer data packets only. The former fixes on
the control channel to negotiate the channel that is used to transfer data packets, and the latter sends/receives data packets
on the negotiated channel. |
The interface is of two types: the receiving interfaces and the sending interfaces. Each receiving interface fixes on a unique
channel, respectively, whereas the sending interface can dynamically switch channels. Unlike there is no common link
between nodes by default. A sender first switches one of its sending interfaces to the receiving channel of the receiver
before communication. |
PRELIMINA RIES AND ASSUMPTIONS |
A. System Model |
We consider a WMN that consists of M gateways and N other mesh nodes [i.e., SNs and GNs]. In most scenarios, the ratio
between M and N is much less than 1 since there are usually a few GA nodes. We then assume that M/N is small enough
that any two GA nodes do not interfere with each other, even if they are assigned with a common channel. We assume that
each node is equipped with two interfaces. |
As most traffic loads in WMNs are to and from wired net- works and mesh clients, we omit the traffic flows between mesh
clients in the following discussions. Under this assumption, each mesh node should establish at least one routing path to
GAs to access the resources that reside on the wired networks. For simplicity, we assume that a node can only establish
one routing path to one of the GAs at a time. |
Traffic loads on nodes in the WMN backbone are unbal anced. The outside mesh nodes just relay traffic
loads for mesh clients within their respective coverage range, whereas middle mesh routers should also relay traffic loads
for other nodes. It is obvious that the aggregated loads on GAs are the heaviest in the WMN since all packets that are
destined to and from the wired network would reach GAs. Starting from GAs, loads on the mesh nodes drop dramatically.
The farther the distance between a node and the GA, the lighter the aggregated loads. |
B. Interface Switching Mode and Time Synchronization |
For ease of description, we denote the interfaces that can dynamically switch channels after channel assignment by DIs, and
we denote the interfaces that cannot switch channels after channel assignment by fixed interfaces (FIs). The schedule time
of DIs is divided into small time slices, which define the minimum time duration that one DI spends on a channel before it
switches to another one. The time that it takes to switch channels is negligible compared with the length of each time slice.
We introduce a notion, i.e., slot, to denote the time slice. We use a cycle to denote the maximum number of
communications that the scheduler can schedule at a time. We define the size of a cycle, i.e., S, as the number of slots that
are included in a cycle. The size of a cycle should satisfy that a hybrid node communicates at least once with every hybrid
node within its transmission range in a cycle. The structure of a cycle is shown in Fig. 2. |
Wireless nodes cannot communicate with each other if they fix on different channels due to the characteristic of the
wireless medium. Thus, a pair of communication nodes should switch to a channel at the same time before the
communication. Thus, time synchronization is needed to ensure that nodes switch channels on time. Data transmissions
between nodes that adopt hybrid channel assignment in our proposed protocol do require local synchronization since there
is no common channel be- tween them on default. Nevertheless, our protocol does not re- quire strict synchronization. Here,
we assume that the proposed protocol adopts one of the current synchronization schemes. The initial synchronization
information is embedded into the control packet when two nodes coordinate the time when they communicate with each
other. |
C. Hybrid Channel-assignment Protocol |
Here, we illustrate the proposed channel assignment protocol in detail. We first describe its interface assignment strategies
and then present the channel assignment procedure and cor- responding algorithms. Finally, we provide the coordination
strategies. |
Fig. 3 gives an overview of the interface assignment results according to the HCAP using a seven node network, where a
wireless interface is denoted by one rectangle in Fig. 3(b). The upper rectangle of one SN node denotes its FI, whereas the
lower one represents its DI. The number in the rectangle is its assigned channel. |
Lines without arrows denote links between the GA and SN nodes, whereas arrow lines represent links between hybrid
nodes. Every arrow line starts from the DI of a sender and points to IRec of a receiver. The number besides a link represents
its channel. We can see that the channel used by the link between two hybrid nodes is decided by the receiver. For example,
link CD takes channel 4, whereas link DC takes channel 3. |
In this example, two hybrid nodes may concurrently establish two links. On considering that both interfaces and channels
are precious resources in wireless networks, we adopt the following strategy for hybrid nodes to establish communication
links. When a hybrid node wants to communicate with another hybrid node within its transmission range, it prefers to use
the established link. Two hybrid nodes can establish a new dynamic link only if there is no link established between them at
that time. This strategy not only assures that two hybrid nodes can only use one link to communicate with each other at a
time but also decreases the frequency of interface switching on hybrid nodes. |
D. Channel-Assignment Procedure and Algorithms |
As traffic loads on GA nodes are the heaviest of the network, GA nodes deserve the highest priority. Hence, both interfaces
of GA nodes are assigned with channels during the first phase. The FI of the SN node is used to communicate with GA
nodes. It is natural to assign channels to the FI of SN nodes in the second phase. Finally, the algorithm assigns CRec to
hybrid nodes. |
Interference estimation is a critical issue of channel assignment. The algorithm takes a weighted interference estimation
scheme (WIES) which assigns a weight to each link to denote the interference degree of one node to the other node. We do
not present details of the WIES due to the limitation of space.Since the distance between GA nodes is big enough that they
do not interfere with each other, each GA node randomly selects its channels from the set of all channels. We then focus
our attention on the other two procedures, where the node that has the biggest η is given the highest priority in channel
assignment. η is defined as the number of a node’s interference nodes that have been assigned with channels at present. If
multiple hybrid nodes have the biggest η, they are assigned with channels in a random order. This searching sequence
satisfies our goal of giving higher priority for nodes that have more restrictions. |
We presented centralized algorithms to implement the channel assignment procedure. Before channel assignment, we first
divide all hybrid nodes into groups circled around GAs. One hybrid node can only belong to the group of a GA node. Each
GA node takes the charge of assigning channels to all nodes within its group. It should be noted that this division is only
used by the algorithm to decide which GA is used to assign channels for hybrid nodes. The channel assignment procedures
on all GA are the same. We take a GA, for example, to illustrate the channel assignment algorithm. |
Letβ denote the GA node and Cβ denote the set of
channels that are assigned to β. Let Ψ be the set of
SN nodes within the group of β. The pseudocode for
the GA node β assigning a channel to the FI of each
SN is presented in Algorithm .
Algorithm Assign channels to the FI of SN nodes |
1: while (Ψ = φ) do
|
2: for (i Ψ) do |
3: Compute η for i; |
4: Let Ψ = {γ|γ Ψ, and γ has the
maximum η}; |
5: for (α Ψ ) do |
6: for (c Cβ ) do |
7: Estimate the interference of c on node |
α using the WIES; |
8: Let γ Cβ be the channel with the minimum interference; |
9: Assign γ to the FI of node α; |
10: Delete node α from Ψ; |
The algorithm first computes η for every node in Ψ (lines 2 and 3) and then selects all nodes that have the
maximum η to the set of nodes Ψ (line 4). In lines 5–10, the algorithm selects the channel for the FI of every node α in Ψ .
We can see that the set of candidate channels for an SN node is initialized to the set of channels that are assigned to the GA
node β. The algorithm first computes the interference level of each candidate channel using the WIES (in lines 6 and 7).
Then, it selects the channel that has the minimum interference level for the FI of α (in lines 8 and 9). Finally, it deletes node
α from the set of Ψ (line 10). These operations repeat until Ψ is null. |
PERFORMANCE EVALUATION |
The performance of our proposed protocol was extensively evaluated through both theoretical analysis and simulations.
Here, we first describe main evaluateon metrics used in analysis and simulations. We then present several properties of the
pro- posed protocol and several theoretical analysis results. Finally, we validate the performance of the proposed protocol
through extensive NS2 simulations. |
A. NS2 Results and Analysis |
B. Simulation Settings |
We then choose them as comparison schemes. For ease of explanation, we refer to the two compared schemes as Periodic
and Hybrid in the following simulations. Although we have done a lot of simulations, we only present a set of typical
results due to space limitations. |
Consider a WMN with n wireless mesh routers and C gateways. Assume that the n mesh routers are randomly distributed in
a limited field. Nevertheless, the distance between two neighboring nodes is equal to the transmission range. Let r be the
ratio between the interference range and the transmission range. Suppose that each node is equipped with m wireless
interfaces. |
There are c channels, and the bandwidth of each channel is W Mb/s. Each router generates data at a fixed rate w Mb/s. Here,
we require the sink to receive data from all mesh routers (i.e., the traffic from all mesh routers needs to be delivered to the
GN). |
1) Network throughput |
We measured the impacts of the number of GAs and traffic loads on the network throughput. We first vary the number of
available GAs during simulations, whereas we keep the number of flows unchanged. Then, we vary the number of flows
that are loaded to the network and keep the number of GAs fixed. In these simulations, traffic flows are loaded to the
network by sequence, and all of them will last until the end of simulation. |
CONCLUSION AND FUTURE WORK |
We have designed and implemented HCAP, i.e., a hybrid channel-assignment protocol, for multi interface WMNs. The
proposed protocol does not require prior knowledge of loads and additional broadcast interfaces channels. Extensive NS2
simulations show that the proposed protocol improves the network capacity and flexibility and achieves better interflow
fairness.Nevertheless, the analysis and simulations have been executed in a relatively ideal environment. For example, we
assume that the internal traffic in WMNs can be omitted com- pared with the external traffic.Therefore, the performance of
the HCAP may decrease under such a scenario where inter- nal traffic flows cannot be neglected. We will further study and
analyze the issue of how to apply our method upon the dynamic channel assignment problem under a more complex
environment, where a large quota of traffic is the internal traffic between mesh clients. |
Figures at a glance |
![Click Here Figure](https://www.rroij.com/articles-images/IJAREEIE-338-g001.gif) |
![Click Here Figure](https://www.rroij.com/articles-images/IJAREEIE-338-g002.gif) |
![Click Here Figure](https://www.rroij.com/articles-images/IJAREEIE-338-g003.gif) |
Figure 1 |
Figure 2 |
Figure 3 |
|
|
References |
- F. Akyildiz, X. Wang, and W. Wang, âÃâ¬ÃÅWireless mesh networks: A survey,âÃâ¬Ã in Computer Networks and ISDNSystems. New York: Elsevier, 2005, pp. 445âÃâ¬Ãâ487.
- P. Kyasanur and N. H. Vaidya, âÃâ¬ÃÅCapacity of multi-channel wireless net- works: Impact of number of channels and interfaces,âÃâ¬Ã in Proc. MobiCom, 2005, pp. 43âÃâ¬Ãâ57.
- S. Merlin, N. Vaidya, and M. Zorzi, âÃâ¬ÃÅResource allocation in multi- radio multi-channel wireless network,âÃâ¬Ã in Proc. INFOCOM, 2008, pp. 1283âÃâ¬Ãâ1291.
- T. Liu and W. Liao, âÃâ¬ÃÅLocation-dependent throughput and delay in wireless mesh networks,âÃâ¬Ã IEEE Trans. Veh. Technol., vol. 57, no. 2, pp. 1188âÃâ¬Ãâ1198, Mar. 2008.
- X. Wang and J. J. Garcia-Luna-Aceves, âÃâ¬ÃÅDistributed joint channel as- signment, routing and scheduling for wireless mesh networks,âÃâ¬Ã Comput. Commun., vol. 31, no. 7, pp. 1436âÃâ¬Ãâ1446, May 2008.
- H. Mohsenian Rad and V. W. S. Wong, âÃâ¬ÃÅJoint optimal channel assign- ment and congestion control for multichannel wireless mesh networks,âÃâ¬Ã in Proc. ICC, 2006, pp. 1984âÃâ¬Ãâ1989.
- X. Lin and S. Rasool, âÃâ¬ÃÅA distributed joint channel-assignment, scheduling and routing algorithm for multi-channel ad hoc wireless networks,âÃâ¬Ã in Proc. INFOCOM, 2007, pp. 1118âÃâ¬Ãâ1126.
- H. Wu, F. Yang, K. Tan, J. Chen, Q. Zhang, and Z. Zhang, âÃâ¬ÃÅDistrib-uted channel assignment and routing in multiradio multichannel multi- hop wireless networks,âÃâ¬Ã IEEE J. Sel.AreasCommun., vol. 24, no. 11, pp. 1972âÃâ¬Ãâ1983, Nov. 2006.
- P. Kyasanur and N. H. Vaidya, âÃâ¬ÃÅRouting and interface assignment in multi-channel multi-interface wireless networks,âÃâ¬Ã in Proc. WCNC, 2005, pp. 2051âÃâ¬Ãâ2056.
- M. Alicherry, R. Bhatia, and L. Erran Li, âÃâ¬ÃÅJoint channel assignment and routing for throughput optimization inmultiradio wireless mesh networks,âÃâ¬Ã IEEE J. Sel. Areas Commun., vol. 24, no. 11, pp. 1960âÃâ¬Ãâ1971, Nov. 2006.
- Raniwala, K. Gopalan, and T. Chiueh, âÃâ¬ÃÅCentralized channel assign-ment and routing algorithms for multi-channel wireless mesh networks,âÃâ¬Ã ACM Mobile Comput. Commun. Rev., vol. 8, no. 2, pp. 50âÃâ¬Ãâ65, Apr. 2004.
- Raniwala and T. Chiueh, âÃâ¬ÃÅArchitecture and algorithms for an IEEE 802.11-based multichannel wireless mesh network,âÃâ¬Ã in Proc. INFOCOM, 2005, pp. 2223âÃâ¬Ãâ2234.
- K. N. Ramachandran, E. M. Belding, K. C. Almeroth, and M. M. Buddhikot, âÃâ¬ÃÅInterference-aware channel assignment in multi- radio wireless mesh networks,âÃâ¬Ã in Proc. INFOCOM, 2006, pp. 1âÃâ¬Ãâ12.
|