无线mesh网络中的信道分配问题研究_苏家勇

发布时间:2021-05-18 18:04:06

无线 mesh 网络中的信道分配问题研究
苏家勇 ,许   磊 ,周   国
( 重庆大学 通信工程学院 ,重庆 400030)
摘  要 : 在多接口无线 mesh 网络中使用多信道可以减少碰撞和干扰 , 提高系统吞吐量 。因此 , 合理的信道分配是 无线 mesh 网络中多信道技术的关键 。用图论理论建立信道分配数学模型以及用图着色理论研究信道分配问题是无线 网络中解决信道分配问题的有效方法 。因此针对无线 mesh 网络中多接口多信道 ( multi2radio and multi2channel ) 的特点 , 重点介绍了无线 mesh 网络中信道分配的基本 理 论 、 主要约束和图论模型等 , 最后提出应用图着色理论解决信道分 配 问题的一般途径 。 关键词 : 无线 mesh 网络 ; 多信道 ; 多接口 ; 信道分配 中图分类号 : TN924 + . 1     文献标识码 : A     文章编号 : 1003 - 3114 (2009) 05 - 04 - 3

Study on Channel Assignment Problem of Wireless Mesh Net work
SU Jia2yong ,XU Lei ,ZHOU Guo
( College of Communication Engineering , Chongqing University ,Chongqing 400030) Abstract :The goal of using multi2channel in multi2radio wireless mesh network is to reduce collision and interference and increase the throughput of the system. Therefore ,reasonable channel assignment is a key factor of multi2channel technology in wireless mesh network. It is an effective manner to establish mathematical model of channel assignment based on graph theory and study channel assignment problem by using graph coloring theory in wireless network. Therefore ,in view of the multi2radio and multi2channel ( MRMC) characteristic of wireless mesh network , the basic theory , graph theory mathematical model , main constrain of channel assignment problem in wireless mesh network are introduced. Finally ,the general way of solving channel assignment problem by using graph coloring theory is proposed. Key words :wireless mesh network ;multi2channel ;multi2radio ;channel assignment

0  引言
无线 mesh 网络 [1 ] 是基于 IP 协议的无线宽带接 入技术 ,主要功能体现在无中心 、 自组网 、 多级跳接 和路由判断选择等 。对于无线 mesh 网络来说 ,节点 间的干扰会使网络的传输性能严重降级 。为了降低 节点间干扰提高 mesh 网络的容量 ,一些研究者提出 了多接口 ( radios) 无线 mesh 网络的概念 , 每个节点 都配备有多个无线接口 , 每个接口都具有完整的物 理层和介质访问控制层 , 独立工作互不影响 。通过 给每个接口分配频率 ( 信道) 可以使同一碰冲突域内 的节点对可以在不同的信道上同时传输而不发生冲 突 ,从而提高了网络的吞吐量 。
基金项目 1 : 层次化*丝刂频目泶尴咦宰橥逑笛芯 , 国家高新 技术研究发展专项课题 ,课题编号 :2008AA01Z202 ; 基金项目 2 : 认知 网格网*斯芾 MAC 协议和资源动态分配策略研究 ,国家自然科学 基金项目 ,项目编号 :60872038 收稿日期 :2009 - 07 - 02 作者简介 : 苏家勇 (1982 - ) ,男 ,硕士研究生 。主要研究方向 : 无线网 络中的频谱资源分配和多信道技术 。

在数学上通常用图论理论为无线网络建立数学 模型 , 并应用图着色理论[2 ] 来解决信道分配问题 。 图着色理论通常给网络节点分配不同颜色以使满足 信道约束 ( 同道约束 、 邻道约束等 ) 的节点保持信道 分离 ,最后达到使用最少的信道资源使整个网络无 干扰或干扰最小 。这一信道分配理论在蜂窝网络中 得到了很好的应用 ,但由于无线 mesh 网络存在网络 中信道数目有限 、 节点接口数约束 、 接口共享以及信 道分配带来的波及效应等信道分配约束 , 使得传统 的基于图着色理论的信道分配问题无法直接应用于 无线 mesh 网络中的信道分配问题 。但其理论基础 仍对指导无线 mesh 网络中的信道分配问题有着重 要的价值 。本文首先阐述了无线 mesh 网络中信道 分配的基本问题 、 网络模型和主要约束 ,最后总结了 应用传统的图着色模型解决无线 mesh 网络中信道 分配的基本思路与面临的基本问题 。

