（通信与信息系统专业论文）面向ad+hoc网络应用的协同功率分配策略与网络性能研究.pdf

南京j i u 人学颂l j 研究生学位论文摘曼 摘要 无线a dh o e 网络是在没有固定基础设施的情况下，由具有无线通信功能的节点自组 织形成的网络，它的主要特点是无线、多跳和移动。这种网络的简易、快速部署以及抗 毁性强等特点使得它不仅能有效延伸传统网络的覆盖范围，也能独立满足不同场合的特 殊需要，如军事、工业、家庭及办公等各种场合与行业。a dh o c 网络节点电池能量有限， 节约能量是主要问题。拓扑控制的目标是通过控制节点的传输功率使生成的网络拓扑满 足一定的性质，以降低节点的功率开销，延长网络生命周期，减小网络干扰，提高吞吐 率。我们对a dh o c 网络中的拓扑控制引入协同通信技术，利用协同通信技术的优点，建 立一个t c c 模型，确保网络拓扑结构强连通性的前提下，运用d t c c 算法和i t c c 算 法，对网络中的节点进行功率分配，使整个网络的总功率减少，达到功率控制的目的。 本论文的主要研究工作包括： 首先论述了a dh o c 网络的特点及研究的难点，分析讨论了a dh o c 网络中功率控制和 拓扑控制并研究了两种传统的典型拓扑控制算法c b t c 算法和l m s t 算法； 然后论述了协同通信技术及其三类典型的方案：译码前传法、放大前传法和编码协 同法，并提出了在拓扑控制中引入协同通信技术，给出了t c c 模型及相关的分析； 最后重点研究了d t c c 算法和i t c c 算法在t c c 模型中的应用，分别对其进行性 能分析以及与传统的l m s t 算法和d m s t 算法进行比较，并给出了在t c c 模型的参数 不同时d t c c 算法和i t c c 算法的性能仿真，得到了若干结论。 关键词：无线白组网，协同通信，拓扑控制，功率分配 南京l l l f f l 【1 人学倾i j 研7 生学位论文 a b s t r a c t a b s t r a c t w i r e l e s sa dh o cn e t w o r ki sf o r m e df r o ms e l f - o r g a n i z e dw i r e l e s sc o m m u n i c a t i o nf u n c t i o n n o d e sw i t h o u ta n yf i x e di n f r a s t r u c t u r e ，w h o s em a i nc h a r a c t e r i s t i c sa r ew i r e l e s s ，m u l t i - h o pa n d m o b i l i t y t h ep r o p e r t i e so fs i m p l i c i t y , f a s td e p l o y m e n ta n ds t r o n gs u r v i v a b i l i t yo ft h ea dh o c n e t w o r km a k ei tc a p a b l eo fe x t e n d i n gt h ec o v e r a g eo ft h et r a d i t i o n a ln e t w o r ke f f e c t i v e l y , a n d m e e t i n gt h es p e c i a ln e c e s s i t i e si nv a r i o u ss i t u a t i o n s ，s u c ha sm i l i t a r ya f f a i r ，i n d u s t r y ，h o m e ， a n do f f i c e ，e t c t h eb a t t e r yp o w e ri sl i m i t e di na dh o cn e t w o r k ，s oi t sv e r yi m p o r t a n tt os a v e p o w e ru s i n g t h eo b j e c t i v eo ft o p o l o g yc o n t r o li st ob u i l dp r o p e rt o p o l o g yb yc o n t r o l l i n g n o d e st r a n s m i s s i o np o w e rt od e c r e a s ee n e r g yc o n s u m p t i o na n dc o m m u n i c a t i o ni n t e r f e r e n c e ， e x t e n dn e t w o r kl i f e t i m ea n di m p r o v en e t w o r kt h r o u g h p u t w eu s et h e c o o p e r a t i v e c o m m u n i c a t i o nt e c h n o l o g yi nt h et o p o l o g yc o n t r o lo fa dh o cn e t w o r k ，t a k i n ga d v a n t a g eo f c o o p e r a t i v ec o m m u n i c a t i o nt e c h n o l o g yt os e tu pat c cm o d e l ，i np r e m i s eo fp r e s e r v i n gt h e n e t w o r kt o p o l o g yc o n n e c t i v i t y ，r u n n i n gt h ed t c ca l g o r i t h ma n di t c ca l g o r i t h m ，a l l o c a t i n g t h en o d e sp o w e rt or e d u c et h et o t a lp o w e ro fn e t w o r ka n da c h i e v et h eg o a lo ft o p o l o g y c o n t r 0 1 t h em a i nr e s e a r c hw o r ko ft h i st h e s i si n c l u d e s ： f i r s t l y ，w ei n t r o d u c et h ec h a r a c t e r i s t i c so fa dh o cn e t w o r ka n dd i f f i c u l tp o i n t so fr e s e a r c h b r i e f l y ，t h ep o w e rc o n t r o la n dt o p o l o g yc o n t r o li na dh o cn e t w o r k w ea l s op r e s e n tt w ok i n d s o ft r a d i t i o n a lt o p o l o g yc o n t r o la l g o r i t h m s ，w h i c ha r ec b t ca n dl m s t ； t h e n ，w ed i s c u s st h ei d e a so fc o o p e r a t i v e c o m m u n i c a t i o nt e c h n o l o g ya n dt h r e e c o o p e r a t i v es c h e m e s ：a m p l i f y a n d f o r w a r d ，d e c o d e d a n d f o r w a r da n dc o d e dc o o p e r a t i o n w e a p p l yc o o p e r a t i v ec o m m u n i c a t i o nt e c h n o l o g yi nt o p o l o g yc o n t r o l ，a n dt h et c cm o d e li s p r e s e n t e d ； a tl a s t ，w es t u d yt h ea p p l i c a t i o no fd t c ca n di t c ci nt h et c cm o d e l ，a n a l y z et h e p e r f o r m a n c eb yc o m p a r i n gw i t ht r a d i t i o n a ll m s ta n dd m s ts e p a r a t e l y ，d ot h ep e r f o r m a n c e e m u l a t i o no fd t c ca n di t c cw h e nt h ep a r a m e t e r so ft c cm o d e lc h a n g e s k e yw o r d s ：w i r e l e s sa dh o cn e t w o r k ，c o o p e r a t i v ec o m m u n i c a t i o n ，t o p o l o g yc o n t r o l ，p o w e r a l l o c a t i o n 南京i i | i j l u 人学顾l j 研究生学位论文缩略语硎汇 缩略语词汇 b sb a s es t a t i o n 基站 d fd e c o d e d a n d f o r w a r d 译码前传法 a f a m p l i r y a n d f o r w a r d 放大前传法 c c c o o p e r a t i v ec o m m u n i c a t i o n协同通信技术 g p sg l o b a lp o s i t i o n i n gs y s t e m 全球定位系统 g t cg e n e r a l g r a p h v e r s i o no f t o p o l o g y一般图形版本的拓扑控制 c o n t r o l t c c t o p o l o g yc o n t r o lw i t h 采用协同通信技术的拓扑控制 c o o p e r a t i v ec o m m u n i c a t i o n m s tm i n i m u ms p a n n i n gt r e e 最小生成树 c b t cc o n e b a s e d d i s t r i b u t e d 基于扇区的拓扑控制 t o p o l o g y c o n t r o l l m s tl o c a lm i n i m u ms p a n n i n gt r e e 本地最小生成树 d m s td i s t r i b u t e dm i n i m u ms p a n n i n gt r e e 分布最小生成树 d t c cd i s t r i b u t e d t o p o l o g y c o n t r o l u s i n g采用协同通信技术的分布拓扑控制 c o o p e r a t i v ec o m m u n i c a t i o n i t c ci n c r e m e n t a l t o p o l o g y c o n t r o l u s i n g采用协同通信技术的递增拓扑控制 c o o p e r a t i v ec o m m u n i c a t i o n 6 3 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均己在论文中作了明确的说明并表示了谢意。 研究生签名：垦蔓墨同期：型塑：竺! 兰 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：鍪盏垄 - 91 j i t j 签 q 、 南京帅i u 学$ lj 研究生学位论空笫一章绪论 第一章绪论 无线a dh o c 网络( 以f 简称a dh o e 网络) 是仪由一组装备无线通信装置、具有联网 能力的节点组成，而没有任何基础设施的无线通信网络 i 【2 【3 。 a dh o c 网络研究的最初动困来自于军事需求。自2 0 世纪7 0 年代丌始，美国以及一 些西方国家开始研究a dh o c 网络，其目的是期望在战场恶劣的环境下，不需要铺设任何 通信设施而快速组建通信网络。如今，a dh o c 网络的应用日益广泛，除了应用于军事领 域外，在医疗急救、灾难恢复、大型会议、环境检测等方面，甚至同常生活，如家庭、 个人周边设备的通信中都有广泛应用。图11 显示了一个简单的a d h o c 网络。 1 1a dh o c 网络的特点 漤 力i 铲 0 式_ 幽1 i 简单的a dh o c 时络实例 a dh o e 网络因其无线、点对点的通信方式，使得它与传统网络具有很大的不同。与 传统的计算机网络相比，a dh o c 网络中的节点具有可移动性，拓扑结构的动态可变性 以及在通常情况下无需额外通信费用等特点。a dh o c 网络也不同于蜂窝移动通信系统； 在蜂窝网络中，主要由基站( b a s es t a t i o n ，b s ) 组成的固定网络形成通信系统的基础性 网络。网络中的移动设各通过无线信道与基站建立连接，从而访可网络资源。蜂窝网络 的优点是基础性网络的存在增强了通信的可靠性，其缺点也很明显，即并非所有地方都 能够建立基础性网络，而在没有基站信号覆盖的地方，移动设备也就无法进行通信。a d h o c 网络正好弥补了这一缺点。它为没有基站覆盖或需要为移动设各建立l 脚对网络的场 添j ：弓 南京| i i i j i 【1 人学颂f j f j f 究生学位论义第一章绪论 合提供了设备问有效通信的方式。 a dh o c 网络主要具有以下特点： 1 无基础性网络 a dh o c 网络中，由于不存在基础性网络，任何节点在作为网络普通节点的情况下， 可能同时充当了路由、网关等多种角色。任何一种角色的实现，都需要相应的协议和算 法提供支持。这些协议和算法通常需要在分布环境下依赖于本地信息而执行。这是因为， 在没有基础设施，如基站、服务器等的无线a dh o c 网络中，节点为获取网络全局信息需 要很大的通信丌销，而且在移动a dh o c 网络中，节点的移动性导致信息很快过时，因此， 依赖于全局信息的集中式算法在a dh o c 网络中通常是不现实的。由于没有基础性网络， a dh o c 中传递的消息可能需要经由多个中间节点才能到达目标节点，因此a dh o c 网络是 一种多跳网( m u l t i h o pn e t w o r k s ) 。 2 节点资源的有限性 a dh o c 网络中的节点往往是手持设备，因而，其能量储备和计算能力都是非常有限 的，同时硬件配置也有可能比较简单。所以如何利用这些简单而有限的资源，在a dh o c 网络中提供有效的数据通信，是众多协议和算法需要考虑的问题。一方面，由于节点通 常由电池提供能量，在网络通信过程中应尽可能地降低功率丌销；另一方面，由于节点 的计算能力和硬件设备的限制，复杂的、或者需要众多额外信息的协议或算法往往是不 实际的，因为节点可能无法支付所需的计算丌销，或者无法获取计算所需的信息。 3 无线通信介质的不可靠性 a dh o c 网络中无线通信介质的不可靠性主要体现在以下几个方面：首先，无线传输 受到地形地势、天气、障碍物等多方因素的影响，因而本质上是不可靠的；第二，节点 信号可能受到其它节点信号的干扰，因而信息可能无法被j 下确传输；再者，无线网络信 号传输的本质是广播，这种广播会带来隐藏终端和暴露终端等问题：最后，广播特性以 及无集中化的安全认证，使网络更易受到窃听和攻击。由于通信的不可靠性，在移动a d h o c 网络中，复杂而精确的协议通常没有用武之地。这是因为基于不可靠的通信网络之 上的复杂精确的协议，其输出常常不会令人满意，基于这点，许多研究目前仅仅在假 南京邮i 【1 人学f 嗍i ：研究生学位论义 第一帚绪论 设的理想网络模型中进行。 4 节点的移动性 在传统的有线网络中，节点是固定的，因而网络的拓扑是长时l 、日j 不变的。然而，在 移动a dh o c 网络中，节点被允许任意移动，这种移动使得网络拓扑经常发生变化，而节 点的快速变化常会导致路由的迅速无效甚至数掘分组的丢失和错误。以上这些特点给a d h o c 网络中相关协议与算法的设计带来挑战。一方面，设计应尽可能的简单化( 尽量减 少计算复杂度) 和本地化( 仅仅依赖于本地信息) ，以此适应a dh o c 网络中节点资源的 有限性；另一方面，设计需要考虑网络拓扑的动态性和通信的不可靠性，甚至网络的异 构性等众多因素。事实上，设计的这两个方面在很多情况下存在着矛盾。因此，现有的 协议与算法往往是基于特定的网络模型和针对特定问题而提出的解决方案。 1 2a dh o c 网络研究内容 目前a dh o c 网络研究的主要内容为路由协议、服务质量、m a c 协议、功率控制、 节点移动性管理、安全性问题等。 1 路由协议：丌发良好的路由协议是建立a dh o c 网络的首要问题，同时也是主要的 研究热点和难点。传统的距离向量和链路状态路由协议并不适用于拓扑结构高度动态变 化的a dh o c 网络。理想的a dh o c 网络的路由协议应陔具有以下性能：分布式运行、无环 路、按需运行、考虑安全性、高效地利用电池能量、支持单向链路。 2 服务质量q o s ：q o s 是指信源端向目的端发送分组流时，网络向用户保证提供一 组满足预先定义的服务性能约束，如端到端的延迟、带宽、分组丢失率等。现有的无线 网络中提供q o s 保障的机制一般都基于有基础设施的单跳蜂窝系统，无法直接应用在多 跳、拓扑动态变化的移动a dh o c 网络中。这就要求设计和研究新的q o s 保障机制，为 a dh o c 网络中的各种业务提供相应的服务质量保证。 3 介质访问控甫o ( m a c ) 协议：a dh o c 网络中m a c 协议主要是i e e e 8 0 2 11 标准中的 c s m a c a 协议和h i p e r l a r d 2 协议。i e e e8 0 2 11m a c 层的协议在多跳网络中存在一些 问题：首先，仍然没有解决隐藏终端和暴露终端问题，i e e e8 0 2 1 1 m a c 协议的载波监听 ( 和干扰) 的范围通常大于通信范围，加剧了隐减终端和暴露终端的问题；其次，二进制 南京i | f i j i u 人学坝j j 研究生学位论义第一章绪论 退避算法对刚发送成功的节点有利，对发送失败的节点不利，使各节点问存在明显的不 公平；再者，没有考虑a dh o c 网络功率控制的问题。 4 功率控制问题：功率控制问题涉及到无线网络中的各层。节点功率控制可以分为 通信丌销和计算丌销两部分。前者是指无线网络接口消耗的能量。在a dh o c 网络中，移 动节点可以处于发射、接收和空闲( 旁路) 三种模式，其中发射模式的功率消耗最大，空 闲模式的功率消耗最小，缺省模式为空闲模式。后者指协议处理方面消耗的能量。通常 在这两者之间存在一个折衷，降低通信丌销的技术可能增加计算丌销，反之亦然。在接 收端可以f 确接收分组的前提下，减少节点的功率消耗可以延长节点和网络的寿命；减 少了对邻节点的干扰，提高了网络的吞吐量；减少了数据被窃听的可能性，提高了通信 的安全性。在物理层可以调整节点的发射功率来减少网络的功率消耗。m a c 层的主要 措施为减少数据发送的冲突、避免重传和进入睡眠状态。在网络层，采用功率控制路由 算法，而不是以最小跳数或最小延迟作为路由度量。 5 安全性问题：无线链路使a dh o c 网络容易受到链路层的攻击，包括被动窃听和主 动假冒、信息重放和信息破坏；节点在敌方环境( 如战场) 漫游时缺乏物理保护，使网络 容易受到已经泄密的内部节点( 而不仅仅是外部节点) 的攻击，而采用分布式的网络体系 结构可以提高a dh o c 网络的生存能力；a dh o c 网络的拓扑和成员经常改变，节点i 白j 的信 任关系经常变化，与移动i p 相比，a dh o c 网络没有值得信任的第三方的证书的帮助，在 节点建立信任关系成为a dh o c 网络安全的中心问题；a dh o c 网络包含成百上千节点，需 要采用具有扩展性的安全机制。 1 3 论文研究内容 协同通信是最近几年无线通信领域的研究热点。单天线的终端采用协同通信技术后 形成虚拟的m i m o 系统，可以实现良好的分集或者复用效果，系统的容量、可靠性和 功率效率有大幅度的提高。 功率控制是a dh o c 网络中的一项重要内容，本论文研究协同通信技术在a dh o c 网络 功率控制中的应用，目的是最大地节省a dh o c 网络的功率，从而满足对整个网络功率丌 销的控制。我们研究了高能效的拓扑控制算法来降低网络通信时候的功率丌销。具体的 做法就是通过对网络中节点进行功率分配，满足网络拓扑结构连通性的情况下，动态地 调整无线节点功率从而改变节点的传送范围。在建立的t c c 模型中使用了协同通信技 4 南京l j | l j l u 人掌坝i j 研冗生学位论义第一章绪论 术，从而网络的节点通过合并部分信息能成功解码出完整的信息。在满足合并部分信启、 能成功解码的前提下，节点动态地分配各个节点的功率，使整个网络总的功率丌销都发 生了一定程度的减少。我们研究了两种采用协同通信技术的拓扑控制算法( d t c c 算法 和i t c c 算法) ，在这两种拓扑算法的初始拓扑结构中，网络节点初始的功率分配就是不 一样的，两种算法对节点功率重新分配的策略也是不同的。分析和仿真结果表明，两种 算法与传统的拓扑算法相比都降低了网络的功率丌销。 1 4 论文架构 本论文主要是研究在a dh o c 网络中拓扑控制引入协同通信技术后，建立一个t c c ( t o p o l o g yc o n t r o lw i t hc o o p e r a t i v ec o m m u n i c a t i o n ) 模型，确保拓扑结构强连通性的前 提下，运用d t c c ( d i s t m u t e dt o p o l o g yc o n t r o lu s i n gc o o p e r a t i v ec o m m u n i c a t i o n ) 算法和 i t c c ( i n c r e m e n t a lt o p o l o g yc o n t r o lu s i n gc o o p e r a t i v ec o m m u n i c a t i o n ) 算法，对网络中的节 点进行功率分配，使整个网络消耗的总功率减少，达到功率控制的目的。本论文的结构 安排如下：第二章简要分析了a dh o c 网络中功率控制和拓扑控制，研究了两种传统的典 型拓扑控制算法c b t c ( c o n e b a s e dd i s t r i b u t e dt o p o l o g yc o n t r 0 1 ) 算法和l m s t ( l o c a l m i n i m u ms p a n n i n g t r e e ) 算法；第三章论述了协同通信技术产生的背景，三类主要的协 同方案：译码前传法( d e c o d e d a n d f o r w a r d ，d f ) 、放大前传法( a m p l i f y a n d f o r w a r d ， a f ) 平i 编码协同法( c o d e dc o o p e r a t i o n ) ，然后研究如何在拓扑控制中引入协同通信( c c ： c o o p e r a t i v ec o m m u n i c a t i o n ) 技术，建立t c c 模型；第四章研究了d t c c 算法和i t c c 算 法，分别进行性能分析，并与传统的l m s t 算法和d m s t 算法进行比较研究；第五章 主要通过仿真对d t c c 算法和i t c c 算法进行比较研究，得出有关结论；第六章是进一 步研究的建议。 南京l | | | j i 【i 人学f 唤i j 研究生学位论文第二常a dh o ch 络中j j j j 红挣制使拓扑摔制算法 第二章a dh o c 网络中功率控制及拓扑控制算法 2 1a dh o c 网络中的功率控制 a dh o c 网络中，节点靠自身携带的能源进行通信，生存时间较短。为了尽量延长网 络的生命周期，必须使用功率控制机制，减小不必要的功率损耗。功率控制主要是通过 调整发送节点的信号传输功率，在保证一定通信质量的前提下尽量降低信号的传输功 率。 a dh o c 网络对功率控制技术的要求是 4 ： 分布式：要求功率控制算法能在各节点处分别运行。 简单性：要适于实时执行，而且不能消耗过多的计算资源。 灵活性：能快速跟踪信道的改变以及由于节点移动而造成的网络拓扑变化。 健壮性：能适应各种不同的情况，特别是一些偶发事件。 可扩展性：在各种网络规模条件下都能f 常运行。 在进行功率控制算法设计时，不但要遵循以上原则，更要充分考虑到各种因素，以 保证算法的实用性和可靠性。 a dh o c 网络中的功率控制机制研究主要集中在3 个方面，即网络层功率控制、链路 层功率控制以及混合功率控制。网络层功率控制所关心的问题是如何通过改变传输功率 动态调整网络的拓扑结构和选路，最终使全网性能得到优化；链路层功率控制主要通过 m a c 协议完成，发送节点根据每个报文目的节点的距离、信道状况等条件来动态调整 传输功率，用以提高网络容量或降低节点能耗；混合功率控制将这两种机制结合起来， 用网络层的功率控制调整网络拓扑结构和选路，而在发送报文时通过链路层功率控制根 据目的节点的远近调整发送所用的功率。 1 网络层功率控制 通常，在收发机参数及信道条件一定的情况下，节点的传输功率决定了节点的通信 距离。当此通信范围内的节点数过多时，由于竞争的加剧导致冲突迅速增加，使整个网 络的性能不能达到最优。无线自组网使用环境特殊，节点分布密度有时是无法预料的， 这就需要种机制来自动调节节点的传输功率，使其根据节点的分布情况自动调节传输 功率。但目前，对于网络中的节点到底应该用多大功率传输的问题仍然难以回答。因为 发送功率大，通信距离远，报文平均转发次数就少，信道的空间复用度降低，每个节点 6 南京邮l 【1 人学坝| ：研究生学位论文第_ 二常a dh o ch 络中j j 半拧制使拓扑控制算：泫 的有效带宽就会减小；而减小传输功率，能提高信道的空l 刮复用度，增大节点的有效带 宽，但报文的平均转发次数要增多。 对于节点静止的a dh o c 网络，理论分析得出最佳邻节点的个数为6 时，网络性能最 好 5 】。而对于移动的a dh o c 网络，当移动性的节点增加时，应适当提高传输功率以增 大邻节点数目 6 ，因为这样能减少链路中断的次数，同一路由能维持更长的时间，所以 能更好的提高网络性能。 网络层功率控制根据节点网络层获得的拓扑信息进行相应操作，通过使用最小传输 功率来构成想要的网络拓扑，从而使网络获得更好的性能。 2 链路层功率控制 链路层的功率控制一般通过m a c 协议完成，其目的是在给定最大传输功率条件下， 通过功率控制尽量节省节点能耗和提高信道的空浏复用度。链路层无线自组网拓扑控制 算法研究功率控制机制不会影响网络拓扑结构，因此不会增加报文在转发过程中所经历 的平均跳数。c s m c a 类型的m a c 协议在发送数据报文前要首先经过r t s c t s 控制 报文的交互，这为进行功率控制提供了极大方便，当前链路层的功率控制机制也主要是 以此为基础进行的。无线自组网中的信道接入协议按具体的工作方式可分为单信道协议 和多信道协议。他们都可以使用功率控制机制来提高整个网络的容量。 3 混合功率控制 在混合功率控制机制中，网络层功率控制负责调整节点发送广播或控制报文时的功 率以形成较合适的网络拓扑，而当节点发送数据报文时则根据目的节点的位黉! 通过链路 层功率控制机制使用较小的功率发送。 t a e l b a t t 等人研究了一种低速移动网络中的分布式功率控制机带l j 7 ，节点动态调 整自己的传输功率，以使邻节点数目保持恒定。协议有一个信令信道和一个反向确认信 道，并需要全网同步机制。每个节点在信令信道上的特定时隙用最大功率发送信标报文。 其它节点按各信标报文的平均接收功率大小将其周围节点排序，并调整自己的传输功率 以使邻节点数保持为预定值，同时更新其邻节点的损耗。节点随后再在信令信道上广 播其邻节点表，其他节点据此获得全网的网络拓扑。路由协议采用由表格驱动最短路径 算法改进而得到的基于最小能耗的路由算法。由于各节点各自调整后的传输功率可能各 不相同，可能导致出现单向连通链路。协议利用个反向信道，用最大功率发送确认消 息，部分解决了此问题。 功率控制的好处是能使网络的拓扑结构保持稳定，提高信道空f b j 复用度，易于进行 位置管理。 7 南京i f i j j i u 人学硕i j 研究生学位论文 第二章a dh o c 川络中j j 半控制硬拓扑控制算法 2 2a dh o e 网络中的拓扑控制 2 2 1 拓扑控制与a dh o e 网络其它研究内容之间的关系 图2 1 拓扑控制与a dh o e 网络中其他研究领域之间的关系 图2 1 表示了拓扑控制与m a c 层、功率控制以及上层的路由控制之间的关系。拓 扑控制是a dh o c 网络中一个重要的研究领域。目前的研究往往通过图形学、随机过程、 博弈论等各种方法学为网络设计合理的拓扑，并通过控制节点的传输功率实现最终的拓 扑结构，从而为上层的路由提供支持。关于m a c 协议，较为成熟的有 m a c a 8 ，m a c a w 9 】以及i e e e 8 0 2 1 lm a c 协议d c f 1 0 等。目前很多人认为应该将功 率控制融入到m a c 协议中，典型的例子有p a m a s 协议 11 】。关于路由协议，近年来的 许多研究往往综合了m a c 的信道分配，q o s ，功率控制以及拓扑控制等功能，这种 c r o s s l a y c r i n g 的设计方式，已经成为a dh o c 网络研究的焦点。 2 2 1 拓扑控制的目标 在没有拓扑控制的a dh o c 网络中，每个节点采用最大的传输功率进行通信。这样的 网络存在两个主要问题。 首先，功率浪费。网络中互为近邻的两个节点通信时，通常不需要采用最大传输功 率即可成功的进行消息传递。由于最小传输功率以距离的路径耗损指数方式增长，其指 数范围通常为2 - 6 。因此，近距离的传输如能降低传输功率将会在很大程度上节约功率 开销。假设路径耗损指数为4 ，所需最小传输功率为距离的路径耗损指数次方。若节点 的最大传输距离为2 0 0 米，则在不考虑丢包等出错影响的情况下，不同距离下若以最小 传输功率进行通信所节约的功率p ：朋占最大传输功率p ：的比率( 定义为最大节能率， 南京邮i 【1 人学顺f j 研究生学位论文第二章a dh o cm 络中助；红挖制及拓扑摔制算：f 左 即吒= 比。p ；，) 如图2 2 所示。 姆 u d 血= # 斗 5 n 6 则不能保证网 络连通性。 多跳无线网络，例如分组无线网络、a dh o c 网络和传感器网络 1 9 】，都具有以下的 特点：两节点间的通信可能会经过多条连续的无线链路。而有线网络一般有固定的网络 拓扑( 除了发生故障) 。无线网络中的节点通过调整自己的发射功率来控制自己的邻节 点个数，从而可以潜在地改变网络拓扑。 拓扑控制的目的是设计控制功率的高效算法，既可以保持网络连通性又能优化网络 性能指标，如延长生存时i n ：币1 2 增加吞吐率。在节点出现故障和节点移动时，需要简化网 络的初始配置和重新配置过程，分布式的拓扑控制算法由于只需要知道本地的拓扑信息 并且容许异步运行，这两个特征使算法很有价值。 c b t c 算法具体描述如下： 给定节点集合v ，v 是平面上的所有移动节点的集合。对于每个在矿中的节点“， 在任一个给定时刻用指定的坐标( x ( z 吐j ，( “) ) 来表示。每个节点有功率函数p ，这罩用 p ( d ) 表示节点“与距离为d 的节点v 建立通信链路所需的最小功率。假定，每个节点的 最大发射功率p m 缸都是相同的，并且任意两个节点之问直接通信的距离为尺，例如 南京邮i u 人学颂i j 研究生学位论文第二币a dh o cm 络中助；红挖制及拓扑控制算法 p ( 尺) = p 驮。如果每个节点均以最大功率p “发射，可以得到个g 门= ( 矿，) ，其中 e = ( “，v ) fd ( u ，v ) r ) ( d ( u ，v ) 是节点z z 和节点v 之间的欧几罩德距离) 2 0 。 不希望节点以最大功率发射有两点原因。 1 ) 两点之间通信所需的功率是距离的门次幂，一般 l 2 2 1 ，节点“通过一系列 的中继节点把消息发送到节点v 比节点“直接发送到节点v 需要更小的功率。 2 ) 节点发射功率越大，则对其他节点传输数据时的干扰可能性也越大。 提出的拓扑控制算法的目的就是找到g 。的一个子图g ，g 满足： 1 ) 包含了瓯中的所有节点，但有较少的边。 2 ) 若节点“和节点v 在g 凡中连通，那么在g 中也是连通的。 3 ) 节点“发射信号到g 中所有其邻节点所用的功率要比蹦发射信号到g ”中的邻节 点所用的功率小。 因为使网络的功率消耗最小非常的重要，所以希望可以找到一个图g 满足以上的三 点。更进一步说，为了让拓扑控制算法具有实际意义，对于网络中的每个节点“必须能 够以一种分布式的方式建立自己的邻节点集n ( u ) = vl ( 甜，v ) g 。最后，如果由于节点 发生故障或移动而使g 。变为g 。厅，必须能够在不知道全局节点坐标信息的情况下重构连 通图g 。 c b t c 算法满足了上面的这些条件。在这之前的拓扑控制算法通常都是借助于g p s 的支持知道位置信息。使用g p s 有很多缺点，特别是通过g p s 获得位置信息有很大延 时，并且g p s 不能工作在室内。相比较而言，c b t c 算法却仅仅需要方向信息。也就是 说，必须能估计从另一个节点接收来的信号的方向。不知道位置信息的情况下估算方向 从技术上来说是可行的，可以通过天线技术解决这个问题。解决这个问题的一般做法是 使用不止一个的定向天线，具体的讲，接收到的信号方向由信号到达各个接收天线元的 时间差决定。 c b t c 算法以口角度作为参数。节点“尝试找到最小功率b 。，以功率p 虮。发射信 号时必须确保“周围的每个o r 扇形区域内，都有某个节点“的信号可以到达的节点。若 满足口5 x 6 ，则如果在g ( 包括了所有的节点) 中有一条从节点甜到节点y 的路径， 那么在g 。中也会有这样的一条路径；否则，图g 心是连通的，但图瓯却是不连通的。 1 1 南京i | | l j l u 人学颂f j 饼彳e 生学位论义第二章a dh o cm 络中功：年摔制使拓扑摔制算法 2 c b t c 算法的具体步骤： 这里用到了三个通信原语：广播，发送，接收 b r a s t ( u ，p ，聊) ：表示节点“以功率p 发射消息m ，它导致节点集 v ip ( a ( u ，v ) ) p ) 中 的所有节点可以接收到消息1 7 7 。 s e n d ( u ，p ，m ，v ) ：表示节点“以功率p 向节点v 发射消息m 。这一通信原语用来发送 单播消息。 r e c v ( u ，m ，v ) ：表示节点u 从节点v 接收到消息m 。 假定当节点v 从节点u 接收消息m 时知道消息m 的接收功率p 7 。因为存在着信号空 间衰减，这个功率一般小于节点u 发送消息m 的功率p 。并且假定给定传输功率p 和接 收功率p 7 时，节点“可以估计p ( d ( u ，v ) ) 。 为了方便表示，先假定一个同步模型；即假定通信是按照一个由全局时钟控制的时 间单位轮转进行，每一轮都会消耗一个时间单位。每一轮中节点b l 可以用通信原语b r a s t 和s e n d 检测发给它的消息，计算发送消息的功率。 c b t c 算法解释如下：算法用角度口作为参数，每个节点“尝试在以节点甜为中心 的每个扇形区域口内，搜寻至少一个邻节点。节点b t 先以一个较低的发射功率广播h e l l o 消息，同时收集反馈的a c k 。它会不断的增加发射功率去找到更多的邻节点。同时保留 一张已经发现的邻节点的方向表，然后根据这个方向表检测扇形区域口角度内是否存在 一个节点。这个算法很容易实现：节点按它们与参考点形成的角度进行排序。很显然， 如果有一个以u 为中心的扇形区域口没有节点，那么在两个连续节点的夹角i 白j 就会有一 个超口的区域。如果出现这样的区域，u 会以更大的功率广播。这种情况会一直持续到 u 的周围不再有这样的区域，否则的话节点u 以最大功率发射。 c b t c 算法如下： m 卜；发现的节点“的邻节点集 见卜o ；从返回的a c k 得知方向 p 。卜p o w h i l ep 。 d ( 甜2 ，v 2 ) d ( u 1 ，v 1 ) d ( u 2 ，v 2 ) 或者( j ( “i ，1 2 1 ) = d ( u 2 ，v 2 ) & & m a x i d ( u 1 ) ，i d ( v 1 ) ) m a x i d ( u 2 ) ，i d ( v 2 ) ) ) 或者( d ( u i ，u ) = d ( u 2 ，v 2 ) & & m a x i d ( u 1 ) ，i d ( v 1 ) ) = m a x i d ( u 2 ) ，i d ( v 2 ) ) & & n f i n i d ( u i ) ，i d ( v 1 ) ) m i n i d ( u 2 ) ，i d ( v 2 ) ) 权值函数d 保证了p r i m 算法的每一步中，关于最小权值边e 的选择是唯一的，因 此节点z ，构建的本地最小生成树瓦也是唯一的。 在节点建立的最小生成树生成了它的可见邻域之后，该节点就可以确定其邻节点。 为了方便讨论，下面对邻域关系和邻域设置做个说明。 邻域关系和邻域设置是指：节点v 是节点“的邻节点，如果( “，v ) ( 瓦) ，标记为 u v 。如果u v 同时v 一“的话标记为u 付v 。也就是晚，节点v 是节点a 的邻节点， 节点，在节点u 的最小生成树瓦上，与节点“距离是一跳远。节点“的邻域设置( “) 是 ( “) = v y ( q ) ：“寸v ) 。 上面所说的邻域关系不是对称的，也就是说u v 不一定意味着v 一甜。下面用图 2 3 来解释这一点。图2 3 旱面一共有6 个节点v = ( “，v ，w 。，w 2 ，嵋，w a ，这里 d ( u ，v ) = d d m ，d ( u ，心) 矗越，f 1 ，2 ，3 ，同时d ( v ，w ，) 吨戤， j = l ，2 ，3 ，4 。既然圪= 甜，v ，心 ，可以从乏推导出掰- - 4v 和“一心。同样 眦= “，