BFS-CA Algorithm for Channel Assignment in Multi-Radio Wireless Mesh Networks

• Download source code for BFS-CA algorithm for Mesh Network - 131.78 KB

Introduction

The channel assignment problem for mesh networks is similar to the list coloring problem, which is defined as follows: given a graph, G = (V,E), and for every v in V , a list L(v) of colors, is it possible to construct a valid vertex coloring of G such that every vertex v receives a color from the list L(v)? The list coloring problem is NP-complete [21]. Therefore, we rely on an approximate algorithm for channel assignment. Our algorithm, called the Breadth First Search Channel Assignment (BFS-CA) algorithm, uses a breadth first search to assign channels to the mesh radios. The search begins with links emanating from the gateway node. The rationale behind the use of breadth first search is intuitive: by using breadth first search, we satisfy our goal described in Section III of giving channel assignment priority to links starting from the gateway and then in decreasing levels of priority to links fanning outward towards the edge of the network.

Background

This is the algorithm:

Algorithm 1 BFS-CA Algorithm:

1: Let V = {v|v 2MCG}
2: while notAllVerticesVisited{V } do
3: Let h = smallestHopCount(V )
4: Q = {v|v 2 V and notVisited(v) and hopcount(v) == h}
5: sort(Q)
6: while size(Q) > 0 do
7: vcurrent = removeHead(Q)
8: if visited(vcurrent) then
9: continue
10: end if
11: visit(vcurrent)
12: Vn = {u|u 2 MCG and edgeInMCG(u, vcurrent) == TRUE}
13: permanently assign highest ranked channel c from vcurrent’s channel
ranking that does not conflict with ui, {ui 2 Vn and 0  i <
size(Vn)}
14: if c does not exist then
15: permanently assign random channel to vcurrent
16: end if
17: L = {v|v 2MCG and v contains either radio from vcurrent}
18: removeVerticesInListFromMCG(L)
19: tentatively assign c to radios in L that are not part of vcurrent
20: Let rf be router with interface in vcurrent that is farthest away
from gateway
21: Let Tail = list of all active v (v 2 MCG) such that v contains an
interface from rf
22: sort(T)
23: addToQueue(Q, Tail)
24: end while
25: permanently assign channels to radios that are unassigned a permanent
channel.
26: end while

Using the Code

Creating neighbor code:
//boolean createNeighbor(String radioIP, String neighborIP, int neighId) {
    boolean createNeighbor(String radioIP, String neighborIP) {
        Radio myRadio = (Radio) radios.get(radioIP);
        if (myRadio == null) {
            System.out.println("createNeighbor: Radio object for " + 
					radioIP + " does not exist");
            return false;
        }

//        return myRadio.createNeighbor(neighborIP, neighId);
        return myRadio.createNeighbor(neighborIP);
    }
    
    boolean neighborExists(String radioIP, String neighborIP) {
        Radio myRadio = (Radio) radios.get(radioIP);
        if (myRadio == null) {
            System.out.println("neighborExists: Radio object for " + 
					radioIP + " does not exist");
            return false;
        }
        return myRadio.neighbors.containsKey(neighborIP);
    }
