当前位置:首页 >> 电力/水利 >>

无线网状网容量分析与优化理论研究


ISSN 1000-9825, CODEN RUXUEW Journal of Software, Vol.19, No.3, March 2008, pp.687?701 DOI: 10.3724/SP.J.1001.2008.00687 ? 2008 by Journal of Software. All rights reserved.

E-mail:

jos@iscas.ac.cn http://www.jos.org.cn Tel/Fax: +86-10-62562563

无线网状网容量分析与优化理论研究
杨盘隆 1,2,3+, 陈贵海 1,2
1 2 3

?

(南京大学 计算机科学与技术系,江苏 南京

210093) 210093) 210007)

(南京大学 计算机软件新技术国家重点实验室,江苏 南京 (解放军理工大学 通信工程学院 电信工程系,江苏 南京

Research Paradigm of Capacity Analysis and Optimizing Theory on Wireless Mesh Network
YANG Pan-Long1,2,3+,
1 2 3

CHEN Gui-Hai1,2

(Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China) (State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China) (Department of Telecommunication, PLA University of Science and Technology, Nanjing 210007, China)

+ Corresponding author: Phn: +86-25-84607181, Fax: +86-25-84607181, E-mail: plyang@computer.org

Yang PL, Chen GH. Research paradigm of capacity analysis and optimizing theory on wireless mesh network. Journal of Software, 2008,19(3):687?701. http://www.jos.org.cn/1000-9825/19/687.htm Abstract: This paper firstly analyzes the technical difficulties in capacity estimation and optimization theory on

wireless mesh network, and summarize the prospects in it. Based on the existing work in this area, a brief introduction to interference model and schedule model of capacity analysis problem is proposed. An optimization model is proposed based on the two models mentioned above. This paper reviews the mathematical models in capacity analysis, including programming model, information model, combinatorial optimization models and stochastic model. Evaluation metrics of capacity analysis model is proposed, and different models are evaluated by using this rule. At the end of this paper, future works of capacity analysis and optimization theory are introduced. Key words: wireless mesh network; NPC problem; capacity analysis theory; linear programming; approximation algorithm 摘 要: 首先对网状网容量估计与优化理论的技术难点进行分析,总结了其中的研究意义.根据国内外的研究现

状,对干扰模型和调度模型进行总结与归纳,并对典型的优化模型进行了介绍.对目前容量优化算法常用的数学模型 ——规划模型、信息论模型、组合优化和随机过程模型进行了总结,提出了算法评价准则,对现有模型进行了点评. 最后对未来的发展趋势提出了自己的观点. 关键词: 无线网状网;NP 完全问题;容量估计理论;线性规划;近似算法 文献标识码: A 中图法分类号: TP393

?

Supported by the National Basic Research Program of China under Grant No.2006CB303004 (国家重点基础研究发展计划(973));

the National Natural Science Foundation of China under Grant Nos.60673154, 60573131 (国家自然科学基金); the Natural Science Foundation of Jiangsu Province of China under Grant No.BK2005411 (江苏省自然科学基金); the Jiangsu High-Tech Research Project of China under Grant No.BG2007391 (江苏省高技术研究计划) Received 2007-05-27; Accepted 2007-08-16

688

Journal of Software 软件学报 Vol.19, No.3, March 2008

自从 Shannon 创立信息论以来,无线信道容量估计就成为无线通信系统发展的基础性课题之一.近年来,随 着无线网新技术的演进,分布式、自组织网络技术得到了迅猛的发展,研究的重点开始由无线信道容量估计向 网络容量估计转移.容量估计理论对于提高网络效率、增强网络业务保障能力具有重要的理论价值.由于无线 网状网采用了灵活的组网手段与先进的无线通信技术,正确的容量估计算法能够确保异构网融合效率,增强网 络的可扩展性.但无线自组织网中众多不确定的因素增加了问题的复杂度:一方面,无线网信道属于竞争信道, 移动节点拓扑动态性较强,个别节点位置的变化可能会极大地影响网络容量;另一方面,分布式环境下节点之间 协同计算行为比较复杂,使无线自组织环境下网络容量估计理论遇到了前所未有的挑战. 无线网状网(wireless mesh network)技术不但具有明显的分布式自组织特征,还可以利用多种通信手段如 IEEE 802.11,WiMax,ZigBee 等技术,被认为是一种有效的异构互联网络技术.其中,关于无线网状网容量估计的 理论研究是基础性课题,与上述几个方面问题的研究重点密切相关.但是,相对于无线自组织网络而言,无线网 状网容量估计理论的难度更大、挑战性更强.总结起来,主要体现在以下 3 个方面: (1) 网络基础结构复杂.无线网状网的基础结构相对复杂,从家庭网络设备的宽带互联到社区之间的资源 共享;从企业内部的高效自组到边远乡村的经济性接入,无线网状网不同的应用背景直接影响网络的配置.除此 之外,新兴无线网(如传感网、移动自组网、卫星网等)和传统因特网融合,也依赖于无线网状网技术,异构网络的 引入增加了网络的复杂性.上述结构特点直接影响了网络配置和工作方式.无线自组织网现有的容量估计理论 模型和实用成果具有一定的可借鉴性,但是由于网状网技术发展迅速,现有的研究成果无法满足无线网状网的 研究要求. (2) 协议复杂.无线网状网的另一个特点是协议较为复杂.由于在物理层采用了 MIMO 和 OFDM 等多信道 技术,传统的单信道 MAC 协议不适用,需要多信道技术的接入算法.目前,算法仍有许多问题亟需解决,如多信道 条件下的隐终端问题、 多信道切换的时延不确定性以及报文失序问题[1].网状网路由算法也更加复杂,不再采取 单一路径选择的策略,而是通过多径路由(multi-path routing)实现负载均衡.另外,为了适应不同的应用需求,路 由协议采用不同的性能指标(routing metric),不再简单地计算源节点到目的节点的跳数(hop count)[2,3].因此,总 体上看,无线网状网协议复杂度远远高于一般无线自组织网协议. (3) 影响网络效率的因素多.在无线自组织网中,流量、拓扑、移动性是影响网络效率的 3 个重要因素.但是 在无线网状网中,除了上述不确定因素之外,还包括了许多重要的网络配置,如天线数目、信道数目、切换效率 及网络切换的优先原则,跨层设计与网络编码技术的引入也使网络效率有所提升.从应用场景的角度来看,用于 数据采集环境的网关需要以节能、高效的数据收发为目标;用于无线传感环境还要考虑节能,而作为个域网或 者家庭网关互联,关注的是公平性、经济性和便捷性.这些因素直接影响容量估计理论的优化目标,由于网络效 率不再仅仅以系统(总)吞吐量作为单一的衡量指标,传统的容量估计模型已不能适用于各种类型的应用场景. 综上所述,无线网状网容量估计技术具有重要的理论意义和实用价值,但是存在着许多前所未有的困难,面 临着较大的挑战,需要对其进行较为深入的理论分析,剖析技术难点,总结出行之有效的分析方法.本文试图通 过对研究进展的总结,使更多的研究人员关注网状网容量理论,同时,更加迅速地把握问题的本质,提出创新性 见解,实现理论突破. 本文第 1 节论述无线网状网容量估计理论研究的意义.第 2 节对目前的研究现状进行介绍,重点介绍几种 经典的建模方法与问题求解手段.第 3 节对主要研究内容进行详细的分析与比较,从规划模型、信息论模型、 组合优化理论和随机过程模型几个方面对不同的研究方法进行总结与分析,对不同类型的算法结合评价指标 进行横向比较.第 4 节提出亟需解决的问题及未来的研究重点内容.最后是工作总结.

1

研究意义

1.1 优化链路-信道调度策略 由于无线信道是共享信道,节点之间的通信存在着竞争,因此,研究无线网状网的最大容量问题,必然需要 优化链路-信道调度策略.由于无线网状网具有灵活的组网功能,多接口-多信道、流量均衡和路由指标(routing

杨盘隆 等:无线网状网容量分析与优化理论研究

689

metric)灵活多变等因素影响“链路-信道”调度策略,仅仅依靠仿真已经很难完成吞吐量优化的工作.一方面,仿真 环境局限性大,仿真结果受无线环境多元因素影响,无法得到渐近容量的结论;另一方面,在没有链路-信道调度 优化算法之前,很难通过仿真得到网络的最大容量.而容量估计理论的研究可以很方便地对渐近容量问题进行 讨论,并通过网络规划与约束条件模型(详情见第 2 节、 3 节)实现调度策略的最优化,因此,可以从理论上根本 第 解决问题. 1.2 优化数据分发与收集策略 针对功率可调、数据产生率已知的网络,如何确定一个最优广播树?如何确定一个最优数据收集树?结合容 忍技术中的存储与转发策略,最优广播树和最优数据收集树是否会发生变化?这都是容量估计理论需要研究的 问题.如果从节省能量和存储空间的角度考虑,还需要优化无线网状资源利用率.文献[4]提出了具有时间容忍和 差错容忍的移动传感节点的收集策略,对缓存策略和数据转发策略进行了详细的讨论,但是并没有考虑数据的 时效性和接入节点效率问题.所提出的方法,一种是以投递概率为依据;另一种是以消息跳数为依据,并以此为 优化目标,提出队列管理与广播优化算法.对数据收集与分发算法研究的重点是资源与网络利用率二者之间的 影响,寻找平衡上述目标的结合点,提高数据传递效率和网络资源利用率. 1.3 网关部署及移动管理 容量估计理论成果能够推动数据分发与收集策略的研究:一方面,容量估计理论有助于进行高效的资源调 度,适合用于可靠性、连通性较差的传感网络;另一方面,信息调度与转发策略可以根据网络容量状况进行调整, 必要时可以采用多个网关对网络区域进行覆盖优化,提高了接入的健壮性和可靠性. 由于不同的网络节点出于应用场景的需要,采取不同的调度策略和移动方式,导致网络中的数据分布与节 点工作状态差异较大.如果网状网协议能够具有较强的预测能力和历史数据分析能力,则可以为网关部署策略 和移动策略提供有效的支持.容量估计理论可以通过数据进行有效的分析,排除干扰,提供高效并且可行的网关 部署和移动策略. 1.4 可扩展性问题研究 与无线通信理论相比,Shannon 公式虽然给出了信道的容量极限模型,但是对于分布式系统,由于影响因素 较多,单一地讨论渐近容量往往局限于个别因素导致结论过于理论化,或过分强调某一方面的性能指标而导致 实用性不强.基于容量估计理论的可扩展性问题研究能够有效地克服上述局限性:一方面能够依据现有成果,对 理论模型进行修改;另一方面,模型对于讨论渐近性问题,尤其是网络规模等因素趋近于无穷的情况,可以很方 便地与现有容量估计理论研究方法相结合(如图 1 所示).
Capacity estimation Static analysis Scheduling and E2E throughput Traffic analysis Data collection and dissemination Traffic and topo dynamic analysis Placement
or act X-F

Traffic and topology

History behavior analysis and prediction Mobility management

Mobility

y ilit lab Sca

Fig.1

Research field of capacity estimation theory in wireless mesh network 图1 无线网状网容量估计理论所覆盖的研究领域

690

Journal of Software 软件学报 Vol.19, No.3, March 2008

2

研究现状
许多研究人员根据无线自组织网网络参数对网络性能的影响、对分布式无线网络环境的容量估计理论展

开了研究.其中,具有代表性的是 Gupta 和 Kumar[5] 所提出的多跳无线网“逼近容量或渐近容量(asymptotic capacity)”问题.所谓渐近容量是一种理想情况,即节点数目趋于无穷的极限模型.由于无线信道具有广播特性, 需要对节点之间的干扰行为建模,文献[5]建立了两个实用模型:(1) 协议层干扰模型(PrIM-protocol interference model);(2) 物理层干扰模型(PhIM-physical interference model).目前,绝大多数关于网络容量估计或优化的文章 都建立在上述两个模型的基础上.文献[6]在考虑了多跳无线网路由转发对无线网容量的影响后,指出渐近容量 为 O(logn).文献[7]对多信道多天线(multi-channel and multi-radio 简称 MC-MR)问题进行了讨论;文献[8]将 MESH 网络优化问题归结为物流问题(multi-commodity flow)和最大并行流问题(maximum multi-concurrent flow),提出用规划模型求解.利用“原始-对偶”问题的特性,首先将整数规划问题退化为普通线性规划问题,将约 束条件进行了一定程度的松驰,由充分必要性转化为必要性问题的研究.再将原始线性规划问题求解转化为对 偶问题的求解,得到了网状网容量的上界.文献[9]也根据组合优化理论、链路随机分配策略和节点分布得到容 量上限.上述成果对于 MESH 网络容量问题的研究有一定的借鉴意义.本文希望通过对现有容量估计理论研究 意义及现状的介绍,能够了解最新的技术进展,全面分析并比较现有研究的不足,进而寻求理论上的突破(如图 2 所示).
Other factors multi-path energy-saving crosslayering App. and cross layer

Capacity optimization

Network/APP

Scheduling model

MAC/Network

Interference model

PHY/MAC

Fig.2

Layered model for capapcity estimation in wireless mesh network 图2 网状网容量理论研究的层次化模型

我们借用网络层次的概念对容量估计理论进行介绍.从网络层次的概念来看,网络干扰模型要考虑到无线 信道属于物理层和媒体接入层(MAC);调度模型属于接入层,而由于跨层技术或流量公平性等因素的影响,模型 也会受到应用层的影响;容量优化一般从网络层来考虑优化,并以调度模型和干扰模型为基础;如果考虑其他因 素如节能设计、跨层设计等,则需要根据应用目标建立优化模型,因此属于应用层的范畴. 2.1 干扰模型 无线网络的干扰主要来自两个方面:一是信号干扰;二是数据干扰.信号干扰是由于无线信道本身不稳定性 和传输距离的限制导致无法接收数据;数据干扰是由于无线信道的广播特性导致的数据碰撞.目前,容量分析模 型中的干扰模型主要考虑数据干扰. 干扰模型中,一般用无向图表示双向信道,有向图表示单向信道,也有的模型采用双向的有向图表示双向信 道,以保证模型的通用性.由于无线网状网的数据干扰模型与无线信道技术(MIMO,OFDM)、无线网接入协议 (CSMA,MACA)等技术密切相关,因此,采用不同技术体制的接入协议,其干扰模型亦不相同. 目前,绝大多数文献按照 3 种类型的干扰模型来讨论分布式环境下的网络容量问题,分别是发送模型 (Tx-model)、协议模型(protocol-model)和发送接收(Tx-Rx)模型[9](如图 3 所示).

杨盘隆 等:无线网状网容量分析与优化理论研究

691

Range(u)

Range(w) u v w u1 e1 v1

No less than two hops (1+?) d(u,v) ……… u2 e2 v2

w u (1+?) ( Range(u)+Range(w))

Fig.3 图3

Interference model, from left to right, TxM, PrIM and Tx-Rx model

干扰模型示意图,从左至右分别是发送模型、协议模型和发送接收模型

(a) 发送模型(Tx-model) 在发送模型中,节点 u 能够成功地向节点 v 发送数据的充分必要条件是:所有需要发送数据的节点 w 都满 足式(1)的条件.其中,d(u,w)表示节点 u 和节点 w 之间的距离,?≥0 表示容差,rang(u)表示节点 u 的接收半径. d(u,w)≥(1+?)?(rang(u)+rang(w)) (1) 模型的优点在于:(1) 与目前 CSMA 方式较为接近;(2) 由于不存在 RTS/CTS 模型中“暴露终端”问题,分析 结论较为接近理论上界.但是模型的缺点在于,要求感知距离大于发送距离,需要采用功率控制的方式对发送距 离和感知距离进行调整,以适应模型的约束条件,即 d(u,w)≥(1+?)?(rang(u)+rangmax(wi)) 当 rangmax(wi)>>rang(u)时,天线感知距离在设计工艺上可能难以达到要求,此时,模型约束条件不成立. (b) 协议模型(protocol model) 协议模型从数据接收方角度考虑无干扰的充要条件.当节点 u 需要向节点 v 发送数据时,节点 v 能够成功接 收数据的充分必要条件是:(1) 节点 v 在节点 u 的传输范围之内,即 d(u,v)≤Rang(u);(2) 所有数据发送节点 w 都 满足 d(w,v)≥(1+?)?d(u,v). 从充分必要条件来看,协议模型要求节点能够按照距离远近对数据包进行区分,消除噪声的影响.但是对无 线通信系统而言,协议模型属于理想模型,在实际系统中较难实现.另外,协议模型不适用于具有功率控制功能 的网络,当节点的通信半径不同时,协议的充要条件不成立,协议模型的通用性不强. (c) 发送-接收模型(Tx-Rx model) 发送-接收模型没有像前两个模型那样明确发送节点或接收节点,令 e1=(u,v)表示一条边并且产生了一次数 据发送过程(并不明确区分节点 u 和节点 v 谁是发送节点,谁是接收节点),模型无冲突数据发送的充要条件是 D(e1,e2)≥2 (3) 其中,D(e1,e2)是指两条边 e1 和 e2 之间任意两点之间的最小跳数.发送-接收模型对应于 CSMA/CA 协议,可以适 用于节点发送 RTS/CTS 的情况.发送-接收模型最接近实用情况,同时也适用于基于竞争的信道协议.但是在 TDMA 体制中,由于时隙长度是相同的,而 RTS/CTS 属于短帧,将会直接导致 TDMA 的接入效率大幅度降低.发 送接收模型的缺点是 CSMA/CA 协议依靠 RTS 和 CTS 报文的交互,导致暴露终端的节点不仅不允许发送数据, 而且不能接收数据,模型与实际理想容量上界之间存在偏差. (d) 针对多信道多接口的扩展 对于多信道多接口的扩展模型,其本质上依然以发送-接收模型为基础.文献[8]提出了一种解决方案,对其 进行了进一步的约束: (1) 不能超过最大的无线接口数目,此约束对应于式(4); (2) 不能超过最多的信道数目,此约束对应于式(5); (3) 不能超过每个信道所能承受的最大带宽,此约束对应于式(6).
i∈OC

(2)

∑ gi (e) ≤ ρ (e), ?e ∈ E

(4)

e∈E ( v ) i∈OC

∑ ∑ gi (e) ≤ κ (v), ?v ∈ V

(5)

692

Journal of Software 软件学报 Vol.19, No.3, March 2008

∑ g (e) ≤ 1, ?i ∈ OC , ?e ∈ E ∪ Eτ
e∈

(6)

2.2 调度策略 即使不考虑干扰带来的影响 , 调度策略都属于 NP 完全问题 [10] . 文献 [11] 考虑了干扰的问题 , 提出了基于

CSMA/CA 的调度算法 ,目的是单信道条件下的网络容量 .文献 [6,10,12]对节点的布局作出了要求 ,因此 ,模型的
适应性强 ,对于方向性天线的支持、非对称链路等情况 ,模型依然适用 .文献 [10,13,14]都采用了路由负载均衡的 评价标准 ,并应用于多信道多天线模型 .其中,文献 [10,13]提出了分布式和集中式算法 ,但是都没有考虑链路冲突 调度和最优化问题 .文献 [14]没有假设流量已知 ,目的是为了更加逼近理论上界 .文献 [8]提出了 α因子的概念 ,也 称为α-竞争的调度算法(α-competitive scheduling algorithm).主要思想是某种调度方案 ?的获得吞吐量 q(?)和 最优吞吐量 q*的比值 .文献证明了在发送干扰模型下 ,竞争因子 α≥0.2.文献 [9]用地理几何学的原理得出了若干 推 论 , 引 入 了 距 离 因 子 αd, 并 且 对 干 扰 集 合 的 比 例 因 子 Cα d 进 行 估 计 , 得 到 了 其 与 距 离 因 子 αd 的 关 系 服 从
Cα d ≤ (6α d + 1) 2 + 11 .

但是在无线网状网中 ,由于天线之间采用了多信道多接口 (MC-MR)的设计 ,上述竞争干扰集的约束条件与 容量限制都以单一信道为假设 ,并结合各种不同的干扰模型 .由于网状网中的天线可能具有时间空间复用功能 , 因 此 不 能 简 单 地 认 为 是 多 个 无 线 信 道 和 无 线 接 口 的 简 单 叠 加 . 通 常 采 用 的 方 法 有 无 线 接 口 分 配 法 (radio

interface assignment)和链路分配法 (link assignment)两种 .文献 [8]认为链路分配难度更大 ,但是考虑接口链路切
换的无线接口链路算法也是应该考虑的 ,否则 ,对于优化 MESH 容量研究不利 .但在有些应用场景下 ,需要考虑 链路分配算法. 文献 [8,13]将不同信道的链路在一个链路集合中考虑 ,但是 ,这种方法没有考虑天线之间的切换开销和路由 选择等多方面的因素 . 文献 [7] 证明了如果考虑天线切换带来的开销 , 则会对容量估计的结论产生影响 . 同时 , 如 果考虑实用化的模型 ,不同无线信道的带宽不同 ,如果仅仅考虑竞争调度的效率而忽视节点实际可获得带宽 , 则 会导致调度算法不能按照无线信道的优先级进行选路 ,影响网络效率 .无线网状网中应该如何对调度算法效率 进行评估并得到更实用的调度算法 ,现有结论如何在无线网状网环境中进行改进 , 都值得我们有针对性地进行 研究. 上述算法有些是针对无线自组织网容量进行了理论研究 , 但是由于无线网状网的特殊性 ,并不能作为已有 成果直接应用于容量估计理论的研究,但是可以积极借鉴已有的研究方法. 作为无线网状网的调度算法可以分为触发层面、 执行层面和网络环境层面 3 个层次来进行考虑.触发层面 决定了算法执行的时机 , 一般分为静态算法和动态算法 .如果网络调度算法对于任何网络流和网络资源分配状 态都采用同样的计算策略 ,则称为静态算法 (static algorithm);如果调度算法对于不同的网络状态采用不同的计 算策略,则称为动态算法(dynamic algorithm)(如图 4 所示). 执行层面决定了算法计算执行的方式 ,通常可以分为分布式算法与集中式算法 .集中式算法由于已知所有 的网络输入参数,可以得到全局最优解或全局最优近似解(对于 NP 难题一类问题).文献 [7]提出了一种更加实用 的模式 ,即随机式执行方式 .随机方式介于分布式与集中式之间 ,即不假设所有的调度策略都需要根据集中式算 法 ,也没有假设分布式计算环境 ,要求各个节点之间完全独立 .通过随机分配将各个节点之间的调度策略联系起 来 . 随机分配方式与集中式的区别在于不需要全局信息 , 同时 , 不需要集中式的计算与优化 ; 与分布式的区别在 于随机分配方式并不试图像分布式算法那样寻求局部最优 . 文献 [7]还讨论了一种基于连续频带之间按照固定 顺序分配的模式 (adjacent channel assignment). 从实用角度来看 , 随机调度算法实现较为简单 , 具有相对可扩展 性 .同时 ,随机调度算法还给出了信道数目与接口数目及网络带宽之间的关系式以及网络容量的下界 ,具有积极 的理论意义. 网络环境层面决定了算法的节点流量、拓扑和移动方式等因素 .现有算法在考虑链路 - 信道调度与吞吐量 优化时,往往采用两种网络约束条件:(1) 约定式网络约束(arbitrary network model):约定式约束指定网络拓扑形 态 和 流 量 形 态 , 有的 模型 还 对节 点 之间 的 数 据 交 互 特 点 进 行 了 约 束 ;(2) 随 机 式 网 络 约 束 (random network

杨盘隆 等:无线网状网容量分析与优化理论研究

693

model):随机式网络约束与约定式恰恰相反 ,并不限定网络拓扑和网络的流量形态 .其中 ,约定式约束可以根据特
定的网络拓扑和流量形态提出链路调度算法 , 得到较高的吞吐量 . 但是 , 约定式环境的适应性较差 , 一旦流量或 拓扑形态发生变化 ,调度算法需要根据已知的网络环境参数进行调整 ,本质上是一种需要动态调整的集中式算 法 .随机式约束不依赖具体的网络环境 ,也不需要根据网络环境参数的变化进行调整 ,本质上是一种静态分布式 算法.
Arbitray Arbitrary and random Random

Network environment layer

Centralized

Random

Distributed

Schedule layer

Dynamic

Static

Triggered layer

Fig.4

Layering structure of scheduling algorithm
图4 调度算法分解层次示意

为了克服约定式网络约束与随机式网络约束的局限性 , 文献 [7,9]提出了随机指定式网络环境 , 介于指定式 和随机式之间 ,目的是根据研究目标的需要对部分网络参数进行约束 ,而将另外部分参数设置为随机式约束 , 常 常用于定量地对某一因素对网络容量或对网络可扩展性的影响. 2.3 典型的优化模型介绍与分析 典型优化模型的侧重点各不相同 ,可以按照研究目的的不同加以区别 :一类是由于应用场景目标不同 ,导致 优化模型的目标发生改变 ,典型的是以最大流量为目标的最大并行流问题和网络流量公平性问题 ;另一类是受 到网状网协议的影响 ,典型的是多径路由条件下网络容量研究和网络编码对量的影响 ; 还有一类是出于理论分 析的需要,保证理论成果的前瞻性和完备性,典型的模型是稳定性理论和协议干扰无关集算法的研究.上述 3 种 类型与模型之间的关系如图 5 所示.
Traditional optimize model

Goal of application scenario

Impact of key technology

Requirements of theory analysis

MCFP

FAIRNESS

Multi-Path

Network coding

Stability

Maximum independent set

Fig.5

Basic classification on typical optimum model
图5 典型优化模型基本分类

694

Journal of Software 软件学报 Vol.19, No.3, March 2008

(a) 最大并行流问题
网络最大流问题(maximum flow problem,简称 MFP)和多最大流问题(multiple maximum flow problem,简称

MMFP)都存在最优多项式时间算法[15],而最大并行流问题(maximum concurrent flow problem,简称 MCFP)却属
于 NP 完全问题[16].二者的区别在于,MMFP 仅仅规定了源点集合 S 和 T,而 MCFP 规定了 “源点 ?目的点”的集 合偶对 P={?si,ti?|i∈[1,…,m]},并且每个源点都有一定的流量需求 di. 采用网络最大并行流问题求解,而非网络最大流问题解决容量估计问题 ,其主要原因是 :MCFP 更加符合网 络的真实情况 ,端到端行为是网络中最常见也是最有效的手段 ;而最大流问题得到的是网络容量 ,但是没有考虑 节点之间的流量需求 ,很难应用于实际网络 .其缺点是不能得到最大网络容量 ,只能算是在一种特定约束条件下 网络容量的最大估计算法. 显然,MCFP 问题难度大于 MFP.同时,MCFP 问题还可以兼顾公平性,巧妙地将公平性用公式(7)表示,通过 在原问题上保证了 MCFP 求解的公平性.

?i∈C,?j∈C\{i},ri≥λrj
其中, λ =

(7)

min i ri . max i ri

文献[8]考虑了 TDMA 网络中的无干扰流量调度问题,对 TDMA 信道竞争机制进行了数学描述,采用

?1, 在时隙t , 信道i在链路e上有数据发送 yit (e) = ? . ?0, 其他
由于文献 [8]讨论的是基于时隙分配的网络 ,时隙资源的分配具有周期性 ,并且将 yit (e) 整数替换成了 gi(e), 问 题由 整 数 规 划 变换 成 了 线 性 规划 问 题 . 为此 , 文献 [8] 还特意讨论了 ILP 和 LP 关于最优值之间的差距

(optimality gap)问题 ,并对产生的影响进行了分析 .但是 ,由必要条件得到的结论再作为上界 ,并且把求解到的结
果在充分必要条件的约束下得到问题的一个下界 .同时 ,文章还对约束条件进行了等价变换 ,分别对集中式算法 和分布式算法进行了分析与讨论.

(b) 考虑公平性的问题
为了克服单纯获得最大网络吞吐量 ,文献 [17]提出了一种 Max-min 公平模型 .问题背景来自于接入点 AP 对来自于不同节点数据流量的分配策略.称一个流量分配策略 f = { f1 , f 2 ,..., fi ,..., f n ?1 , f n } 为 Max-min 公平的,当 且仅当对分配策略中任意的一个元素 fi,如果有另外一种分配方式使得 yi>fi;那么,必然存在 fj<fi 并且 yj<fj.换言 之,流量分配策略 f 保证了所有分配的网络流量中最小的元素 fmin 取得最大值. 文献 [17] 中的模型通过计算瓶颈带宽来确定最大可获得的流量 , 并将瓶颈容量进行平均分配 . 通过迭代实 现,每一步都对剩余可用网络容量进行计算,直至网络中没有可用的剩余容量为止. 具体的计算公式为
Capd = min
s∈C

∑ e∈d ∑ f ∈F Af ,e
前可用容量.

∑ e∈s ∑ f ∈F Af ,e

Caps

,

其中,Af,e=1 表示流量 f 流经边 e,否则为 0;Capd 表示竞争集(collision set)上的剩余可用容量;Caps 表示网络流当 但是 ,文献 [17]所提出的算法是一种启发式算法 ,并没有给出严格的证明 .同时是一种静态算法 ,对于网络流 量和拓扑动态变化的情况而言 , 很难利用公式进行计算 , 所以不能称其为一个完整的公平性模型 . 另外 , 算法没 有对分配策略 Af,e 进行优化.但是从计算公式可以看出,分配策略对结果的影响较大,一方面影响可用容量,另一 方面影响竞争集.如果得到的不是寻求最大剩余容量,那么公平算法的意义将大打折扣.

(c) 多径路由效应
无线网状网采用多径路由技术主要出于以下几个方面的原因 : ① 减小干扰 ; ② 节约能量 ; ③ 充分利用网 状网通信组网手段的多样性 , 减小时延 ;④ 提高无线资源利用率 ,降低成本 .多径路由协议会对容量模型产生影 响 : 首先 , 在网络拓扑上 , 多径路由一般由互不相交的路径组成 (disjoint route), 不同路径上的数据之间没有干扰

杨盘隆 等:无线网状网容量分析与优化理论研究

695

(如果路径上的节点满足干扰模型的约束条件 ),因此 ,干扰集的规模将大为减少 .多个并行流同时传输时 ,需要考
虑多径路由间的最小无关集问题 ;另一方面 ,由于源节点与目的节点之间采用多个路径同时进行数据传输 ,无线 网状网所支持的源 - 目的节点对 ?si,ti? 的数目会有所减少 , 但是传输效率相对较高 . 因此 , 无论是多径路由协议网 络的最大流量还是最大并行流量问题都是值得关注的问题 . 文献 [18] 提出了基于网络编码和数据扩散 (data

diffusion)的多径路由协议 ,为容量估计算法研究提供了新思路 .多径路由还能有效地减小报文的时延 ,在时延限
制的网络中(time bounded network),如何在时延约束下达到系统最大容量,也是值得关注的问题.

(d) 网络编码(network coding)技术带来的影响
如图 6 所示,节点 S 向网络中的节点 D 和节点 E 广播数据 X 和数据 Y,节点 A,B 和 C 都与节点 S 一跳可达. 假设转发节点为 A 和 B,当节点 S 先后向两个节点发送 X 和 Y 后,图 6 中的节点 C 也先后收到了这两个数据,如 果节点 C 向节点 D 和节点 E 发送数据 X 异或 Y,则 A 无须向 D 再发送数据 Y,B 也不需要发送数据 X 到节点 E.
A D

X

S
Y

X(1) Y(2)

C

X XOR Y E

B

Fig.6

Impact of XOR network coding on transmission optimization mechanism
图6

XOR 网络编码对优化传输策略的影响

文献 [19]针对网络编码对容量模型的改进算法进行了分析,对于二维 (2D)情形,增益因子为 α (n) = 示由于引入网络编码获得的吞吐量增益 . α (n) ≤ 2c? π
1+ ?

λC ( n) ,表 λF ( n)

?

, 其中 , c? = max{2, ? 2 + 2? } , ? 是无线网的竞争参

数,表示无线信道共享及冲突程度.同时还考虑了 1D,2D 和 3D 直至 K-D 的情形.根据文献[19]所得到的结论,采 用网络编码技术后,对于广播业务而言,吞吐量增益仍然在常数 c 之内,不会有本质性的提高. 文献 [18,20]利用 Fountain 编码提高了网络数据分发的容错性能 .编码冗余能够提高网络存储效率与传输 效率 ,为模型进一步应用于实用无线系统打下了良好的基础 .文献 [21]将网络编码与机会路由相结合 , 提出了实 用化的网络编码与优化传输模型.作为进一步的研究成果,文献[22]对物理层级别的网络编码效应进行了研究.

(e) 稳定性理论
文献[23,24]从稳定性理论角度对问题进行了分析,但分析角度有所不同. 文献 [23] 主要从资源分配角度考虑稳定性问题 , 考虑时间趋于无穷时 , 链路占用率与数据缓冲区和时延的 X 关系,并给出了稳定调度策略的充要条件,即 t ′ → ∞, x(e) = ∑ t ≤t ′ e,t ′ 是稳定的当且仅当: t (1) 确定的时延;

(2) 缓冲区有界.
文献[24]主要是从算法收敛角度对模型稳定性进行了讨论,对迭代函数进行了分析,优化目标 V(K)(x)是迭代 函数 x*(k).有如下关系:
? ?V ( k ) ( x) ? d (k ) V ( x(t )) = ?α ? ? . dt ? ?xl ?
2

x*( k ) = arg min V ( K ) ( x) ,并且
x ≥0

因此得出结论,优化目标 V(K)(x)是迭代函数 x*(k)的李雅普诺夫函数,极值点就是稳定点.

696

Journal of Software 软件学报 Vol.19, No.3, March 2008

(f) 无关集算法
文献 [9]根据着色问题和组合优化理论提出了集中式算法与分布式算法 . 文章还根据流量特征提出了基于 流量权重的改进算法,提高了吞吐率,对节点之间的干扰和冲突条件进行了分析与讨论. 但是 ,由于网状网是一个 “多信道 -多接口 ”网络 ,无关集模型还需要结合信道匹配优化算法以提高网状网吞 吐率 .现有的分布式算法一般以算法求解效率和算法复杂性为衡量指标 ,但是没有考虑节点之间通过迭代达到 协同的过程 , 特别是在多跳情况下就更加复杂 . 算法收敛性也是无线网状网容量估计理论 , 特别是分布式环境 下,需要重点考虑的问题. 无线网状网可以充分借鉴目前无关集算法取得的成果 , 同时考虑无线网的特殊性 ,其中最重要的是干扰模 型中的结论 , 尤其是对干扰因子的讨论 , 特别依赖于节点之间的位置与流量关系 . 属于过于理想的模型 , 与实际 应用还有一定的距离.

3

主要研究手段介绍与分析比较

3.1 主要研究手段

3.1.1

规划模型 文献[8,17,23]不同程度地归结为规划问题,优化目标从网络流量、公平性、并行吞吐量到网络资源利用率,

种类繁多 .虽然最大生存时间问题与容量问题存在较大差异 ,但其本质上是一种网络资源的优化 ,特别需要对网 络时隙资源、转发节点等问题进行优化处理 ,这些方面的问题也是容量估计算法所关注的 .文献 [8]利用线性规 划中的对偶理论对原始问题进行转化 . 文献 [23] 将传感网最大生存时间问题转化为非线性规划问题 , 并通过分 布式信息交互完成迭代计算,最后利用稳定性理论,对算法的敛散性进行讨论. 通常,通过对问题的建模性可以发现,无线网中的容量优化问题均属于 NP 难题,利用近似算法求解是一种 高效、实用的方法(如图 7 所示).

Object

Max (Min)

{

Traffic Fairness Concurrent throughput Life time Timeslot and forwarder

Conversion

Constraints

s.t

{

Interference Number of channels Switch delay Multi-Path routing Redundancy

Fig.7

Programming model of capacity estimation algorithm
图7 规划模型在容量估计算法中应用

3.1.2

信息论模型 网络编码技术属于信息论范畴 ,直接影响网络的运行方式与组织模式 , 所以需要单独对网络编码技术进行

讨论.文献[20]充分利用了 Fountain 编码的优势,提供了更强的容错性(fault tolerance).虽然文献的主要目标是在 传感网随机分布和移动的状态下 ,利用编码冗余提高网络存储效率 ,但是 ,对于无线网状网而言仍然具有实用意 义 : 一方面 , 目前容量模型都没有考虑网络通信中的差错 , 实际中的无线网络都具有一定的差错率 , 考虑容错因

杨盘隆 等:无线网状网容量分析与优化理论研究

697

素的模型显然更接近实用 ; 另一方面 , 可以利用分布式存储策略和时延容忍技术 (delay tolerant network, 简称

DTN),优化网络流量的分配策略,提高网络吞吐量.
文献[18]采用较低复杂度的线性码 Fountain Code(复杂度为 O(klnk)),结合随机移动模型(random walk)对网 络数据的容错存储策略进行了分析 , 并提出了优化算法 . 文献 [20]从网络增益的角度来考虑这个问题 , 指出网络 编码所获得的吞吐量增益为常数.在一般意义下,对于长度为 n 的数据段,经过编码后,冗余系数为 r.显然,r>1,则 有 m=n×r.对于编码后的数据段,目的节点只要成功接收到 m 中任意 n 个即可以正确接收数据.因此,网络吞吐量 的计算方式有所改变 , 网络编码赋予数据更多的含义 , 也会影响规划模型中的约束条件 . 同时 , 网络中数据冗余 也会给网络效率带来影响,如果结合多径路由选择,基于网络编码技术的网络容量分析会更加复杂.

3.1.3

组合优化与随机过程模型 文献[7]采用组合优化与随机过程研究,首先将网络分为 n×n 的网格,利用组合论分析节点在网格中的分布,

并得出在随机分配条件下 ,节点之间具有相同信道的概率 pmd.进而得到的结论是 ,随机分配模式下每个数据流 可获得的吞吐量为

Θ ?W ?
?

?

prnd ? ?. n log n ? ?

? f ?? f ? ? f ? 其中, prnd = 1 ? ?1 ? ??1 ? ? ,c 为信道总数,f 为连续频率点的集合.文献[9]用鸽笼原理对干扰 ? ... ? 1 ? c ?? c ? 1 ? ? c ? f + 1 ? ? 集的规模以及调度周期等问题进行了分析,也属于组合优化范畴.

组合优化与随机过程模型也是研究网状网容量优化理论的一个基础性问题 . 对于最大无关集和最大并行 流等 NP 完全问题,部分近似算法也用到组合优化理论.对于网络编码问题,也利用随机过程分析法对数据的分 布和容错、抗毁效率进行了分析. 3.2 综合评价与分析比较 为了便于不同容量估计算法进行横向比较 , 我们根据算法的特点进行了总结 , 部分算法虽然并非以网络容 量优化为目标,但是研究手段与问题的处理方法对于容量优化理论研究具有借鉴意义,在此一并列出(见表 1). Table 1
Network scenario Random Random Arbitrary Arbitrary Arbitrary Random Random

Characteristics of different capacity estimation algorithm
表1 不同容量估计算法特点简表
Trigger layer Static &Dynamic Static Static Static &Dynamic Static Dynamic Static Goal of optimization Throughput Fairness Fairness &Throughput Throughput Fairness &Throughput Maximum matching Throughput Interference model Protocol model Sender model Send/Recv model Protocol model Send/Recv model Send/Protocol model Protocol model Traffic factor Weighted factor Fairness factor Arbitray Arbitrary Randomize Randomize Random with delay parameters Random with probabilistic model

Algorithm Efficient-TDMA[9] MAX-MIN fairness[17] Joint routing
[28]

Execution layer Centralize &Distributed Centralize Centralize &Distributed Centralize Centralize Distributed Distributed

Characterizing mesh capacity[8] Algorithmic aspects[23] Distance-2[29] Capacity scaling[13] Comparative study[27]

Random

Distributed

Dynamic

Min E2E delay

Send/Recv model

我们从 4 个方面对模型(算法)进行综合评价,分别是:

(1) 模型的环境依赖性; (2) 模型的自适应性;

698

Journal of Software 软件学报 Vol.19, No.3, March 2008

(3) 模型的理论贡献; (4) 模型的实用性.
其中实用性和理论贡献是一对矛盾.适用性和环境依赖性也是一对矛盾. 按照上述评价准则,对现有的容量估计算法进行横向比较,结果如图 8 所示.图中算法的英文简称与表 1 相 对应.
Adaptivity

Distance 2 matching

Characterizing mesh capacity MAX-MIN fairness

Joint routing Theory contribution Gateway placement Reliability

Capacity multichannel impact Algorithm aspects

Comparative study Distributed joint channel

Efficient-TDMA

Environment dependancy

Fig.8

Comparison of algorithms under synthetic evaluation metric
图8 综合评价指标意义下的算法比较

4

亟需解决的问题及未来研究

4.1 更实用的理论成果 目前的研究还存在实用化程度不高的问题 , 还需要更加实用的理论成果 . 模型假设是影响模型实用性的重 要因素,现有模型的假设主要体现在网络环境、网络节点和优化应用目标 3 个方面,如图 9 所示.

(1) 网络环境的假设
网络环境假设主要包括流量假设、 网络拓扑假设和运动形态假设.如果将无线网状网作为传感网的接入手 段 , 网络环境假设则需要根据应用场景进行调整 . 实际的应用场景 , 传感节点的分布不再是均匀分布 , 节点的运 动也不再是随机游走 . 同时 , 流量的计算也需要结合应用场景中 , 而不是简单地固定比特率流量模型 . 节点拓扑 关系是容量分析的重点问题 ,直接影响调度策略 .如果用于军事侦察目的 ,节点布局则与军事目标运动和部署密 切相关,不可能是均匀分布.如果用于生态保护,则传感器的移动与生物的生活习性有关.

(2) 对于网络节点的假设
对于网络节点的假设 , 首先要考虑节点的通信能力 , 如信道数目与节点关系的模型 . 通常情况下 , 出于成本 考虑 ,信道数目是固定的 ,不会随节点数目的增加而增加 .在基于 TDMA 访问协议的场景下 ,需要考虑时钟同步 精度问题.算法基于 TDMA 的接入协议,不适合采用类似 RTS/CTS/DATA/ACK 的方式,因为 RTS 和 CTS 都是短 帧,对于时隙固定的 TDMA 协议而言,效率会很低.如果网状网节点存在能量限制,则需要考虑其生存时间;如果 网状网节点之间采用网络编码协议,则还需要结合存储优化策略进行考虑.

杨盘隆 等:无线网状网容量分析与优化理论研究

699

Total throughput Concurrent throughput Maximum lifetime Fairness Realtime
O n io at iz t im e c pt obj

Traffic Topology Mobility

N env etwo ir o r k nm ent

Storage Energey Network node capacity Configuration and communication Routing protocol

Fig.9 (3) 对于优化目标的假设

Realized theory results and assumptions of model
图9 实用化理论成果与模型假设

优化目标需要明确容量与吞吐量的区别 ,同时 ,网络稳定性的代价与目标 (是每一步的稳定还是逐步迭代的 稳定 ) 需要进一步明确 . 随着应用范围的扩大 , 公平性和实时性也成为系统追求的目标 , 需要结合具体的应用场 景确立优化目标.尤其是在多目标优化的情况下,更需要在各个因素之间寻求平衡. 4.2 具有容忍能力的网状网容量估计理论研究 不同的存储转发策略会导致网状网容量与资源分配调度策略发生明显的变化 ,那么 ,网关数目与节点数目 之间的关系如何描述? 固有容量也就是网络容量的上限为多少 ,可使用的网络容量至少 (容量下限 )是多少? 什么 样的策略会使上界和下界之间的差距尽量地小? 网状网资源分配与调度策略会发生什么样的变化? 这些都是我 们非常关心的问题 .同时 ,我们也特别关注端到端的可获得吞吐量 ,因为链路上的容量估计仍然不能作为网络获 得吞吐量的依据. 具有容忍能力的网状网 , 需要增加存储转发能力 . 同时 , 由于网络比网状网复杂 , 对图的连接的描述也有相 当大的限制 , 约束条件更多 , 模型会比较复杂 , 分析和求解都相当困难 . 由于面向工程的数学模型不同于纯粹算 法理论研究 ,实践中存在着可以简化的环节 ,可以充分利用容忍网状网的技术特点 ,从网络数据流量、节点分布 和存储特点等各方面的工程实际入手,对模型加以剖析,化简为繁,由简入繁,逐步逼近真实结论.

5

结束语
无线网状网容量估计与优化理论是链路调度优化策略、数据收集分发算法及网络可扩展性等问题的理论

基础 ,其中的研究方法涵盖了优化理论、信息论编码、随机过程及近似算法等多个学科领域 ,通过对现有技术 的分析与比较 ,有助于我们确立未来的研究目标 :一方面要提高模型的实用性 ;另一方面需要加强网状网的存储 能力,提出适用于复杂接入环境的时延容忍策略. 致谢 我们特别感谢 “国家重点基础研究发展计划 (973)重大技术专项——无线传感网络的基础理论与关键技

术研究”所提供的学术交流机会及资金支持. References:
[1] Akyildiz IF, Wang XD, Wang WL. Wireless mesh networks: A survey. Computer Networks, 2005,47:445?487.

700

Journal of Software 软件学报 Vol.19, No.3, March 2008

[2]

De Couto DSJ, Aguayo D, Bicket J, Morris R. A high-throughput path metric for multi-hop wireless routing. In: Proc. of the ACM Annual Int’l Conf. on Mobile Computing and Networking (MOBICOM). ACM, 2003. 134?146. http://portal.acm.org/citation. cfm?id=939000

[3]

Draves R, Padhye J, Zill B. Comparisons of routing metrics for static multi-hop wireless networks. In: Proc. of the ACM Annual Conf. of the Special Interest Group on Data Communication (SIGCOMM). ACM, 2004. 133?144. http://www.sigcomm.org/ sigcomm2004/papers/p171-draves.pdf

[4]

Wang Y, Wu HY. DFT-MSN: The delay/fault-tolerant mobile sensor network for pervasive information gathering. In: Proc. of the IEEE INFOCOM. 2006. 1021?1034. http://citeseer.ist.psu.edu/cache/papers/cs2/317/http:zSzzSzwww.cacs.louisiana.eduzSz~ wuzSzpaperzSzDFT-MSN.pdf/dft-msn-the-delay.pdf

[5] [6]

Gupta P, Kumar P. Capacity of wireless networks. Journal of IEEE Trans. on Information Theory, 2000,IT-46(2):388?404. Gapster M, Vetterli M. On the capacity of wireless networks: The relay case. In: Proc. of the IEEE INFOCOM. 2002. 1577?1586. http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/7943/21923/01019409.pdf

[7]

Kyasanur P, Vaidya N. Capacity of multi-channel wireless networks: Impact of number of channels and interfaces. In: Proc. of the ACM Mobicom. 2005. 43?57. http://www.crhc.uiuc.edu/wireless/papers/pradeep-capacity.pdf

[8]

Kodialam M, Nandagopal T. Characterizing the capacity region in multi-radio multi-channel wireless mesh networks. In: Proc. of the ACM MobiCom. 2005. 73?87. http://www.cs.sfu.ca/~qgu/pdf/MobiCom05KN.pdf

[9]

Wang W, Wang Y, Li XY. Song WZ. Efficient interference-aware TDMA link scheduling for static wireless networks. In: Proc. of the ACM MobiCom. 2006. 262?273. http://www.vancouver.wsu.edu/fac/song/pub/linkSchedule-MobiCom.pdf

[10]

Raniwala A, Gopalan K, Chiueh T. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks. Mobile Computing and Communications Review, 2004,8(2):50?65.

[11]

Krumke S, Marathe M, Ravi SS. Models and approximation algorithms for channel assignment in radio networks. ACM Wireless Networks, 2006,7(6):575?584.

[12]

Kumar A, Marathe M, Parthasarathy S. End-to-End packet-scheduling in wireless ad-hoc networks. In: Proc. of the ACM SODA. New Orleans, 2004. 1021?1030. http://web.sau.edu/LillisKevinM/wirelessbib/KumarMaratheParthasarathySrinivasan.pdf

[13]

Raniwala A, Chiueh T. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh networks. In: Proc. of the IEEE INFOCOM. 2005. 2223?2234. http://www.ecsl.cs.sunysb.edu/tr/hyacinth-infocom.pdf

[14]

Kyasanur P, Vaidya N. Routing and interface assignment in multi-channel multi-interface wireless networks. In: Proc. of the IEEE WCNC. 2005. 2051?2056. http://www.crhc.uiuc.edu/wireless/papers/pradeep-wcnc2005.pdf

[15] [16] [17]

Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 2nd ed., The MIT Press, 2001. Hochbaum D. Approximation Algorithms for NP-Hard Problems. Boston: PWS Publishing Company, 1997. 144?191. Aoun B, Boutaba R. Max-Min fairness capacity of wireless mesh networks. In: Proc. of the IEEE MASS. 2006. 21?30. http://bcr2. uwaterloo.ca/~rboutaba/Papers/Conferences/MASS06.pdf

[18]

Lin YF, Liang B, Li BC. Data persistence in large-scale sensor networks with decentralized fountain codes. In: Proc. of the IEEE INFOCOM. 2007. 1658?1666. http://www.eecg.toronto.edu/~bli/papers/ylin-infocom07.pdf

[19]

Liu JN, Goeckel D, Towsley D. Bounds on the gain of network coding and broadcasting in wireless networks. In: Proc. of the IEEE INFOCOM. 2007. 1658?1666. http://www.cs.umass.edu/~liujn/research/info07.pdf

[20]

Luby M. LT codes. In: Proc. of the 43rd IEEE Symp. on Foundations of Computer Science (FOCS). 2002. 271?281. http://www.inference.phy.cam.ac.uk/mackay/dfountain/LT.pdf

[21]

Katti S, Rahul H, Hu WJ, Katabi D, Muriel M, Crowcroft J. XORs in the air: Practical wireless networking. In: Proc. of the ACM SIGCOMM. 2006. 241?252. http://piper.csail.mit.edu/papers/copesc.pdf

[22]

Katti S, Gollakota S, Katabi D. Embracing wireless interference: Analog network coding. In: Proc. of the ACM SIGCOMM. 2007. 397?408. http://nms.csail.mit.edu/~dina/pub/anc.pdf

[23]

Kumar VSA, Marathe MV, Parthasarathy S, Srinivasan A. Algorithmic aspects of capacity in wireless networks. In: Proc. of the ACM SIGMETRICS. 2005. 133?144. http://portal.acm.org/citation.cfm?id=1071690.1064228

[24]

Kim SJ, Wang XD, Madihian M. Joint routing and medium access control for lifetime maximization of distributed wireless sensor networks. In: Proc. of the IEEE ICC. 2006. 3467?3472.

杨盘隆 等:无线网状网容量分析与优化理论研究

701

[25]

Kozat UC, Koutsopoulos I, Tassiulas L. A framework for cross-layer design of energy-efficient communication with QoS provisioning in multi-hop wireless networks. In: Proc. of the IEEE Annual Conf. on Computer Communications INFOCOM. 2004. 1446?1456. http://citeseer.ist.psu.edu/cache/papers/cs/33149/http:zSzzSzwww.ieee-infocom.orgzSz2004zSzPaperszSz31_3.PDF/aframework-for-cross.pdf

[26]

Németh G, Turányi ZR, Valkó A. Throughput of ideally routed wireless ad hoc networks. In: Proc. of the ACM MobiHoc. 2001. 271?274. http://citeseer.ist.psu.edu/cache/papers/cs/32921/http:zSzzSzwww.comet.columbia.eduzSz~zoltanzSzLargeAdhoc_mobi

hoc01.pdf/throughput-of-ideally-routed.pdf [27] Zhou W, Zhang D, Qiao D. Comparative study of routing metrics for multi-radio multi-channel wireless networks. In: Proc. of the IEEE WCNC. 2006. 270?275. http://home.eng.iastate.edu/~daji/papers/wcnc2006.pdf [28] Alicherry M, Bhatia R, Li L. Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks. In: Proc. of the ACM Mobicom. 2005. 58?72. http://portal.acm.org/citation.cfm?id=1080829.1080836 [29] Balakrishnan H, Barrett CL, Kumar VSA, Marathe MV, Thite S. The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc wireless networks. IEEE Journal on Selected Areas in Communications, 2004,22(6):1069?1079.

杨盘隆(1977-),男,辽宁盘 锦人,博士,讲 师,主要研究领域为无线传感网技术,无线 自组织网络技术,协议一致性测试技术.

陈贵海(1963-),男,博士,教授,博 士生导 师,CCF 高级会员,主要研究领域为无线传 感网,并行计算技术,网络计算技术.


相关文章:
无线网络的网络容量研究进展
计算机科学,2006,33(4):1-3,8 杨盘隆,陈贵海.无线网状网容量分析与优化理论研究.软件学报,2008,19(3):687-701 Jovicic A, Viswanath P, Kulkarni S.R....
无线网状网及其发展.李明.201110405118
Zigbee无线组网技术的研究 84页 免费 无线网状网络 ...从技术上分析,无线网状网、Wi-Fi、WiMAX 彼 此...在选择路由时考虑无线电链路的质量和容量 避免环路 ...
无线网络优化论文
GSM无线网络优化论文,涵盖案例分析 东莞理工学院 本科...一、研究背景及其目的随着移动通信的普及,GSM 已经...如何合理利用配置现有的 网络设备、资源与容量,最...
LTE网络容量优化方法研究
龙源期刊网 http://www.qikan.com.cn LTE 网络容量优化方法研究 作者:吴文波 来源:《中国新通信》2014 年第 23 期 【摘要】 介绍了 LTE 网络无线帧结构,对 ...
毕业论文 无线通信网络优化
分析与排查,提出并实施了切合工程实际的无线网络 ...因此网络优化工程师需要较全面的基础理论知识和专业...因为 CDMA 系统的容量直接与所受的干 ○ 扰有关,...
无线Mesh网络关键技术分析
无线 Mesh 网络(简称 WMN、无线网状网、无线多条网或无线网格网)是 一种多跳、具有自组织和自愈等特点的新型宽带无线网络,也是一种高容量、高 速率的分布式网络...
无线网状网中的抗干扰频道分配
本文提及了频道划分的问题以及特别研究了无线网状网...我 们利用链路状态路由优化方法和加权累积预期传输来...无线网状网容量分析与优... 15页 免费 无线网状网...
毕业设计无线局域网WLAN优化技术研究
关键词:无线局域网;覆盖;容量;干扰;优化 I ...从理论上来讲,这很容易被监听,导致信息在不知不觉...无线传输链路和干扰的分析与调整,最 终达到提升网络...
网络优化现状及发展趋势分析报告
年中国网络优化市场调查研究及发展前景趋势分析报告 ...随着通信技术服务涉及的领域越来越广以及市场容量越来...无线网络日常优化 三、交换网络日常优化 四、通信...
CDMA网络优化北邮毕业论文
无线网络优化 摘要 CDMA 是为满足现代移动通信网在大容量、高质量、综合业务、...通过对覆盖区基本情况、网络覆盖、质量、话务的分析,应用 现有理论和技术,在...
更多相关标签:
无线网状网 | lte容量优化 | 性能容量优化 | 微网容量组合优化 | 基站容量优化 | 最优化理论与算法 | 最优化理论 | 最优化理论与方法 |