无线Mesh网络的最大并发公平调度

无线Mesh网络的最大并发公平调度 北 京 邮 电 大 学 学 报Aug. 2007 2007 年 8 月 第 30 卷 第 4 期Vol . 30 No . 4 Journal of Beijing U niversity of Post s and Teleco mmunicatio ns () 文章编号 :100725321 20070420033204 无线 Mesh 网络的最大并发公平调度 王英杰 ,刘觅 ,吴振华 ,彭木根 ,王文博 ( ) 北京邮电大学 无线信号处理与网络实验室 , 北京 100876 摘要 : 研究了基于 I EEE 802 . 16 的集中式控制无线 Mesh 网络 ,提出了一种基于干扰集的树形路由和基于最大并发集的公平下行调度算法. 该路由算法使树上节点具有较小的干扰度 ,从而达到干扰避免的效果. 基于此干 扰避免树的下行调度实现对最大并发集的高效利用 ,同时尽量保证节点业务请求满意率的公平性. 仿真结果表明 , 由于节点干扰度的降低以及并发传输机会的增加 ,网络吞吐量得到提高 ,并满足了一定的公平性要求. 关 键 词 : 无线 Mesh 网络 ; 树形路由 ; 下行调度 中图分类号 : TN915101 文献标识码 : A Fa ir Schedul ing f or Ma ximal Concurrent Transmissions in Wireless Mesh Net works WAN G Ying2jie , L IU Mi , WU Zhen2hua , P EN G Mu2gen , WAN G Wen2bo ( )Wireless Signal Processing and Net wo r k L ab , Beijing U niversit y of Po st s and Teleco mmunicatio ns , Beijing 100876 , China Abstract : The wireless mesh net wo r ks based o n t he I EEE 802 . 16 standard and co nt rolled in a cen2 t ralizedway were st udied. And an interference set based t ree ro uting algo rit hm and a maximal clique based f air dow nlink scheduling algo rit hm were p ropo sed. The p ropo sed ro uting algo rit hm will make t he no des o n t he ro uting t ree be of less interference degree in o rder to get an interference2aware t ree , w hile t he p ropo sed dow nlink scheduling o n t he basis of t his t ree will take f ull advantage of maximal cliques , as well as ensures f air ness amo ng request satisf actio n ratio s. Simulatio n show s t hat a great net2 wo r k t hro ughp ut enhancement w hich is benefited f ro m t he decrease of no de’s interference degree alo ng wit h t he increase of co ncurrent t ransmissio ns , and a satisf actio n wit h t he f air ness. Key words : wireless mesh net wo r ks ; t ree ro uting ; dow nlink scheduling [ 1 22 ] ( ) PMP点 I EEE 802116 标准定义的无线宽带城域网拓扑下视距传输对网络覆盖的极大限制. 空中接口支持 Mesh 网络拓扑结构 , 提供高速 提高集中式无线 Mesh 网络的吞吐量是达到上 率“最后 1 km”接入互联网服务 , 可称为无线 Mesh 述设计目的的关键 , 而研究干扰和空间复用等因素 ( ) 网络. 集中式控制模式下的无线 Mesh 网络中的用的影响 , 探索高效的路由和媒体接入控制 MAC层 ( ) 户站 SS , subscriber statio n , 允 许 为 其 他 与 基 站多跳无线资源管理成为人们主要的研究方法. 文献 ( () ) B S ,base statio n无直接连接的 SS 中继数据包以多 [ 3 ]提出空间时分多址 TDMA的信道接入 , 举 跳的方式通过 B S 接入骨干网 , 在尽量不降低网络 例说明了得到最大并发集的方法 , 但没有提供基于 容量的条件下提高系统的节点覆盖率 , 突破点到多 数学模型的调度算法描述 , 且其设计目的只限于最 收稿日期 : 2006209205 ( ) 基金项目 : 国家自然科学基金项目60572120 ,60602058 ( ) 作者简介 : 王英杰1978 —, 男 , 博士生 , E2mail : wyjleo @gmail . co m. 小化消息传输时延 ; 文献[ 4 ]在文献[ 3 ] 的基础上表节点要求发送给其子节点 i 的所有业务 , 包括以节述了根据最大并发集得到公平调度的算法 , 但其变 点 i 为目的节点的下行业务 , 也包括为节点 i 子树 化的调度周期不适用固定帧长的协议 , 且其公平性 上所有子孙节点中继的下行业务. 是针对两层网络模型中的下层终端 , 与本文讨论的 情形有很大差异 ; 文献[ 5 ]提出考虑节点间干扰的路 由和调度跨层#设计# , 但没有明确路由算法中的 节点加入顺序这一影响性能的关键因素 , 而调度算 法既没有理论优化也不能保证公平性. 本文提出了一种基于 I EEE 802116 标准无线 Mesh 网络的最大并发公平调度算法 , 提供了干扰分 析和调度集得出的数学模型 , 设计目的扩展到利用 最大并发集实现空间复用对网络吞吐量的提升 , 明 确了路由算法中的节点加入顺序 , 调度算法的公平 图 1 拓扑 、干扰与业务模型性定义针对 SS 节点的自身及中继业务请求 , 且算 首先 , 根据节点位置及邻居集合信息为数据调 法适用于固定帧长的协议. ( ) 度和传输生成集中式路由树 T = V , A , 以避免树 枝链路间干扰为目的 ; 然后 , 依据此干扰避免树及每 个 SS 在当前调度周期内的带宽请求在 B S 端进行 1 问题定义 集中式下行调度 , 旨在允许尽可能多的并发数据传 I EEE 802116 标准 Mesh 模式可以采用集中式 输 , 同时兼顾高效性和公平性. 调度和分布式调度 , 或两者的结合. 本文只考虑集 中式下行数据调度. 在集中式调度中 ,B S 根据网络 中所有 SS 的位置及其邻居集合信息建立集中式路 2 干扰避免树形路由 由树 , 收集树上 SS 的资源请求 , 做出带宽分配 , 并 ( 根据上面的干扰模型 , 定义给定节点 i 不包括 按照路由树确定的路由反馈给每个 SS ; SS 据此在 ) B S的干扰集为相应的数据子帧内收发数据 , 完成一个调度周期. p 与 Ad hoc 网络的对等拓扑结构不同 , 以下问题 i( ) ( ) = { C m | m = i 或 m ?N i , m ?p } ? I i i 的讨论都是基于一个无线 Mesh 网络中的所有节点 ( ) ( ){ n| n = p 或 n ?N p, n ?i , n ?0} 1 i i ( V 和部分链路 A 所构成的集中式路由树 T = V , 由此可定义节点 i 的干扰度为其干扰集的势 , 即 p p i i( ) ( ) = | I| = | { C m | m = i 或 m ?N i, m ?p } ?i i i i ) V 以非负整数标记 , 0 代表 B S , 1, N 代A . 节点( )) 2 ( { n | n = p或 n ?N p, n ?i , n ?0} | i i 表其他 N 个 SS , | V | = N + 1 ; A 代表 V 中每对由 它表征了由该节点拓扑邻接关系所造成的其与父节父节点指向子节点的无线连接. 不失一般性 , 以 SS . 点间链路对其他链路的干扰程度节点 i 为例 , 图 1 示出了树的一部分拓扑模型 , 包含 ( 在网络接入阶段 , 树上所有节点 初始时只有 ( ) ( ) 节点 i 及其邻居集合 N i 中的所有节点. N i 中 ) B S计算其不在树上邻居节点若加入后的所有可能 ( ) 包含 i 唯一的父节点 p , i 的子节点集合 C i 中的i ( ) 干扰度 初值为 0, 然后根据 n p ( ) 所有节点 c0 ?n ?M 以及其他节点.i j( )i = arg min 3 i j ( ) j ?/ T , p ?T , j ?N p j j 假定各节点的传输域与干扰域重合 , 如图 1 虚 决定加入节点. 其中 , 路由树集合 T 表示该次循环 线所示. 这里的干扰模型不同于基于 I EEE 802111之前已经加入到树上的节点集合; j 表示待加入节 协议的情况. 考虑下行链路 , 同一时隙内 , 如果父节 ( ) 点; p表示 j 的待定父节点. 式 3说明路由树建立 点 p 到子节点 i 间的链路上有数据传输 , 那么 pj i i ( ) 及其邻居节点 不包括 i 不能接收 , 而 i 及其邻居 过程中的节点加入顺序遵循干扰度最小的原则. 如 ( ) 节点 不包括 p不能发送. i 果节点 i 被选中在该次循环中加入 , 而有 2 个或 2 不同于局域网内任意节点间互为源目节点的模 p对应相等的最小干扰度值 , 那 个以上待定父节点i 式 , 图 1 中表示了节点 i 和 p以 bit / s 为单位的下 i 么 B S 按照 ( ) ( ) h 行业务请求 图中 0,4, x i 表示在第 w 帧内父w j p j( ) j hk i m+ i ( ) p = arg min 4 i i ( )? h j) k( j ?S 3 k = 1 35 第 4 期王英杰等 : 无线 Mesh 网络的最大并发公平调度 ( ) ( ) 从中为其选择父节点. 其中 , S 3表示满足式 3, 即要求剩下的所有最大并其他并发集包含的集合 的待定父节点集合 ; h为从 B S 到节点 j 的跳数 ;发集两两互不包含j p q ( ) hj 表示负责为节点 j 中继数据业务的第 k 跳节⁄ S S k m n ( ) 点. 式 4表明 , 选择父节点的依据是使从待加入节 kk 1 ?q ?C, 1 < m ?N , 1 < n ?N 1 ?p ?C, N N ( 点到 B S 整条链路上的干扰度之和最小 注意每次 ( )10 ) 循环后都要更新树上节点的干扰度. 如果仍有 2 然后 , 把这些最大并发集按照其势 k 从大到小排( ) 个或多于 2 个节点同时满足式 4, 再依据 列 , 并把没有在任何最大并发集中的节点单独构成 一个势为 1 的集 , 排在最大并发集序列之后. 排序 ( )p = arg min h5 i j( ) j ?S 4后的集合构成 r 个调度集 , 其中第 l 个势为 k 的调 ( ) ( ) 从中选取节点 i 的父节点. S 44 表示满足式 的度集可表示为 备选节点集合. 循环至所有节点加入树上为止. l 当节点在网络接入阶段后搜索到这个激活的无 = { i ,S , i } k 1 k k线 Mesh 网络并准备接入 , 或该网络中的任何 SS 节 )( , 1 ?k ?N , i ?V , 1 ?l ?C11 i , k N 1 点关机 , 都需要 B S 重建集中式路由树 , 并在上一个 给该节点分配的与其请求的数据速率之比 调度周期最后一个带宽请求机会后和下一个调度周 T t( )i y w 期第 1 个带宽分配机会前分发路由更新消息.? N N R lg M t = 1 S C C α= ?( )x i T / N w FrameMinislot3 最大并发公平调度t ( ) ( ) ( )y 12 x i > 0 , i ?0 , i , p ?V w w i 根据生成的干扰避免树计算每个节点的干扰 ( ) 式 12右边第 1 部分为本文定义参数 , 其中 , 若节点集 , 并定义兼容矩阵为 i 作为子节点的链路在第 w 帧内的 t 微时隙被激( ) ( )C = [ c m i , j ] , i , j ?V 6 tN ×N ( ) ( ) 活 , 则 y i 为 1 ; 反之为 0 . 式 12右边第 2 部分表 w 兼容矩阵 C 中的元素定义为 示由协议参数可得的每微时隙所支持数据速率 , 其pi 0 , j ?I i 中 , 每微时隙 O FDM 符号数 N , 每 O FDM 符号数S ( ) ( )c i , j = 7 1 , j = i N , 编码速率 R , 每子载波比特数据子载波数 C C 其他1 , lg M , 帧长T , 每帧微时隙数 N . Frame Minislot ( ) ( ) i 和节在式 7中 , 如果 c i , j 取值 0 表示以节点 分配带宽开始时 , 从 i = 1 开始在集合 V 中依 j 为子节点的 2 条链路互相干扰 ; 如果取值 1 则点 次查找第 1 个请求满意率最低的节点 z , 并从 k = 表示它们不在彼此的干扰域内 , 有可能在数据传输 1 、l = 1 开始在 r 个调度集中依次查找第 1 个包含 ( l时实现空间复用. 取兼容矩阵 C 的任意 k 行 i < 1 节点 z 的调度集 S ; 之后在 t = 1 微时隙为调度集 k ) ) ( i 位 < < i 和相同序号的 k 列 i < i < i < k l 2 k 1 2 中包含的所有节点分配带宽 , 即 S k 2 于这些行和列相交处的 k 个元素按原次序构成兼t = 1 l y ( ) ( )13 i = 1 , i ?S kw 容矩阵 C 的一个 k 阶子式 , 其对应的矩阵为 随即更新这些节点的请求满意率 , 重复上述分( ))( )( c i , i c i , i c c, i 1 1 1 2 1 k 配带宽开始后的步骤 , 直至 t = T .)))( ( ( c i , i c i , i c i , i 2 1 2 2 2 k l C= k 4 性能仿真 ( )( )( )c i , i c i , i c i , i k 1 k 2 k k 为说明本算法的有效性 , 在 O PN E T 仿真环境 k ×k k i < k ?N 下搭建了一个基于 I EEE 802116 标准的无线 Mesh ( )i ,, i ?V , 1 ?l ?C, 8 1 k N 网络动态仿真平台. 在正方形区域中依次布置 1 个 ( ) 如果式 8矩阵全部元素为 1 , 说明该矩阵所对应的B S 和 8,18 个 SS ,发射功率均为 21 dB m ,背景噪声 ( ) 原行 或列代表的 k 个节点作为子节点的 k 条链路 ( ) 为 - 103 dB m ,信干比 S IR门限值为 20 dB ,传播模 两两兼容 , 可以构成第 l 个势为 k 的并发集为 型为车载模型. 假定系统有效带宽为 20 M Hz ,帧长 l S 为 10 ms ,控制子帧中有 98 个 O FDM 符号 ,数据子 = { i , , i } k 1 k k 帧中有 631 个 O FDM 符号 ,仿真时间为 015 h . ( )i ,, i ?V , 1 ?l ?C, 1 < k ?N 9 1 k N k ( ) ( ) 对式 9列出的最多 N - 1C个并发集 , 去掉能被N 图 2 所示为 8 个 SS 情形下 ,应用本文提出的干内 B S 能较公平地满足各节点不同的带宽请求 , 实 ( 现了公平的下行调度.扰避 免 树 形 路 由 IA2TR , interference2aware t ree ) ( ro uting与 随 机 选 取 树 形 路 由 RS2TR , rando m2 ) selected t ree ro uting对节点干扰度影响的比较. 图 中 2 组数据的均值分别为 41125 和 51000 ,采用 IA2 TR 的平均节点干扰度减少 1715 %. 图 4 瞬时节点请求满意率 5 结束语 本文以链路间干扰的数学模型为出发点 ,通过 对干扰模型的理论寻求减小节点干扰度的集中 图 2 节点干扰度式路由树生成方法 ,以及运用对兼容矩阵的数学运 在均采用 IA2TR 的条件下 , 图 3 给出了对应算解决提高并发集利用率 、尽量保证节点请求满意 8,18 个 SS 不同场景 ,基于本文提出的最大并发公 率公平性的调度方法. 据此 ,提出了干扰避免树形 ( ) 平调度 MC2FS , maximal cliques f air scheduling、干 路由和最大并发公平调度问题. 性能仿真说明 ,本 5 文算法有效避免了树枝链路间的干扰 ,提升了并发 ( 扰 避 免 的 下 行 调 度IA2DS , interference2aware 传输对网络吞吐量的贡献 ,并保证了一定的公平性. ) dow nlink scheduling及无空间复用的基本下行调 5 () B2DS , basic dow nlink scheduling所对应的平 度 均网络吞吐量. 由图 3 可见 ,采用 MC2FS 可获得比 参考文献 :IA2DS 更大的相对于 B2DS 的网络吞吐量增益 ,且有 1 I EEE St d. 802 . 16 —2004 , I EEE standard for local and相对增益随节点数增多而缓慢增大的趋势. met ropolitan area net wor ks2part 16 : air interface for fixed broadband wireless access systems S . S. l . : I EEE Press , 2004 . 2 L ee M J , Zheng J , Ko Y2B , et al . Emerging standards for wireless mesh technology J . I EEE Wireless Co m 2 () mun Mag , 2006 , 13 2: 56263 . Nelso n R , Kleinrock L . Spatial TDMA : a collisio n2f ree 3 multi hop channel access p rotocol J . I EEE Transactio ns () o n Co mmun , 1985 , 33 9: 9342944 . 4 Salem N B , Hubaux J2P. A fair scheduling for wireless 图 3 平均网络吞吐量mesh net wor ks : 1st I EEE wor kshop o n wireless mesh 在 18 个 SS 的场景下 ,取 1 帧为样本 ,以上 3 种 ( ) 209202 . ht t p : ? 2005 2006 net wor ks EB/ OL . 下行调度算法所对应的瞬时节点请求满意率如图 4 www . cs. ucdavis. edu/ ,p rasant / wimesh.所示. 图中 3 组数据的均值分别为 01325 %、01182 45 % 5 Wei H2Y , Ganguly S , Izmailov R , et al . Interference2 和 01081 % , 标 准 偏 差 分 别 为 01254 、01351 和 aware I EEE 802116 WiMax mesh net wor ks C ?61st01254 . 可见 ,本文提出的 MC2FS 对应曲线以最小 I EEE Vehicular Technology Co nference. Stockholm 的标准偏差达到最大的均值 ,说明在 1 个调度周期 Sweden : I EEE Press , 2005 : 310223106 .