/*

How to Run Project

java rica -r relay_information -g gateway_info -n neighbor_table 
       -p ap-priority-list -c channel-rank-file

The relay_information file contains information about each node in the mesh network, such as its hostname, its radios, radio types (802.11a/b/g), and radio IP addresses. The gateway-info file contains the identity of the gateway in the network. In the example file provided in the config folder, the first name in the file is the gateway. All other hostnames are essentially routers that associate with this gateway. The neighbor_table file contains the latest topology information. RICA uses the latest topology information to decide which channels to use for which radios. The paper indexed above describes how the topology information is gathered in the TIC architecture. The ap-priority-list contains a ranking of APs. RICA gives channel assignment priority to APs ranked higher. Ranking becomes important when not enough channels or radios are available because of which links in interfering range of each other can be assigned the same channel. Therefore ranking can influence inter-flow interference. The paper has more on this condition. Finally, channel-rank-file allows each radio to influence which channels are assignable to it. So for example, if there is a lot of external interference on channel 36 in the neighborhood of a router, that router can inform RICA of its disliking for channel 36 by placing it last on the ranking list.

Example use contained in source package:

java rica -r config/meshnet-dotab-hosts -g config/meshnet-gateways 
     -n neighbortable -p config/meshnet-ap-priority -c config/meshnet-channel-ranking

The above invocation generates an assignments file that contains the channel assignments for each IP address in the relay_information file. Any assignment equal to -1 means that RICA never assigned a channel to it. This typically happens because either the IP is not reachable or the router containing that radio is reachable through another of its own radio. RICA does not perform flow splitting. Therefore, the same "best" route is always used. The best route is the route that yields the lowest WCETT metric. WCETT is a multi-radio routing metric. This publication describes WCETT in detail. To understand how RICA uses WCETT, please refer to our publication indexed above.

OUTPUT

Channel Assignments:
Host - mobile6; 10.2.1.106 52 (permanent)
Host - mobile3; 10.2.1.103 44 (permanent)
Host - mobile2; 10.2.2.102 44 (permanent); 10.2.1.102 52 (permanent)
Host - mobile5; 10.2.1.105 52 (permanent)
Host - h3123; 10.2.1.25 44 (permanent)
Host - h3115; 10.2.1.8 60 (permanent)
Host - h4123; 10.2.1.20 44 (permanent)
Host - h1151; 10.2.1.2 157 (permanent)
Host - h3155; 10.2.1.9 44 (permanent)
Host - h2113; 10.2.1.21 60 (permanent)
Host - h2151; 10.2.1.60 157 (permanent)
Host - h2116; 10.2.1.4 52 (permanent)
Host - h2164; 10.2.1.7 52 (permanent)
Host - hmobile; 10.2.1.109 52 (permanent)
Host - mobile0; 10.2.2.100 36 (permanent); 10.2.1.100 157 (permanent)
Host - mobile1; 10.2.2.101 36 (permanent); 10.2.1.101 44 (permanent)
Host - h5119; 10.2.1.27 52 (permanent)
Host - h2121; 10.2.1.5 36 (permanent); 10.2.3.5 60 (permanent); 10.2.2.5 149 (permanent)
Host - h2120; 10.2.1.3 149 (permanent); 10.2.2.3 52 (permanent)
mobile6 : 10.2.1.5->10.2.2.101 10.2.1.101->10.2.2.102 10.2.1.102->10.2.1.106 
mobile3 : 10.2.1.5->10.2.2.101 10.2.1.101->10.2.1.103 
mobile2 : 10.2.1.5->10.2.2.101 10.2.1.101->10.2.2.102 
mobile5 : 10.2.1.5->10.2.2.101 10.2.1.101->10.2.2.102 10.2.1.102->
				10.2.1.106 10.2.1.106->10.2.1.105 
h3123 : 10.2.1.5->10.2.2.101 10.2.1.101->10.2.1.25 
h3115 : 10.2.3.5->10.2.1.21 10.2.1.21->10.2.1.8 
h4123 : 10.2.1.5->10.2.2.101 10.2.1.101->10.2.1.25 10.2.1.25->10.2.1.20 
h1151 : 10.2.1.5->10.2.2.100 10.2.1.100->10.2.1.60 10.2.1.60->10.2.1.2 
h3155 : 10.2.1.5->10.2.2.101 10.2.1.101->10.2.1.103 10.2.1.103->10.2.1.9 
h2113 : 10.2.3.5->10.2.1.21 
h2151 : 10.2.1.5->10.2.2.100 10.2.1.100->10.2.1.60 
h2116 : 10.2.2.5->10.2.1.3 10.2.2.3->10.2.1.4 
h2164 : 10.2.1.5->10.2.2.101 10.2.1.101->10.2.2.102 10.2.1.102->10.2.1.7 
hmobile : 10.2.1.5->10.2.2.101 10.2.1.101->10.2.2.102 10.2.1.102->10.2.1.109 
mobile0 : 10.2.1.5->10.2.2.100 
mobile1 : 10.2.1.5->10.2.2.101 
h5119 : 10.2.1.5->10.2.2.101 10.2.1.101->10.2.2.102 10.2.1.102->10.2.1.27 
h2120 : 10.2.2.5->10.2.1.3 

History

• 6^th August, 2009: Initial post