1  问题描述
111   多接口无线 mesh 网络 无线 mesh 网络可以和多种无线网络系统 ,如无
Vol135 No15 2009

  4  

R adio Communications Technology
? 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved.

http://www.cnki.net

线局域网 ( WLAN) 、 无线个域网 ( WPAN) 以及无线城 域网 ( WMAN) 等相结合 ,改善无线网络的性能 ,提高 网络的覆盖范围 。随着无线 mesh 网络技术的广泛 应用 ,IEEE802 的相关标准组正在致力于推动无线
mesh 网络技术的发展 , 制订相关的技术标准 。目

分配的关键问题 。 信道分配算法的主要约束[5 ] 包括 : ①总的可使 用的信道数目是固定的 ; ② 分配给 mesh 路由器的 不同信道数目受到该路由器接口数量的限制 ; ③互 相通信的 2 个节点必须绑定在一个公共信道上 ; ④存在干扰且共享同一信道的各个链路上期望发 送的业务负载总量不能超过信道的原始容量 。

前 ,无线 mesh 网络标准已经出现在 IEEE802. 11s 、
802. 15 、 802. 16 、 802. 20 中[1 ] 。

每个网络节点安装多个接口 ( 多 radios) 被广泛 认为是提高无线 mesh 网络容量的有效途径 。IEEE
802. 11b 和 802. 11a 标准分别提供了 3 和 12 个非重

2  信道分配问题比较
无线 mesh 网络在无线蜂窝网络中信道分配问 题已经进行了大量的研究 [ 5 ] 。其基本概念就是划分 无线频谱为非重叠的无线信道集 , 把这些信道资源 分配给基站 , 使得存在信道分配约束 ( 邻道约束 、 同 道约束等) 的基站分配不同的信道 。在数学上通常 建立图论模型 G ( V , E) , 其中 V 表示网络中的节点 集合 , 每个节点 v ∈V 代表一个发射机或基站 , E 表 示约束边集合 , 如果 2 个节点存在潜在信道分配约 束 , 则在它们之间用一条边 e ∈ E 连接 。通常给每 个节点分配一组信道| f ( v) | = Dv , Dv ∈Z , 并且对任 意 f ∈f ( v ) , f ∈f ( v ) , 要求 | f - g | | Tvw , Tvw ∈ Z ,
Tvw 为信道分配约束禁用组合 , 即给节点分配的信道

叠信道 ,这样 mesh 路由器和邻居节点就可以通过多
radios 使用这些非重叠信道同时进行信息的发送和

接收 ,可以有效地提高频谱利用率和增加网络带宽 。
112   频率( 信道) 分配问题

频率分配问题 ( FAP) 也叫信道分配问题 , 就是 给网络站点分配频率 , 使得在合理的频率复用条件 下达到网络干扰可以避免或者达到干扰最小化 。对 于一个网络 ,一个可行的频率分配方案就是给每个 站点 u 分配的频率 f ( u ) 满足一定的频率和距离约 束 。通常情况下频率分配有 2 种目标 : ①最小化使用的频率带宽范围 ( 跨度) : 跨度是 网络中分配的最大频率和最小频率的差值 , 在实际 网络中频率资源通常是一段连续带宽而不是离散的 频率 。因此这种形式的频率分配也叫最小跨度频率 分配 ; ②最小化使用的频率数目 ( 阶 ) : 这种情况往 往在网络中的频率带宽不连续的情况下进行研究 , 可以使网络使用尽可能少的频率资源 。 目前频率分配问题 ( FAP) 已被很多工程师 、 数 学家 、 科学家研究 , 但普遍证明这个问题是一个 NP 难的问题 , 并且广泛认为 FAP 最接*于图着色问 题 ,因此大部分的研究者集中于图着色理论和基于 图着色的启发式算法 [3 ] 。信道分配中常用的图着色 理论包括 List2coloring 、 Set2coloring 、 T2coloring 、 List T2 [4 ] λ coloring 、 2coloring 等 。
113   信道分配问题和主要约束

