多无线电无线网状网络中的 BFS-CA 算法用于信道分配

• 下载网状网络 BFS-CA 算法的源代码 - 131.78 KB

引言

网状网络的信道分配问题与列表着色问题类似，定义如下：给定一个图 G = (V,E)，并且对于 V 中的每个 v，都有一个颜色列表 L(v)，是否可以构造 G 的有效顶点着色，使得每个顶点 v 都从列表 L(v) 中接收一种颜色？列表着色问题是 NP 完全问题 [21]。因此，我们依赖于一种近似算法进行信道分配。我们的算法，称为广度优先搜索信道分配 (BFS-CA) 算法，使用广度优先搜索为网状无线电分配信道。搜索从网关节点发出的链接开始。使用广度优先搜索背后的理由是直观的：通过使用广度优先搜索，我们满足了第三节中描述的目标，即优先考虑从网关开始的链路的信道分配，然后优先考虑扇出到网络边缘的链路的信道分配。

背景

这是该算法

算法 1 BFS-CA 算法

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);
    }
/*

如何运行项目

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

relay_information 文件包含有关网状网络中每个节点的信息，例如其主机名、其无线电、无线电类型 (802.11a/b/g) 和无线电 IP 地址。 gateway-info 文件包含网络中网关的身份。在 config 文件夹中提供的示例文件中，文件中的第一个名称是网关。所有其他主机名本质上都是与此网关关联的路由器。 neighbor_table 文件包含最新的拓扑信息。 RICA 使用最新的拓扑信息来决定为哪些无线电使用哪些信道。上面索引的论文描述了如何在 TIC 架构中收集拓扑信息。 ap-priority-list 包含 AP 的排名。 RICA 优先为排名较高的 AP 分配信道。当没有足够的信道或无线电可用时，排名变得很重要，因为彼此干扰范围内的链路可以分配到相同的信道。因此，排名会影响流间干扰。该论文对此情况有更多说明。最后，channel-rank-file 允许每个无线电影响可分配给它的信道。因此，例如，如果路由器附近信道 36 上存在大量外部干扰，则该路由器可以通过将其放置在排名列表的最后一位来通知 RICA 它不喜欢信道 36。

源代码包中包含的示例用法

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

上面的调用会生成一个 assignments 文件，该文件包含 relay_information 文件中每个 IP 地址的信道分配。任何等于 -1 的分配都意味着 RICA 从未为其分配信道。这通常是因为 IP 不可访问，或者包含该无线电的路由器可以通过其自己的另一个无线电访问。 RICA 不执行流拆分。因此，始终使用相同的“最佳”路线。最佳路线是产生最低 WCETT 指标的路线。 WCETT 是一种多无线电路由指标。此出版物详细描述了 WCETT。要了解 RICA 如何使用 WCETT，请参阅上面索引的我们的出版物。

输出

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 

历史

• 2009 年 8 月 6 日：首次发布