（通信与信息系统专业论文）分层无线自组织路由网络仿真分析.pdf

电子科技大学硕士学位论文 摘要 随着移动通信技术的发展和便携式终端设备的普及，对无线组网的便 捷性提出了更高的要求。无线自组织网络应运而生，它能够在没有传统网 络设备参与的情况下实现方便快速的无线组网，支持自组织的网络管理。 i e t f 的m a n e t 工作组研究的a d h o c 网络是目前讨论得最多的自组织网 络技术。 本课题涉及的分层结构无线自组织网络是一种结合了a dh o c 网络自 组织能力和移动蜂窝通信系统中移动用户接入方式的网络体系结构。它即 具有无线自组织网络组网灵活的特点，又能够象移动电话系统那样为终端 用户提供方便的接入服务和用户管理功能。因而在军事和民用无线数据通 信领域有广泛的应用前景。 本文首先对比了分层网络结构无线自组织网络和现有a dh o c 网络的 工作原理和各自特点。通过详细的讨论和仿真分析，对比了不同站点分布 情况下无线信道性能。包括不同分布情况下的网路连通性、链路跳数、信 道冲突情况和信道容量。同时，构造了完整的分层结构的无线自组织路由 网络仿真模型。验证了网络体系结构和关键技术的可行性，包括无线信道 工作方式、网络编址技术、网络路由过程。并通过仿真分析了分层结构的 无线自组织路由网络的路由负载、网络数据到达率和网络通信容量。 关键词：分层无线自组织路由网，无线信道容量，通信容量，仿真 电子科技大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fm o b i l et e c h n o l o g ya n dp o p u l a r i t yo fp o r t a b l e t e r m i n a l s ，t h e r e i sa ni n c r e a s i n gd e m a n do fq u i c kd e p l o y m e n to fw i r e l e s s n e t w o r k s i ns u c hat r e n d ，w i r e l e s ss e l f - o r g a n i z i n gn e t w o r k sa r ep r o p o s e d t h i s k i n do fn e t w o r k sc a nb e e a s i l yd e p l o y e d w i t h o u t e x i s t i n g n e t w o r k i n f r a s t r u c t u r e a m o n g a l lt h e s en e t w o r k s ，a dh o cn e t w o r kr e s e a r c h e db yt h e m a n e t w o r k g r o u po f i e t fi sm o s tf r e q u e n t l yd i s c u s s e d t h e l a y e r e d w i r e l e s s s e l f - o r g a n i z i n gr o u t i n gn e t w o r k ( l w s r n ) d e s c r i b e di nt h i s p a p e rh a s an e wn e t w o r ka r c h i t e c t u r et h a tc o m b i n e st h e s e l f - o r g a n i z i n gf e a t u r eo fa dh o cn e t w o r k sa n dt h e u s e ra c c e s sc o n t r o lo f c e l l u l a rn e t w o r k sw s r nc a nn o to n l yb ed e p l o y e de a s i l ya n df l e x i b l yl i k ea d h o cn e t w o r k s ，b u ta l s op r o v i d ee n du s e r sw i t hc o n v e n i e n ta c c e s sa n du s e r m a n a g e m e n tc o n s e q u e n t l y ，i ti sp r o m i s i n g i nm i l i t a r ya n dc i v i la p p l i c a t i o n i nt h ea r t i c l e ，w ec o m p a r et h ep r i n c i p l e sa n dc h a r a c t e r i s t i c so ft h ew s r n a n da dh o cn e t w o r k s b yc o m p u t e r s i m u l a t i o n ，w ec o m p a r et h ec h a n n e l p e r f o r m a n c eu n d e rd i f f e r e n tn o d ed i s t r i b u t i o n s o b j e c t sw e e x a m i n e di n c l u d e s c o n n e c t i v i t y ，h o pc o u n t ，c o l l i s o n so nc h a n n e la n dc h a n n e lc a p a c i t y i nt h e m e a n w h i l e ，w eb u i l d a c o m p l e t e s i m u l a t i o nm o d e lo fl a y e r e dw i r e l e s s s e l f - o r g a n i z i n gr o u t i n g n e t w o r ka n d v e r i f yf e a s i b i l i t y o fn e t w o r k a r c h i t e c t u r ea n d k e yt e c h n o l o g i e s ，i n c l u d i n go p e r a t i n gm o d eo fw i r e l e s s i n t e r f a c e ，a d d r e s s i n g a n dr o u t i n gi nl w s r nw es t u d yt h e p e r f o r m a n c eo f w s r ni nt e r m so f r o u t i n go v e r h e a d ，p a c k e td e l i v e r yr a t i o ，a n d t h e c o m m u n i c a t i o nc a p a b i l i t y a n d c o m p a r et h e s e r e s u l tw i t ht h a to fa dh o c n e t w o r k k e y w o r d s ：l a y e r e dw i r e l e s ss e l f - o r g a n i z i n gr o u t i n gn e t w o r k ，w i r e l e s sl i n k c a p a c i t y , s i m u l a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特j ；c l d n 以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 囱 日期：2 卯岁年6 月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：剖羞导师签名：錾垒：四 日期：年月日 第一章引言 1 1 课题背景 第一章引言 无线移动自组织互联网技术在过去的十多年里已经进行了大量 的研究。i e t f 的m a n e t ( m o b i l ea dh o cn e t w o r k i n g ) 工作组目前 正致力于无线移动自组织互联网路由算法的研究工作，提出了很多 可应用在无线网络上，能够适应网络动态拓扑变化的路由协议。 在m a n e t 工作组所研究的a dh o c 网络中，通常一个移动设备 既是主机又是路由器，除了自身的数据通信之外，每个节点还承担 着组网、为其它节点中继的义务和责任。 在共享信道方式情况下，m a n e t 工作组所提出的任何一种算法 都很容易产生相当大的组网开销，使网络的实际通信能力受到很大 限制。此外，a dh o c 网络中的移动节点既是端系统又是中继系统， 节点负担加重，并且由于移动节点需要具备特定的路由功能，a d h o c 网络中的每台移动设备上需要进行t c p i p 协议栈的修改，接入固 定i n t e r n e t 的普通移动设备加入a dh o c 网络中将无法通信，因此不 具有通用性。 本课题研究和设计的无线移动自组织互联网，是针对通用计算 机系统( 尤其是便携式计算机) 的宽带移动接入和使用互联网业务 的移动互联网。网络由起基站作用的无线路由器和移动终端构成两 级网络结构。自组织网络中的无线路由器通过无线信道沟通和自组 织，形成无线互联网络，实现网络的拓扑构成、中继与路由、接入 控制和用户管理等功能，为移动终端提供无线接入和通信服务。移 动终端实际上不参与网络的自组织和动态路由等，只使用网络提供 的可移动的通信服务。这样，无线网络中所有站点分成两个部分： 少量的无线路由器和较多的无线终端站点，在同样数目的无线节点 情况下，大大减少了参与白组织、动态路由算法的无线节点，也大 大降低了网络的组网开销。 1 2 仿真主要任务 本课题的仿真工作主要分为两个部分，对共享无线信道的仿真 分析、和对分层网络结构的仿真分析。对共享无线信道的仿真包括 在不同分布情况下网络连通性、无线链路跳数、无线信道冲突的仿 分层无线自组织路由网络仿真分析 真分析。通过这些分析可以帮助我们选择合适无线路由器数量。仿 真的另一个主要目的是建立分层结构的无线自组织路由网络仿真模 型。通过这一模型可以验证网络基本协议和方案的可行性，比如网 络路由、编址方式、信道工作模式、网络移动性支持等。同时通过 仿真可以对分层网络结构的总体性能做初步的评估，对网络设计的 优化和改进提供依据。 1 3 论文章节 下一章首先对比了分层网络结构和现有a d h o c 网络的工作原理 和各自特点，提出仿真目标。在第三章中对不同分布比例下连通度、 链路跳数、信道冲突和信道容量进行了详缅的讨论和仿真分析。第 四章介绍分层结构的无线自组织网络组网方案。第五章介绍网络仿 真模型的设计，包括功能模块的改造、站点模型构成和网络模型设 置。第六章对网络仿真结果进行了深入的分析，得出相关的结论。 2 第二章自组织网络技术 2 1a dh o c 网络 第二章自组织网络技术 a dh o c 网络是目前讨论的最多的自组织网技术。这种网络不需 要固定的基站设备和路由器，应此不依赖于蜂窝移动通信网络。网 络中的节点可在一定区域内随意移动并能于网络中的任意站点相互 通信。每一个节点都能实现路由器的功能而在网络中搜寻、维护到 另一节点的路由。自组织网可用在事故的突发现场以及人们希望能 迅速共享信息的会议、办公室等场所。 a dh o c 网络根据站点间的逻辑关系可以分为两种网络结构：平面 网络结构、分级网络结构。如图2 1 所示，左边的自组织网络是一个 平面结构的网络，而右边的则是一个二级结构的自组织网络。平面 结构中，所有节点地位平等，也被称为是对等式结构。与之相对的 分级结构中，网络被划分为多个簇( c l u s t e r ) ，每个簇由一个簇首 ( c l u s t e r h e a d e r ) 和多个簇成员( c l u s t e r m e m b e r ) 组成。这些簇首 在逻辑上组成了一个高级的网络，而在这个高一级的网络中又可 以分簇，形成更高一级的网络，直至最高级。任意两个不在一个簇 之内的簇成员之间的通信都要通过各自的簇首来中转。 图2 1 平面结构v s 分级结构 平面结构的自组织网络结构简单，由于站点间是对等的逻辑关系 无需任何的结构维护过程。源节点和目的节点之间可以存在多条路 径，当一条路径繁忙时，可能通过另一条路径继续通信。由于网络 中所有节点是对等的，原则上不存在瓶颈，所以比较健壮。平面结 构的最大缺点是网络规模受限。在平面结构中，每个节点都需要 知道到达其它所有节点的路由。由于节点的移动性。维护这些动态 变化的路由信息需要大量的控制消息。网络规模越大，路由维护的 分层无线自组织路由网络仿真分析 开销就越大。当网络的规模增加到某个程度时，所有的带宽都可能 会被路由协议消耗掉。所以平面式结构网络的可扩展性较差。 分级结构的最大优点则是可以有效控制路由信息量的膨胀，可以 支持更大的网络的规模，必要的时候可以通过增加新的簇或者增加 网络级数来提高整个网络的容量。分级结构中，簇内成员只需要维 护簇内站点间的路由信息，与簇夕 站点的通信交给簇首处理。即简 化了成员站点的功能，又使得簇内的网络管理信息量大大减少，节 省了网络开销。簇内成员无须知道其他簇的拓扑结构，一个簇的拓 扑变化不会被其它簇的节点感知，这就大大减少了网络中路由信息 对无线链路带宽的消耗。簇首的功能较为复杂一些，不仅需要维护 到达其他簇的路由信息，还要知道所有节点与簇的关系。网络中主 要的路由功能由簇首完成，大部分路由、管理信息在由簇首组成的 高级网络中传播。一般情况下簇首只是网络中的少数站点，在同样 规模网络的条件下分级结构的路由开销要比平面结构的小。如果簇 内通信的信息流量在整个网络的通信量中占较大比例的时候，更能 够明显提高整个网络的吞吐量。当然分级结构也有其缺点存在。首 先维护不同层次结构间站点的逻辑关系较为复杂。簇首站点如果由 事先指定，在站点移动情况下无法保证各个簇的规模相当：选举产 生簇首的算法又较为复杂，需要仔细设计。其次簇内的节点与簇外 的节点进行通信时必须经过簇头，所得到的路由不一定是最佳路由。 第三簇首的通信负担较重，容易成为网络中的通信瓶颈。 从上面的比较可以看出，平面结构和分级结构的自组织网络各 自具有不同的优势。平面结构的自组织网终结构简单，站点间的路 由较为灵活，不容易出现网络瓶颈。但是，在网络规模较大时路由 更新信息的负载较重造成通信容量的下降。平面结构更适合较小规 模的网络。分级结构通过路由信息局部化减小路由控制报文的开销， 提高了系统的吞吐量；通过增加新的簇分级结构可以支持更大的网 络规模，有较好的可扩展性；另外分级结构可通过簇首的管理功能 为网络提供用户接入控制和站点定位等辅助功能。 在a d h o c 网络当中，无论采用平面结构还是分级结构有一点是 共同的：所有站点共享一个物理信道。分级结构网络虽然能够限制 簇内部的路由信息向其它簇扩散，但是分簇和分级都只是限于站点 间逻辑关系而言，并不能隔离站点对物理信道的竞争。当网络中有 站点数量越大，站点取得信道资源就越困难，出现信道冲突的可能 性也相应增加。由于站点的通信距离限制，多数情况下a d h o c 网络 4 第二章自组织网络技术 中存在多跳路径。多跳网络中隐藏终端的存在使得站点难以区分无 线信道是空闲还是正被一个隐藏终端使用，物理信道冲突比有线以 太网和单跳无线网络中更为复杂。本论文将在第四章重点讨论多跳 网络中得信道冲突和无线信道容量问题。 2 2 分层网络结构 分层网络结构的设计借鉴蜂窝式移动通信系统( 如g s m 、 c d m a ) 的分层管理思想，结合a dh o c 网络的灵活的的组网特性， 形成移动互联网的网络结构。 分层网络结构由较多数量的无线用户终端和少量无线路由器组 成。无线用户终端是具有无线通信能力的通用计算机主机，我们称 之为无线主机。无线主机不参与网络动态拓扑维护工作不具有路由 功能，所有通信报文都交给无线路由器路由转发。所以无线主机无 需象分级a d h o c 网络中的簇成员那样安装相应路由程序和修改通信 协议栈。无线路由器的网络层功能与分级结构a d h o c 网络中的簇首 相当，即要维护与其它路由器之间的动态路由又要知道无线主机与 无线路由器的对应关系。同时分层网络结构中的无线路由器与簇首 又有明显的区别。a d h o c 站点都是单无线端口网络设备，无线路由 器具有两个不同用途的无线端口。其中一个端口用于与无线主机的 通信，无线路由器通过该端口提供用户接入服务，我们称之为站点 接入端口。另一个无线端口工作方式与a d h o c 站点的无线端口相同， 用于无线路由间的通信，我们称之为网络路由端口。无线路由器具 有网络接入和路由转发的双重功能。同时，无线路由器的两个端口 工作在不同无线信道上。所有无线路由器的网络路由端口工作在一 个单独的无线信道，保证骨干层有足够的网络带宽，降低出现网络 瓶颈的可能。不同无线路由器的站点接入端口工作在不同的无线信 道，接入到不同路由器的相邻主机间没有信道资源的竞争。 分层网络结构中，无线网点之间通过无线信道沟通，以a dh o c 方式自组织形成骨干传输网络( 如图2 - 2 ) ，为移动用户的通信提供 无线网点间的选路、i p 报文转发。同时，无线网点还负责实现与有 线互联网的互连和通信。象蜂窝式移动通信系统中的基站那样，无 分层无线自组织路由网络仿真分析 骨 接 无线网点。移动用户 图2 - 2 分层网络结构 线路由器通过站点接入端口在自己的周围形成一个无线覆盖区域， 为该区域中的无线主机提供接入服务。多个无线路由器构成一种蜂 窝状的覆盖区域。在此覆盖区域内的无线信道接入距离“最近”的 无线路由器，并且可在多个无线路由器的覆盖范围内自由移动，由 无线路由器上的路由算法来解决其在各个路由器之间切换的问题。 分层式无线自组织路由网络具有以下显著的特点。首先，网络 自组织能力强。自组织网络中多无线路由设备能通过无线信道相互 感知，快速掌握它们之间的拓扑结构及变化情况，形成具有路由、 中继功能的无线互联网络。此外，无线路由设备自动感知移动用户 的接入和离开，为移动终端提供移动方式的接入、路由和中继服务。 其次，有效降低了路由信息扩散量。由于无线主机不参与网络拓扑 的构成，只有站节点数量很小部分的移动路由器之间需要路由信息 的交互，有效降低了路由信息扩散对无线链路带宽的消耗。第三， 支持更大的网络容量、更好的网络扩展性。无线路由器间通信和站 点接入使用不同信道，而且各个路由器的接入信道也不相同，这样 将底层链路分割为几个互不干扰的信道，有效的降低了信道竞争、 减少信道冲突。因此，在同等规模下，分层结构的网络比a d h o c 有 更高的网络通信容量，更不容易出现网络瓶颈。通过增加新的无线 路由器可以方便的支持更大的网络规模。第四，支持通用t c p i p 协 议栈。网络面向通用无线主机提供接入服务，无线主机无需修改自 己的t c p i p 协议栈就可以通过该自组织网络进行通信和访问因特 网。 2 3 主要关心的问题 目前对无线自组织网络的讨论主要集中在a d h o c 网络上。讨论 第二章自组织网络技术 的重点是通过对比不同路由协议下a d h o c 网络中路由负载大小和数 据报文的到达率来评价这些路由协议的性能优劣。这些讨论中涉及 的网络在链路层上几乎都采用了i e e e 8 0 21 1 无线局域网技术。本文 希望通过对基于i e e e 8 0 21 1 技术的多跳共享无线信道中的网络冲突 和信道容量的分析对a d h o c 网络的通信容量极限得出客观的评价。 同时，我们按照分层无线自组织网络结构的要求在o p n e t 仿真软件 上构造了仿真网络模型。通过对网络中路由开销、通信报文到达率 和网络数据吞吐率的分析，并与a d h o c 网络对比，来评价分层自组 织网络结构的性能。 7 分层无线自组织路由网络仿真分析 3 1 仿真目标 第三章多跳无线信道仿真 在无线信道中，由于传播介质对信号能量的消耗以及信号能量 在空间中的的发散，信号功率随传播距离的增大迅速衰减。当信号 强度小于一定门限时，不能被其它站点接收。只有在定距离范围 内的站点才能保持正常通信。两个相同站点间可以通信的最大距离 称为站点的最大通信距离。对于理想环境下采用全向天线的站点， 站点的通信范围是以最大通信距离为半径的圆形区域。在本文的讨 论中假设站点的通信半径相等，这样两个无线站点是否可以直接通 信决定于站点间距离是否小于最大通信距离。站点具体分布情况直 接影响到网络拓扑结构、站点间的连接关系和无线信道的竞争情况， 从而影响到网络中各站点之间的通信能力和无线信道通信容量。所 以本章将从以下几方面分析站点分布特性对信道性能的影响： 连通性：由于站点的分布情况决定无线网络的拓扑结构，所 以在一定的分布情况下，某些站点可能无法跟网络中部分站 点通信。3 2 节将讨论在怎样的分布情况下有好的网络连通 性。 链路跳数：在多跳网络中不是所有站点间都可以通过无线信 道直接通信，需要其它站点的中继转发，因此网络中存在多 于一跳的无线链路。3 3 节讨论分布情况对链路跳数的影响。 无线信道冲突：多跳网络中随网络链路跳数的增加，无线信 道竞争和冲突碰撞的情况比单跳网络复杂，冲突避免也比单 跳网络中复杂。在3 4 节中分析多跳网络无线信道冲突问题。 无线信道容量：信道冲突限制了无线网络的信道容量，35 节将讨论不同分布下的无线信道容量。 为了便于讨论和比较，所有无线站点在一个圆形区域中随机均 匀分布。由于不同类型无线站点的通信半径不同，为了讨论有更广 泛的适用性我们用“网络分布比例”作为衡量网络分布大小的标准。 网络分布比例是该区域的半径与站点通信距离之比。 网络分布比例= 站点分布区域的半径站点通信距离 下面将分别对不同网络分布比例下的无线信道连通性、链路跳 第三章多跳无线信道仿真 数、无线信道冲突和无线信道容量进行讨论。 3 2 分布特性对网络连通性的影晌 32 1 连通陛及其衡量标准 无线网络中，如果两个无线站点可以不需要其他站点的中继而 直接通信，我们称它们相互连通。相反由于受通信距离的限制站点 可能处在其它所有站点的通信范围以外，因而不能与其它任何站点 连通，此处称之为“孤立站点”。孤立站点没有通信能力。无线网络 中还可能出现有部分站点内部相互连通却都不与网络中其它部分的 站点相连通。这两种情况都意味无线网络被割裂为相互不能通信的 多个部分。 为了方便对无线网络连通性的讨论定义了以下参数作为衡量网 络连通性的标准： 站点的连通度： 如果两个无线站点可以不需要其他站点的中继而直接通信， 我们称它们相互连通；与一个站点相互连通的站点数量我们 称为该站点的连通度。如果认为两个站点相互连通就是有一 条可用无线链路的话，站点的连通度体现了站点可用无线链 路的多少。 网络平均连通度： 一个无线网络中所有站点连通度的统计平均，它体现了整个 网络中无线链路的丰富程度。 站点的不可达度： 如果网络中存在两个站点它们即不能相互连通也无法通过 其它站点的中继而间接通信，我们称两个站点互不可达。对 一个站点，网络中与它不可达的站点数量称为站点的不可达 度。如果网络中任何站点的不可达度为零，就意味着全网可 达。 网络平均不可达度： 一个无线网络中所有站点不可达度的统计平均。网络平均不 可达度越接近0 网络的连通性越好。 平均不可达概率： 平均不可达概率等于网络不可达度除以网络中的站点数量。 它的它体现了网络中任意一对站点之间不可达的平均概率。 分层无线自组织路由网络仿真分析 连通度和不可达度从两个不同角度定量的反映了网络的连通性 性能，是我们讨论网络连通性的主要衡量标准。 3 2 2 影响连通度的因数 决定两个站点是否连通的条件是站点间的距离，所以站点分布 的疏密程度直接影响连通度的大小。为了便于分析我们假设一定数 量的站点在半径为的圆形区域内随机均匀分布，在此环境下来讨论 站点连通度。影响站点疏密程度的因数主要有两方面：是区域内的 站点数量，和分布区域的大小。我们用前面的网络分布比例作为衡 量分布区域的大小的参数。下面分别讨论两者对站点连通度的影响。 分布区域中的站点数量越多，站点的稠密程度越高，站点落在 另一站点的通信范围内的可能性更大。在一定的分布区域中网络平 均连通度与站点数量间的统计关系如下图所示。 图3 - 2 1 不同分布比例下的平均连通度 在分布比例一定的前提下，网络平均连通度随站点数量增多而增大， 两者间成正比关系。 同时可以看出平均连通度也受到分布比例大小的影响。当网络 分布比例即分布区域半径与站点通信半径之比小于等于0 5 时，无论 如何分布所有站点都在其它站点的通信范围内，网络是“全连通的”， 也就是“单跳”的网络。这时所有站点的连通度等于站点数量减一。 1 0 第三章多跳无线信道仿真 当网络分布比例大于05 时，网络变为多跳的。而且网络平均连通度 曲线的斜率随分布区域的增大而减小最终趋近于0 。而且在0 5 至2 的区域内平均连通度曲线的斜率下降最为显著。 平均连通度是体现站点连通度的一个重要参数，但是应注意到一 个站点少而紧凑的网络平均连通度也较小，一个有相同平均连通度 的大而松散的网络中可能有较多的孤立站点。需要对不同分布区域 大小、不同站点数量下站点连通度的统计分布特性进行分析。 下面分别讨论在网络分布比例位为l 和2 时，不同站点数量的 网络中连通度的统计分布情况。下图是分布比例为2 时，网络中的 站点数分别为8 、16 、3 2 时的连通度分布情况。横坐标x 为连通度， 纵坐标是连通度为x 的站点个数的统计平均值。 图3 - 2 ：2 分布比例2 时的连通度分布 站点连通度分布曲线类似于正态分布曲线，曲线的中轴是网络 的平均连通度。图中站点数为8 的分布曲线显示网络中平均有约两 个孤立站点( 连通度为0 ) ，可见连通性很差；而站点数为3 2 时出现 孤立站点的概率很小，站点连通度多在3 至9 之间，网络连通性很 好。站点数目为1 6 令时，出现孤立站点的概率较小，站点的连通度 主要分布在1 到5 之间。 分层无线自组织路由网络仿真分析 鞲 _ 袭 霸 牛 ， 、落然一 厂! ! 黧 7 二二 12 34567b91 d1 11 2 1 31 41 5 连通度 图3 - 2 - 3 分布比例l 时的连通度分布 我们对比一下分布比例缩小到l 时的连通度分布情况。三条曲 线对应的站点数量分别是4 、8 、1 6 。从图中可以看出，网络比例等 于1 时，网络中无线站点数量减少到4 个仍然有较好的连通性，站 点大多有1 到3 的连通度。站点数为8 个时已经很少出现孤立站点， 站点的连通度主要分布在3 到6 之间。网络的连通性很好。就1 6 个 站点而言，的网络比例为l 时，站点的通度较分布比例为2 时更高， 这是由站点分布更加集中引起的。 3 2 3 对网络不可达性的影响 前面的讨论中我们提到，无线网络中可能出现网络割裂的问 题。因此，一个站点连通度不为零，甚至可能有较大的连通度， 但是并不能保证它与与任意站点可以通信。而我们设计网络时总 是希望能够保证所有站点、至少是尽可能多的站点问可以通信， 无论他们是直接相通或者经过其它站点的中继。讨论不可达性正 是从反面来分析网络的连通性。 网络的不可达度与连通度紧密相关，网络中各站点间的的不 可达度低需要各个站点有好的连通度，而孤立站点与其它站点都 2 2 8 6 4 2 ， b 6 4 2 0 舵 。 伸 饰 他 ， 叫 耻 o 第三章多跳无线信道仿真 不可达。连通度受站点数量和分布范围的影响，不可达度也一样。 在分布比例小于05 的情况下，网络中所有站点相互连通的 所以不可达度一定为0 。下面讨论分布比例为1 和2 时站点平均 不可达度的统计结果。 蒿 不 器 站点数量 图3 - 2 - 4 网络分布比例1 时平均不可达度 坌星委丝皇丝堡墅圭里竺笪墨坌堑 一 图3 2 5 分布比例2 时的网络平均不可达度 从以上两个分布图中我们可以看出以下几点：首先，在相同 的站点数量下分布比例为1 的网络中站点的平均不可达度明显低 于比例为2 的网络，前者的网络连通性好于后者。第二，比例为 1 的网络不可达度低，并且随站点数量增多而降低，说明站点数 越多网络连通性越好。第三，在分布比例为2 的网络中，站点数 由4 到1 6 区域平均不可达度是上升的，是否表明连通性的下降? 有必要考查另一个参数一一平均不可达概率。它体现了网络 中任意一对站点之间不可达的平均概率。分布比例为2 、网络站 点数量在4 到3 2 之间取值的网络的平均不可达概率如下图。 1 4 平幕可达度 苎三垩墨壁歪垡笪堂堕塞一一 _ _ - _ - _ _ _ _ _ _ _ _ _ _ _ ，_ _ _ _ _ _ _ - 一_ _ _ _ _ _ _ _ _ _ _ - - _ _ _ _ _ _ _ _ _ _ _ _ - ，_ - _ _ _ _ _ _ _ _ _ 站点数量 图3 - 2 6 分布比例为2 时的网络平均不可达概率 由图可知：随站点数量增加，任意站点对之间不可达的概率是 下降的。所以网络连通性没有下降而是随站点数量增加而提高。 3 24 小结 上面的分析中，我们从网络连通度和网络不可达度两个方面对 不同分布比例和站点数量的无线网络的连通性进行了分析。两方面 的数据都表明：网络的连通性在站点数量的增加或网络分布比例缩 小的情况下得到提高。 对于给定了分布比例的网络，必须有足够多的站点数量来保证 网络的连通性。具体的讲：分布比例等于l 的网络中有四个以上的 站点就能保证网络有较好的连通性；分布比例等于2 的网络需要1 6 个以上的站点才能保证网络有好的连通性。 3 3 分布特性对无线链路跳数的影响 此处讨论的无线网络中，所有站点都工作在对等模式下，两个 站点是否可以通信由站点间的距离决定。站点问的连通关系是由站 平均不可达概率 分层无线自组织路由网络仿真分析 点的分布情况决定的，所以对等无线网络的网络拓扑也是由站点分 布特性决定的。我们主要讨论的是并非所有站点都能直接连通的无 线网络，因此网络中相互可达但是又不相邻的站点间存在至少一条 多跳链路。两个站点间的链路跳数由网络拓扑决定，所以对等无线 网络中的链路跳数情况也会受站点数量和分布比例的影响。 在以前的讨论中我们已经知道，在网络分布比例小于0 5 时网络 中所有站点都是相互连通的，所有站点间的链路都只有一跳。我们 重点讨论分布比例大于0 5 时对链路跳数的影响。 以1 6 个站点的网络为例。我们对站点分布比例为1 、l5 、2 三 种情况下，网络中任意两个可达站点间的链路跳数的统计结果如下： 无线链路跳数 图3 - 2 - 71 6 个站点不同分布比例下的链路跳数分布 从图中可以看到，在比例为l 比1 的网络中，由于站点分布 拥挤、网络连通度很高，每个站点都有较多的站点相邻，所以半 数以上的站点间只有一跳，而且绝大多数无线链路小于三挑。随 分布比例的扩大链路跳数分布情况向较高的跳数扩散，平均链路 跳数也随之上升。三种分布比例下的平均链路跳数分别是1 4 5 0 6 、 2 17 3 2 、238 4 3 。同时应注意到在网络分布比例扩大到2 比1 时， 各种跳数的平均链路条数的总和明显小于其他两种分布情况。这 霜牛盘螺籁诺淡嚣 第三章多跳无线信道仿真 是网络连通性下降引起的，此时站点间的不可达度上升，造成网 络中总的可达路由减少。 下图是三种网络分布比例下，不同站点数量时，对平均链路 跳数的统计结果。 站点数量 图3 - 2 - 8 不i 司分布比例f 的平均链路跳数 在站点数量小于6 时分布比例小反而有较高的平均跳数。这主 要是因为站点少时分布范围小的网络有好的连通性和较多的可达路 由的原因。站点数多于1 0 个时网络分布范围大的网络有较长的链路。 这是因为站点分散为更长的链路提供了可能。 从上图中还可以看出，网络中站点稀疏时，平均链路跳数随站 点数量增加而上升。因为站点增多使连通度提高，网络拓扑更复杂， 更可能出现多跳链路。当站点密集到一定程度以后，站点增加平均 链路跳数反而下降。这是因为网络最大路由半径受分布比例的限制 不能无限度的增大，限制了多跳链路；而在稠密的网络中添加站点 使单跳链路比例增加。 可见平均链路跳数分布的转折点是判定网络中站点过于稠密的 1 7 赫餐斑掣轷牛 分层无线自组织路由网络仿真分析 一个重要标志。同时网络中链路跳数大小还会信道冲突情况、信道 容量产生影响。下面几节将详细分析。 3 4 多跳网络中的无线信道冲突 3 41 无线网络的隐藏终端问题 在无线信道中，由于站点的发射功率和无线信道信号衰减的限 制，站点的通信距离总是有限的。无线信道中的隐藏终端现象如下 图所示。对无线站点1 而言，工作在同一个无线信道中的站点3 不 再站点1 的通信距离之内。由于接收不到站点3 发出的无线信号， 站点1 即不能通过无线链路与站点3 直接通信、也无法获知站点3 是否在发送数据。此时站点3 对于站点1 而言就是隐藏终端。在我 们讨论的多跳无线网络的链路层信道中必然存在隐藏终端现象。 在单跳网络中，一个站点发送数据时，共享该信道的其它站点 都可以检测到该信号，从而知道信道忙。因此冲突只发生在多个站 点发现信道空闲然后同时开始发送数据时。但多跳网络中由于存在 隐藏终端，站点发送的数据信号不能被隐藏终端检测到，因此隐藏 终端可能在该站点发送数据的过程也开始发送，结果造成信道冲突。 下图是一个共享信道的多跳无线网络，我们分析一下隐藏终端引起 碰撞的情况。 图3 - 4 - 1 多跳网络信道冲突 圆筐表示站点间连通关系，没有相连的站点互为隐藏终端。假 设站点3 正发送数据到站点2 ，同样在站点3 通信范围内的站点4 也 会接收到信号；站点1 因为接收不到3 的信号可能向2 发数据，与3 发出的数据冲突；同时站点5 需要向4 发送数据，然而对于站点4 来说站点5 发出的数据信号与站点3 发出的信号冲突。尽管站点4 空闲，但还是无法接收5 发出的数据。由此可见隐藏终端增加了站 点间冲突碰撞的可能，同时也使得引起信道冲突的情况更复杂。所 以，在共享式无线信道环境中，多跳网络比单跳网络更需要一种有 1 8 第三章多跳无线信道仿真 效的机制来避免信道的冲突。 3 42 无线局域网的冲突避免机制 8 0 21 1 网络节点的m a c 层均采用c s m a c a ( 具有避免冲突 的载波侦听多路存取) 协议。这一协议本质上与8 0 23 以太网用来管 理多点网络信息量的c s m a c d 协议( 具有冲突检测的载波侦听多 路存取) 相似。c s m a 是一种简单的先侦听后发送的协议，可以防 止同级节点中断彼此之间的信息传输。 按照c s m a 协议，一个希望传送有效信息帧的节点首先要侦听 信道上的信息。如果检测到该信道有d i f s ( 分布协调功能帧间间隔) 空闲，它就可以发送其有效信息帧。接收节点在收到有效信息帧之 后可利用s i f s ( 短帧间间隔) 来计算有效信息的c r c ( 循环冗余校 验码) ，并将其与帧中的相应值进行比较。如果两个c r c 一致，接 收节点就在s i f s 间隔之后发回一个短的确认帧。 如果发送节点在d i f s 内检测到信道在被占用，那它就一直等 下去，直到信道空闲时间等于一个d i f s 间隔和长度为若干时隙的 补偿间隔之和为止。如果在这补偿间隔结束之前信道又被占用， 则该节点就保留余下的补偿时间并将此时间用于下一个空闲周期。 因此，即使在随机补偿时间很长的脉冲串期间，各个节点都不会被 长时间封锁，而且它们每丧失一次使用信道的机会，它的优先权就 升高一级。如果网上有多个节点都在等待使用该信道，这种随机的 补偿时间间隔就可降低发生冲突的机会，因为两节点选择相同补偿 时间的概率很低。 在8 0 2l l 的c s m a c a 与以太网的c s m a c d 之间的一个重 要区别源于这样一个事实：在有线网络里，所有的节点可以通过共 用的传输媒体保证彼此之间都能进行通信；而无线网络则必须对付 隐藏终端问题。由于存在隐藏终端，c s m a 简单依靠监听确定信道空 闲的机制是不可靠的。同时站点也无法检测到由隐藏终端引起的信 道冲突。因此，8 0 21 1 无线网络依靠冲突避免协议来解 决隐藏终端 问题 使用c s m a c a 协议时，一个准备好传送有效信息帧的节点要 像上例那样侦听信道上的信息，当该节点发现信道空闲时，它就发 送一个r t s ( 请求发送) 帧给接收节点。r t s 报文含有一个与传送 有效信息帧所需时间相对应的持续时间字段。如果该k t s 报文没有 分层无线自组织路由网络仿真分析 发生碰撞冲突，接收节点在间隔s i f s 的时间后发送一个短c t s 包作 为回答。该c t s 报文中同样包含了持续时间字段。除源节点以外的 其它节点收到c t s 报文后，会在报文指定的时间内抑制自己的数据 发送。源节点收到c t s 报文后，间隔一个s i f s 后开始发送数据报文。 收到发送节点传送有效信息帧之后，接收节点发回a c k ( 确认) 信 号。这种信号交换过程抑制周围站点的数据发送，从而起到了预定 信道的作用。 图3 - 4 - 2 冲突避免机制交互沉程 虽然，在发送r t s 报文申请信道的过程中仍然可能出现碰撞， 但是r t s 报文只有2 4 字节，碰撞造成的数据损失和信道资源的浪费 相对于数据报文发生冲突时要小得多。 3 4 3 多跳无线网络信道冲突抑制 c s m a c a 的r t s c t s 机制在单跳网络环境下能够的冲突避免 问题。在参考文献【2 】中对r t s c t s 机制在单跳网络中的性能已有 详细的分析。但对于多跳网络环境下，尤其是有较大链路跳数时的 情况却少有详细的讨论分析。下面我们分析多跳网络环境下， r t s c t s 机制如何控制隐藏终端引起得信道冲突，和可能存在的碰 撞情况。 图3 - 4 - 3 网络结构如图3 4 - 2 所示。假设站点3 需要向站点2 发送数据， 此时其它站点都空闲；站点3 发送r t s 报文给站点2 ，站点2 发送 c t s 报文允许站点3 发送数据；站点1 收到2 发出的c t s 会抑制自 己发送任何报文，直到站点3 数据发送结束；站点3 接到2 发出的 c t s 报文，开始发送数据；站点4 因为检测到站点3 发出的信号所 以不会发送报文，此时只有站点5 和6 仍然可能发送数据。 2 0 第三章多跳无线信道仿真 图3 4 4 假设站点5 此时需要发送数据到站点4 ，先发送r t s 报文；在站 点4 处，站点5 发送的r t s 报文与站点3 的数据信号冲突，站点4 无法正确接收站点5 的r t s 报文；如果站点6 要发送数据到1 ，先向 站点1 发送r t s 报文；站点l 能够收到站点6 的r t s 请求，但是不 能发送数据，因此也不会响应站点6 的请求。可以看出网络中其它 站点的数据发送得到了有效的抑制，站点2 和3 的数据收发过程中 不会与其它站点发生信道冲突；虽然站点5 和6 发出的r t s 报文丢 失了但是损失的数据很少，数据报文发生碰撞时损失的网络资源会 大得多。由此我们可以看出c s m a c a 的r t s c t s 机制对于抑制多 跳网络中的信道冲突是有效的。 当然，由于多跳网络中站点的分布和站点收发状态的复杂性， 也会有r t s c t s 机制无法避免的冲突出现。下面通过举例说明两种 r t s c t s 机制无法避免的信道冲突。 情况l ： 开始信道空闲，站点l 需要向站点2 发送数据，于是向站点2 发送了r t s 报文。站点2 收到r t s 后准备在等待一个s i f s 时间间隔 以后发送c t s 报文予以响应。假设站点3 此时也有数据要发送到站 点2 。由于它监听不到站点1 的信号，所以仍然认为信道是空闲的。 如果在站点2 发送c t s 报文的同时，站点3 发出了r t s 报文( 如图 3 - 4 4 ) ，由于8 0 21 1 b 无线端口是单双工的，站点2 和站点3 都收不 到对方发出的报文。 图3 4 - 5 站点1 收到c t s 响应后开始发送数据。而站点3 因为没有收到 c t s 应答，随机回退一段时间后重发r t s 报文。如果站点1 的发送 2 l 分层无线自组织路由网络仿真分析 仍未结束，数据报文发生碰撞。 图3 - 4 - 6 只要网络中有超过一跳得无线链路，就有发生这种碰撞的可能。 但幸运的是，c t s 报文和r t s 报文长度都很小( r t s 报文2 4 字节、 c t s 报文2 0 字节) 信道中对应的传输时间短，两种报文在信道中发 生碰撞得概率相应也小。所以在较小跳数的无线链路上发生冲突碰 撞的可能性较小。 情况2 ： 本例是发生在较长无线链路上的信道冲突。 圈3 - 4 - 7 图3 4 7 中站点1 正在向站点5 发送数据；由于在站点1 的通信 范围内，站点2 自身不会发送数据，同时也不能接收其它站点发来 的报文，此处我们称站点2 的状态为“阻塞”状态；这时，站点4 需要向站点3 发送数据，于是发出r t s 请求；站点3 收到站点4 的 请求后发出c t s 报文予以响应同时希望抑制榴邻的站点发送数据； 但是在站点2 处，该r t s 报文和站点1 的数据信号发生冲突，并没 有被站点2 接收；站点4 随后开始发送数据；随后站点1 速据发送 结束，站点2 会发现信道出现空闲。假如站点2 这时