要满足信道分配约束 。其次要求 min 6 f ( v ) , 即要
v ∈V

使网络所使用的信道数最少 。当然在固定信道数的 情况下 ,还要最小化网络干扰 。因此无线蜂窝网络 中的信道分配的目标是最小化网络干扰以有效地增 加频谱的空间复用效率 。 相反 ,无线 mesh 网络中的信道分配与蜂窝网络 中的信道问题有很大的不同 。首先无线 mesh 网络 中 ,mesh 客户端和有线网之间 mesh 路由器形成多 跳无线连接 ,也就是说 mesh 网络是多跳网络 , 邻居 节点之间必须共享相同信道 。而蜂窝网中用户终端 直接通过一跳和基站进行通信 , 终端节点不直接通 信 。其次 ,无线 mesh 网络中的信道分配的目标是使 干扰最小和保持一定的网络连接 , 而蜂窝网络以最 小化干扰为目标 。

无线 mesh 网 络 的 信 道 分 配 问 题 的 输 入 为 : ①连接图 ; ② 非重叠的信道数 ; ③ 每个 mesh 路由 器上配置的接口数 ; ④ 每个通信链路上的业务负 载 ,输出为每个接口绑定一个信道 。目前来讲以怎 样的方式给每个接口分配信道 ( 频率) 使得节点间的 干扰最小化和连接最大化是无线 mesh 网络中信道
2009

3  图论模型和存在问题
311   信道分配图论模型 3. 1. 1   连接图

为了用图论理论建立无线 mesh 网络模型 ,通常   5  
http://www.cnki.net

年第 35 卷第 5 期

无线电通信技术

? 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved.

假设无线 mesh 路由器分布在*面上 , 每个 mesh 路 由器的全向天线有 1 个或多个接口 , 同时假设每个 ( R < R′ )。 接口有相同的传输距离 R 和干扰距离 R′ 根据以上的假设 , mesh 路由器间的连接可以用无向 图 G ( V , E) 来表示 , 称为连接图 。如果节点在彼此 的传 输 距 离 之 内 , 它 们 之 间 就 用 一 条 边 连 接。 图 1 ( a) 为网络中有 5 个节点组成的 7 边连接图的一 个简单举例 , 假设其冲突域为 2 跳范围 。

图1  连接图和冲突图举例

3. 1. 2   冲突图

由于连接图的链路之间存在潜在干扰 , 这样以 连接图为基础可以得到描述网络干扰模型的冲突图 Gc ( Vc , Ec) , 连接图中的每条边对应冲突图中的1 个 顶点 , 如果连接图中的链路相互存在干扰 , 在冲突图 中对应的顶点用 1 条边连接 , 因此 , 冲突图更直观地 表示了网络中的干扰约束 。图 1 ( b) 为图 1 ( a) 对应 的冲突图 , 该图的 7 个节点对应图 1 ( a) 中的 7 条边 。 312   信道分配存在的基本问题 3. 2. 1   最大化网络连接与最小化干扰权衡问题 一个无线 mesh 网络节点在通信范围内必须和 它的各个邻居节点共享一条信道 , 也就是建立虚连 接 。同时 ,为了降低网络干扰 ,和一个节点共享相同 信道的邻居节点数目应尽量少 , 这样最大化网络连 接和最小化网络干扰之间存在着权衡 。图 2 表述了 这种权衡关系 。图 2 ( a) 中 ,每个节点有 2 个接口 ,并 且有 5 个非重叠信道用来通信 。如果任意 2 个节点 在彼此通信范围内 , 则它们之间都有一个公共信道 以实现最大化网络连接 ,尽管如此 ,由于潜在干扰不 是所有的链路都能同时工作 ,因此这种最大化连接

不可能实现的 。图 2 ( b) 中则表示在有 5 个非重叠 信道和每个节点有 2 个接口的情况下 , 所有的链路 都能够同时工作并且网络干扰能够完全消除 , 但是 代价是节点 a 和 c 、 b 和 d 以及 b 和 e 之间的虚拟连 接被断开 。 3. 2. 2   接口共享和信道依存问题 在无线 mesh 网络中为了维持最大化网络连接 , 几条链路可能要共享同一个接口 , 如图 1 ( a ) 中链路 b2d 、 b2e 和 b2c 要共享同一个接口并分配相同的信 道 , 由于网络干扰这些链路不能同时工作 。链路共 享接口问题会带来信道依存问题 , 也就是共享同一 接口的链路中有 1 个改变信道时 , 其他链路也就切 换到相同信道 , 这种现象称为波及效应 。如图 1 ( a) 中链路 b2d 有信道 2 切换到信道 3 时 , 链路 b2e 、 b2c 和 d2e 也就切换到信道 3 。节点之间的这种依赖性 使得很难预测信道重分配带来的影响 。 此外 , 信道分配算法必须考虑虚拟链路上的大 量业务负载 , 通常假设网络中各个虚拟链路有相同 的业务负载 , 但在一些链路 ( 比如网关节点 ) 携带负 载比其他链路多时这种假设就不成立[6 ] 。通常支持更 多业务的节点应该和尽量少的邻居节点共享信道。

4  基于图着色理论的网络信道分配问题
在实际的无线 mesh 网络中 ,网络节点接口的数 量要比可用信道的数目多的多 ,在给定 mesh 路由器 和网关的情况下 ,必须组建一定的 mesh 网络*私 构以适合特定的应用 , 然后在网络*说幕∩细 每个 链 路 进 行 频 率 ( 信 道 ) 分 配 。通 常 假 设 无 线 mesh 网络中有 N 个网络节点 , 对于每个节点 i ∈N , 其对用的接口数为 R i , R i Ε 2 , 并不要求所有节点有 相同的接口数 。非重叠信道集合 k = { 1 , 2 , …, F} , Vc = { l ij | ( i , j ) } , ( i , j) 是通信链路 , Gc ( Vc , Ec ) 为网 络冲突图 。信道分配问题就是计算函数 f : Vc →k 以最小化网络干扰 I ( f ) , 同时满足相应的接口约束 。 总体上来讲无线 mesh 网络中多信道下的信道 分配问题可分为 2 类 , 第 1 类在网络*瞬环⑸ 化的情况下为网络节点长时进行静态分配信道 , 第 2 类每隔一定的短时间隔进行动态信道分配[6 ] 。 对于静态信道分配类似于图着色问题 。如果对 连接图进行信道分配 ,则无线 mesh 网络中的信道分 配类似于边着色问题 , 无线网络中常用的边着色理 论为距离 2 边着色 , 也就是距离为 2 跳的边要着不 同的颜色 ,同时与每个节点相连的边分配的信道数 应不大于该节点的接口数 。 传统的信道分配理论
( 下转第 43 页) Vol135 No15 2009

图2  最大化网络连接和最小化网络干扰权衡举例

  6  

R adio Communications Technology
? 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved.

http://www.cnki.net

交的要求 。 标校和调整主要内容包括 : ( 1) 赤经轴倾斜角度的调整 使用倾斜仪 , 调整赤经轴与水*面的夹角与当 )。 地地理纬度相等 ( 约 36. 24° ( 2) 赤经轴方位的调整 使用陀螺指北仪 ,贴靠代表赤经轴的基准*面 , 根据仪器的方位读数 , 通过结构中的可调环节调整 赤经装置的安装位置 , 使赤经轴方位与当地地理经 )。 线*行 ( 即方位 180° ( 3) 赤纬轴与赤经轴正交 主要依靠设计的技术措施通过加工和安装来 保证 。
( 上接第 6 页)

4  结束语
综上所述 , 极轴式天线座在太阳射电系统的实 时观测中起到了不可替代的作用 。迄今为止 , 某太 阳观测系统已成功运行一年多 , 充分验证了极轴天 线座的设计满足了战术技术指标要求 。目前 ,中 、 大 型极轴天线在国内还不多见 , 相信随着射电天文事 业的发展 ,极轴天线座将得到越来越广泛的应用 。
参 考 文 献 [1 ]   吴凤高 . 天线座结构设计 [M] . 西安 : 西北电讯工程学 院出版社 ,1986. [2 ]   郑元鹏 . 面天线结构动态误差对指向精度的影响 [J ] . 无线电通信技术 ,2002 ,28 (6) :37 - 39. [3 ]   张润逵 , 戚仁欣 , 张树雄 , 等 . 雷达结构与工艺 [ M] . 北 京 : 电子工业出版社 ,2007.

通常采用节点着色理论使满足信道约束的网络节点 分配的信道互相分离 , 这一理论可以应用在冲突图 上 ,即对无线 mesh 网络冲突图进行节点着色 , 但是 冲突图信道分配忽略了信道分配的接口约束 。因此 理论上冲突图模型在节点接口数不受约束的理想情 况下 ,对研究信道分配问题所用信道数的上下界有 着很重要的指导价值 , 可以和传统的信道分配中最 小阶和最小跨度信道分配对应起来 。而连接图模型 更适宜于约束情况下的信道分配问题 , 能更好地解 决信道分配局部优化问题 。当然在具体实施信道分 配算法时要考虑网络中的业务情况 , 很多研究者提 出的信道分配算法依据每个链路上的总业务量 、 距 离网关节点的跳数和节点接口数给链路分配优先 级 ,然后按照优先级次序为链路静态分配信道 。 而无线 mesh 网络中的动态信道分配问题则要 考虑*吮浠 、 业务变化 、 路由问题和网络干扰问 题 。其中业务 、 路由和干扰变化是考虑的主要因素 。 通常在一定的时间间隔内估计和测量各个无线链路 的干扰域内的干扰链路 , 对不满足要求的链路重新 进行信道分配 。而与路由问题 、 业务相结合的信道 分配问题越来要受到重视 , 并且在一定条件下对提 高网络总吞吐量比静态信道分配有明显优势 , 如文 献 [ 7 ] 中提出了信道分配和路由相结合的算法 ,该算 法组成多个生成树以更好了适应业务负载的动态 性 ,该算法证实了信道分配依赖于虚拟链路上的业 务负载 ,而业务负载又依赖于路由 。可以说动态信 道分配是在静态信道分配基础上的进一步优化 , 静 态信道分配仍是整个信道分配理论的基础 , 其中图 着色理论仍对指导无线 mesh 网络中的信道分配问 题有着重要的价值 。
2009

5  结束语
本文对多接口条件下无线 mesh 网络中的信道 分配问题进行了分析 ,重点介绍了无线 mesh 网络中 信道分配的基本理论 、 主要约束和图论模型等 。虽 然传统的图着色理论直接应用于多接口无线 mesh 网络会受到一定的制约 , 但其理论基础仍对指导无 线 mesh 网络中的信道分配问题仍有重要指导意义 。 特别是无线 mesh 网络中的静态信道分配问题可以 和约束边着色很好的对应起来 。
参 考 文 献 [1 ]   AKYILDIZ I F , WANG XU2DONG, WANG WEI2LIN. Wireless mesh networks : a survey , Broadband and wireless networking (BWN) lab[J ] . School of Electrical and Computer Engineering , 2004 , 47 (4) :4452487. [2 ]   J ENSEN T R , TOFT B. Graph Coloring Problems [ M ] . New Y ork :Wiley Interscience ,1995 :50 - 95. [3 ]   MARTELLO S ,TOTH P. Heuristic algorithms for the multiple knapsack problem[J ] . Journal of Computing , 1981 ,27 ( 1 ) : 93 - 112. [4 ]   FOTAKIS D , NIK OLETSEAS S ,PAPADOPOULOU V ,et al. Spirakis. Hardness results and efficient approximations for frequency assignment problems : Radio labelling and radio coloring[J ] . Computing and Informatics 20 , 2001 , 15 ( 6 ) : 121 - 180. [5 ]  K ATZELA I ,NAGHSHINEH M. Channel assignment schemes for cellular mobile telecommunication systems : A comprehensive survey [ J ] . IEEE Personal Communications , 1996 ,3 (3) :10 - 31. [6 ]   SUBRAMANIAN A P , KRISHNAN R , DAS S R , et al. Minimum interference channel assignment in multi2radio wireless mesh networks [ J ] . Sensor , Mesh and Ad Hoc Communications and Networks , 2007 ,7 (4) :481 - 490. [7 ]   RANIWALA A , G OPALAN K, CHIUEH T. Centralized channel assignment and routing algorithms for multi2channel wireless mesh networks [ J ] . ACM Mobile Computing and Communications Review (MC2R) , 2004 ,8 (2) :50 - 65.

年第 35 卷第 5 期

无线电通信技术
http://www.cnki.net

  43  

? 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved.


相关文档

  • 无线Mesh网络中的信道分配研究
  • 无线mesh网络中的信道分配问题研究
  • 关于无线Mesh网络信道分配策略的探讨
  • 无线Mesh网络中基于信道状态的动态信道分配算法研究
  • 无线Mesh网络中混合信道分配算法研究
  • 无线Mesh网络联合信道分配和路由协议研究
  • 多信道无线Mesh网络的性能研究
  • 无线Mesh网络部分重叠信道分配综述
  • 基于*朔指畹奈尴進esh网络信道分配策略
  • Mesh网络中实用有效的多信道分配方法
  • 无线Mesh网络中的信道分配研究
  • 无线mesh网络中的信道分配问题研究
  • 关于无线Mesh网络信道分配策略的探讨
  • 无线Mesh网络中基于信道状态的动态信道分配算法研究
  • 无线Mesh网络中混合信道分配算法研究
  • 无线Mesh网络联合信道分配和路由协议研究
  • 多信道无线Mesh网络的性能研究
  • 无线Mesh网络部分重叠信道分配综述
  • 基于*朔指畹奈尴進esh网络信道分配策略
  • Mesh网络中实用有效的多信道分配方法
  • 猜你喜欢

  • 在办公室厕所吸烟检讨书2020
  • 关于校园趣事的作文500字
  • 张爱芳运用加味桂枝茯苓丸巧治妇科病验案举隅
  • 早餐吃鸡蛋牛奶可减少盐的摄入
  • 油田井下作业中的环保技术应用分析
  • 2019学年三年级第一学期班主任工作计划【精选】
  • 【2019年整理】车辆日常维护作业规范
  • 班级工作计划幼儿园小班上学期(一)范文
  • 柴油机进气和排气装置的构造及其作用
  • 国家行政学院教育经济与管理专业考博招生人数-育明考博
  • 大学生物流实*报告4000字
  • 2019-2020年高中音乐《享受合唱的艺术美》教学设计
  • 黑龙江导游词分享
  • 改良双侧颈总动脉结扎法与传统法制备的大鼠慢性脑缺血模型比较
  • 人就是一切--读《杰克·韦尔奇自传》
  • 【K12学*】关于幼儿中班心理健康教案
  • 人教版八年级语文下册《综合性学习:献给母亲的歌》46张课件
  • 一种转阀换向的液压双缸单作用往复泵设计
  • 最新-学生会办公室工作计划 办公室工作计划开头范文参考 精品
  • 公司怎么注册商标
  • 【免费下载】机械设计终极版有答案
  • 【实用范文模板】2020学校炊事员聘用合同范本【优质版】
  • 可口可乐发展史 这些你了解吗?
  • 美国俚语的社会语言学研究
  • 职场上如何面对一份你不喜欢的工作
  • websocket 简介
  • 中国农业银行三峡分行?亭支行长江储蓄所企业信用报告-天眼查
  • 办理国外签证需要准备的资料翻译
  • 学院教师岗位聘任期管理与考核办法(DOC 37页)
  • 核心力量训练在高校体育教学中的应用综述
  • 校友联谊会活动方案
  • 辽宁省实验中学一所影响学生一生的学校
  • 信息变更流程流程财务标准化作业指导书
  • 贵州昂立教育咨询有限公司企业信用报告-天眼查
  • 【推荐下载】教师的幸福感读后感-word范文模板 (3页)
  • llvm安装方式_带你读《LLVM编译器实战教程》之一:构建和安装LLVM-阿里云开发者社区...
  • 低压脉冲袋式除尘器在料场除尘系统中的应用
  • 五年级上英语课件-Unit 3 What's your favourite food_人教(PEP)2014秋
  • 古代文学史笔记-隋唐五代
  • 兼容安卓微信调用摄像头
  • 基于实践教学支撑*台的ERP课程体系建设
  • 20132014学年高中数学人教B版选修11配套备课资源231抛物线
  • 电脑版