自由空间光通信网络拓扑形成及路由算法研究

课程设计中文题目自由空间光通信网络拓扑形成及路由算法研究英文题目FREESPACEOPTICALCOMMUNICATIONNETWORKTOPOLOPYFORMATIONANDROUTINGALGORITHMRESEARCH课程现代传输技术学院电子与信息工程学院专业通信工程姓名学号指导教师摘要自由空间光通信（FREESPACEOPTICALCOMMUNICATIONFSO）是一种采用红外激光承载高速信号的无线传输技术，具有成本低、容量大、设计简单、接入方便等优势。FSO网络既具有传统移动ADHOC网络的自组织性、独立组网能力、无中心抗毁性强等优点，又能利用FSO高质量的定向无线传输特性，实现网络物理层的收发控制。因此，在无线通信领域，FSO网络技术受到了越来越多的关注。本文在研究传统移动ADHOC网络拓扑及路由的基础上，结合当前FSO网络技术发展前沿，深入研究了FSO网络的初始化算法。主要分析了一种分布式拓扑形成算法，它通过迭代建立连接，直至形成一颗树形拓扑结构，目的是在军事应用中提供快速连通性。本文对该算法在VISUALC环境下进行模拟与仿真，并对其结果进行分析，提出改进方案，最终得到了最优拓扑。在此基础上又提出了一种有效的路由算法，并进行了图解说明。最后通过对算法的正确性论证，得出对于度受限的FSO网络初始化，自下而上最小度生成树算法是首选方法。关键词自由空间光通信，初始化算法，生成树，路由算法ABSTRACTFREESPACEOPTICALCOMMUNICATION（FSO）ISWIRELESSTRANSMISSIONTECHNOLOGYTHATSIGNALCONVEYBYINFRAREDLASER,ITHASLOWCOSTBUTGREATCAPACITYITISDESIGNEDTOBESIMPLEANDEXPEDIENTLYACCESSEDFSONETWORKHASTHESAMEADVANTAGESWITHTRADITIONALMOBILEADHOCNETWORKSELFORGANIZATION,INDEPENDENTNETWORKINGCAPACITY,NOCENTER,ANDINVULNERABILITY,ALSOTAKINGADVANTAGEOFFSOWIRELESSTRANSMISSIONCHARACTERISTICSOFHIGHQUALITYDIRECTIONALFORPHYSICALLAYERTRANSCEIVERSCONTROLITHASATTRACTEDMOREANDMOREATTENTIONINWIRELESSCOMMUNICATIONINTHISPAPER,BASEDONTHESTUDYOFTRADITIONALMOBILEADHOCNETWORKTOPOLOGYANDROUTINGCOMBINEDWITHTHECUTTINGEDGEDEVELOPMENTOFTHECURRENTFSONETWORKTECHNOLOGY,FSONETWORKINITIALIZATIONALGORITHMISRESEARCHEDDEEPLYMAINLYANALYZESADISTRIBUTEDTOPOLOGYFORMATIONALGORITHM,WHICHFORMACONNECTEDTOPOLOGYBYITERATIONSTHISALGORITHMISDESIGNEDTOENSURE“FASTCONNECTIVITY“RATHERTHANOPTIMIZINGOTHERMETRICSTHESIMULATIONENVIRONMENTISIMPLEMENTEDINVISUALC,BUTTOPOLOGYOBTAINEDISNOTIDEAL,THISPAPERPROPOSESTHEIMPROVEMENTPROGRAMANDEVENTUALLYOBTAINTHEOPTIMALTOPOLOGYALSOPROPOSEDANEFFICIENTROUTINGALGORITHM,ANDHADILLUSTRATEDINSTRUCTIONSFINALLY,PROOFOFCORRECTNESSOFTHEALGORITHM,THEBOTTOMUPMINIMUMDEGREESPANNINGTREEALGORITHMISAFIRSTSOLUTIONFORTHEINITIALCONFIGURATIONOFDEGREECONSTRAINEDFREESPACEOPTICAL（FSO）NETWORKSKEYWORDFREESPACEOPTICALCOMMUNICATION，INITIALIZATIONALGORITHM，SPANNINGTREE，ROUTINGALGORITHM目录1绪论311自由空间光通信网络的研究背景312国外自由空间光通信网络的研究概况313国内研究状况314自由空间光通信的技术特点32自由空间光通信系统原理及关键技术321FSO系统组成及各部分功能322激光天线技术323APT技术324高功率光源及高码率调制技术33移动ADHOC网络拓扑及路由研究331移动ADHOC网络简介332移动ADHOC网络的特点333移动ADHOC的拓扑结构334移动ADHOC网络拓扑形成算法335移动ADHOC网络的路由协议要求34FSO网络拓扑形成及路由策略341FSO网络特征分析342FSO网络拓扑形成算法3421算法模型3422算法步骤343FSO网络路由算法35算法实现与分析351算法实现352算法正确性证明3521近似值分析3522时间复杂度3523物理复杂度353算法总结3总结3参考文献31绪论11自由空间光通信网络的研究背景人类对光通信的研究起源于20世纪70年代，经过一百多年的发展，光通信已经成为当今社会信息传播的最重要、最常规的手段。光通信具有灵活、经济等优点，它的迅猛发展，使得21世纪将成为无线光通信大展宏图的辉煌时代。根据传输介质的不同，光通信又可以分为光纤通信，自由空间光通信和水下光通信。其中自由空间光通信（FREESPACEOPTICALCOMMUNICATION,FSO）又称为无线光通信（WIRELESSOPTICALCOMMUNICATION,WOO），是一种基于光传输方式、采用红外激光承载高速信号的无线传输技术，具有高带宽、部署迅速、费用合理等优势。它是以激光束作为信息载体，在大气中传送激光信号来实现点对点、点对多点或多点对多点间语音、数据、图像信息的双向通信技术。FSO技术具有与光纤相同的带宽传输能力，使用相似的光学发射器和接收器，甚至还可以在自由空间实现波分复用（WDM）技术，因此又有“虚拟光纤”之称。广义的FSO系统包括闷星际间光通信、星地间光通信和大气间光通信，狭义的FSO系统就是指大气间的无线传输。按现代网络的功能模块划分，整个电信网可以分为三个部分接入网、交换网和传输网。在90年代的光纤网络建设浪潮中，人们把研究重点主要放在光纤骨干网上。目前，我国许多城市已基本实现光纤到路边/小区。但用户接入网仍多为模拟双绞线技术所主宰，存在信号传输速率低、管子压力大、资源利用率低、配置不便等问题。这些都限制了电信新业务的发展，成为电信网优化的“瓶颈”，即“最后一公里”问题。为了适应这种需要，各种高数据速率的接入方式纷纷登场，其中既有传统技术又有新兴技术，如光纤电缆混合网（HFC）、数字用户环线（XDSL）、电缆调制解调器、以太网无源光网络（EPON）、吉比特无源光网络（GPON）、光纤、直播卫星系统（DBS）和本地多点分配业务（LMDS）系统等。其中（HFC）和（XDSL）的接入部分是采用带宽低得多的现有铜线设施，存在严重的瓶颈问题。解决这个问题的办法就是采用光纤和光无线，但光纤敷设的较长周期及高额投资限制了其普及，并且一旦用户离开，业务提供商想要收回投资就变得十分困难LMDS技术日渐成熟，传输距离远，但这种接入方式需要高额的初始投资（频谱许可证），对业务提供商而言，这种接入技术并不经济。相比较而言，FSO技术既能提供类似光纤的速率，又无需在频谱等稀有资源方面有很大的初始投资。另外，激光技术的进步已经使耐用可靠的器件变得很便宜，大大降低了FSO设备的造价。因此，在目前许多企业和机构都不具备光纤线路，但又需要较高速率的情况下不失为一种解决“最后一公里”瓶颈问题的最可行的解决方案。自由空间光通信最初的研究，主要是用于科学研究目的，而在商业方面的应用最近几年才兴起。作为当今十大电信热点技术之一，FSO技术受到越来越多企业以及运营商的重视，将成为今后构筑电信网的一项重要技术。12国外自由空间光通信网络的研究概况国际上自由空间光通信技术的研究是综合地面、飞机、卫星等方面进行的，从事这方面研究的主要机构在欧洲、日本、美国、韩国、俄罗斯等一些国家。比较有代表性的有欧洲航天局（EUROPEANSPACEAGENCY）、美国宇航局（NASA），LIGHTPOINT公司、ASTROTERRA公司、TERABEAM公司、AIRFIBER公司等。美国是世界上最早研究星际与自由空间光通信系统的国家，也是技术最前沿的国家。主要研究组织是美国空军和美国国家航空航天局（NASA）。从20世纪80年代到1994年期间，美国空军支持麻省理工学院林肯实验室建立起了高速星间光通信实验装置LITE（LASERINTERSATELLITETRANSMISSIONEXPERIMENT）。该实验采用8英寸口径的望远系统和30MW的半导体激光器，模拟星际间通信距离可达40000KM，数据率达220MB/S。由空间与导弹防御司令部和弹道导弹防御组织共同资助的STRV2星一地激光通信计划的两个地面实验终端已加工装配完成。计划在低轨道卫星与固定地面站间建立光链路，数据率将达到1GB/S。美国宇航局于70年代初也开始了激光通信的研究，主要从事GEOGEO链路高码率通信和低空链路的低码率通信的研究。在低码率通信中涉及到定位系统、光信道、激光器、探测器等技术领域，以后逐步扩展到LEOLEO,LEOGEO,LEO一地面站和LEO飞机的光通信链路，又进行了一些其他演示系统和关键技术的研究，其代表性光通信演示系统LCDSLASER传输数据率750MBPS，空对地演示系统、大气能见度监测计划等。目前正在进行光通信演示系统以及窄带激光滤波器、高功率激光器及空间和地面的激光卫星跟踪网络的研制。13国内研究状况和国际相比，我国的研究相对单一，就目前的水平来说，相距国外还有一段距离，特别是在移动中的FSO技术，还没完成突破。但对激光大气通信技术的研究起步并不晚，早在20世纪70年代就开始了大气激光通信的研究。进入90年代后，随着国际上大气激光通信的复苏以及市场的需求，大气激光通信得到有关专家和决策者的重视，也逐渐加紧了这方面的研究。1971年，中国电子科技集团公司第三十四所开始了激光大气通信技术的研究，1974年推出了ND。YAG激光大气通信系统实验样机并成功进行了外场实验，通信距离约13KM。1997年4月三十四所曾派人员到俄罗斯，就激光大气通信技术及应用情况进行了实地考察。它的样机在2001年2月由主管部门进行设计定型，现在已经有部分投入试用。中国电子科技集团公司第三十四研究所经过近几年的努力，已成功开发出了一系列的FSO设备，如专用网接入系列、以太网专用系列、图像传输专用系列、GSM信号传输系列等。随后，北京邮电大学、电子科技大学，武汉邮电研究院以及合肥、大连、长春、北京等地的部分单位也相继展开了对大气激光通信的研究。目前，中国宽带服务供应商长城宽带网络公司（GWBN）宣布将选用TERABEAM的自由空域光通信产品FSO来拓展其在中国的15个城市的宽带网络，通过TERABEAM的系统，GWBN将为大中型商业用户和大型住宅社区提供可靠的宽带服务，尤其是光纤和光缆很难到达或者敷设起来成本昂贵的地方。中科院成都光电技术研究所引进外国公司先进的激光器及其附属电路，利用自己在光学器件上的优势，研发出了工作波长为850NM、能够传输1公里和4公里两种距离的两款产品。14自由空间光通信的技术特点相比于微波通信、铜缆、光纤等其他通信方式，FSO的主要优势是（1）频带宽、速率高、容量大（2）频谱资源丰富、无需频率许可（3）透明的传输协议（4）传输安全、保密性好（5）部署链路（6）成本低廉自由空间光通信技术的不足（1）传输距离有限（2）天气影响通信质量（3）对准困难（4）激光信号对人体安全的威胁2自由空间光通信系统原理及关键技术21FSO系统组成及各部分功能一个FSO通信系统的设备组成，根据通信距离，激光器调制方式的不同而有所不同，结构的繁简程度也有很大差别。根据自由空间光通信的技术特点及要求，光学通信终端主要由激光发射系统、接收系统、光学天线、ATP系统等组成。本文所研究的FSO系统主要由链路信道设备、通信控制器、交换机和用户终端等组成。信道设备包括激光波段的发射机、接收机、天线及APT系统，对应每个链路一套，主要实现物理层的功能；通信控制器主要实现链路层的功能；交换机主要实现网络层的功能；用户终端实现运输层和应用层的功能。22激光天线技术作为空间光通信中光束控制系统的重要组成部分之一的光学天线，直接影响空间光通信的工作质量。光学天线是一个通过折射一反射光学实现的物镜系统，可视为一个能够接收自由空间特定波长微弱光信号的物镜。其基本要求是（1）光天线有较大的入口直径，能最大限度地收集来自光源的信号。（2）光学天线的分辨率与探测器的分辨率应该相匹配。（3）选择合适的视场，大视场加大口径，使得通光口径更大，有利于接收更多的光辐射。（4）光探测器是一个具有低通特性的装置，所以光学天线应该具有较好的低频响应特性。（5）光天线应该有消除杂散光的设置。系统要维持通信链路的高质量通信，需要较高的发射功率，但从人眼的安全方面考虑，激光的发射功率又不能太大。综合考虑简单易实现的单发单收和抗衰减干扰不易实现的多发多收等情况，我们采用多个发射天线一个接收天线，即同一基带信号调制到多个功率较低的光束上同时发射。由于发射的光束具有一定的发散角，这几个光束在较远的地方合在一起能满足通信要求的功率，而在较近的地方光束是相互分开的，也就不会对人眼造成伤害。多个发射光束还有其他好处，如可以减小障碍物（如鸟）的阻挡，降低大气湍流闪烁效应的影响等。23APT技术自由空间光通信链路是点到点的链路，它可以作为固定设备安装在高楼之间进行通信，也可作为无线移动设备随时开通。一个自由空间光通信系统在进行数据传送之前，必须确定发送端光信号被接收端光检测器正确接收，这意味着在需要克服传输通道上的各种效应之的同时，还必须使被发送的光场正确对准接收机。同样接收机探测器也必须按照发送光场的到达角度进行调节。接收机确定入射光束到达方向的操作被称为捕获（ACQUISITION），使发送机瞄准一个恰当方向的操作叫做瞄准（POINTING），在接下来的整个通信期间保持对准和捕获的操作称作跟踪（TRACKING），三者简称为APT技术。APT系统的主要技术指标要求有系统搜索范围、搜索对准时间、信标光束散角、信号光束散角、光束对准精度，系统频率响应（带宽）以及天线安装初始误差。APT技术是保证实现空间远距离光通信的核心技术之一。24高功率光源及高码率调制技术（1）光源的选择激光器光源用来产生激光信号，并形成激光束射向向量空间。为提高通信性能指标，往往采用加大光源发射功率的方式。但这样也会带来很多坏处，如对人眼的伤害以及光源使用寿命等问题。所以，光源的选择非常关键，一般在选择时主要考虑以下几个方面波长应该选择在通过率良好的大气窗口；发射光功率要考虑到人眼的安全；要考虑激光器的输出频率稳定性、光束方向稳定性、输出光功率的稳定性；光源的工作寿命；出射光束窄、质量好、工作频率高等。目前用于空间光通信的激光器主要有三类二氧化碳气体激光器，输出功率最大，但体积大，寿命短，比较适合于卫星与地面之间的无线光通信；激光泵浦NDYAG固体激光器，工作波长1064NM，但难于实现，是未来光通信的研究方向之一；二极管激光器，具有高效率、体积小、重量轻、结构简单等优点，可以采用直接调制方式，并且可以借助于已经成熟的光纤通信技术。所以目前很多自由空间光通信系统都采用这种激光器作为光源，但因其发射光功率低，所以只适合短距离的无线光通信系统使用。（2）调制方式的选择目前，无线光通信系统可采用的调制方式主要有两类，即广泛采用的内部IM/DD制式和相干调制制式。现分述如下内部IM/DD制式采用此种调制方式的无线光通信系统设备是在其光发射机中直接用准备传输的信号调制光源的某个参数，即用准备传输的信号去调制半导体激光器的电流，从而实现对光源的直接调制在接收端则对接收信号做直接检测。相干调制制式相干调制是相干光通信系统的核心技术，相干光通信是在发送端采用相干调制，在接收端采用外差解调的光通信系统。也即外调制/外差检测制式。3移动ADHOC网络拓扑及路由研究31移动ADHOC网络简介ADHOC一词源于拉丁语，是“特殊的，临时的”意思。无线ADHOC网络是一种特殊的没有类似蜂窝移动通信系统中预先部署的网络基础设施支持的，完全由一组带有无线收发装置的移动终端组成的一个多跳、临时性自治系统。ADHOC网络的前身是分组无线网（PRNET,PACKETRADIONETWORK）。ADHOC网络最初应用于军事领域，对它的研究源于战场环境下分组无线网数据通信项目的需要，在1972年，美国DARPA（DEFENSEADVANCEDRESEARCHPROJECTAGENCY）启动了分组无线网（PRNET,PACKETRADIONETWORK）项目，研究分组无线在战场环境下数据通信中的应用。在1983年和1994年进行了抗毁可适应网络SURAN（SURVIVABLEADAPTIVENETWORK）和全球移动信息系统GOMO（GLOBALINFORMATIONSYSTEM）项目的研究。主要研究如何将PRNET的成果加以扩展，以支持更大规模、更高抗毁性的网络。此外，还要开发能够适应战场快速变化环境需要的自适应网络协议等。1991年5月，IEEE802。11标准委员会采用了“ADHOC网络”一词来描述这种特殊的自组织、对等式、多跳、临时的无线移动通信网络，ADHOC网络就此诞生。ADHOC网络中，每个移动终端兼具路由器和主机两种功能，可以通过无线连接构成任意的网络拓扑。作为路由器，终端需要执行相应的路由协议，并根据路由选择策略参与报文的转发和路由表的维护工作作为主机，终端需要运行面向用户的应用程序。这种网络可以独立工作，也可以接入INTERNET或无线蜂窝通信网络中。但ADHOC网络一般不适于做中继网络，它只允许信息收发于网络内部的节点，而不会让来自外界的信息穿越本网络。ADHOC网络同时具备移动通信网络和计算机网络的特点，可以看作是一种特殊的移动计算机网络。32移动ADHOC网络的特点无线ADHOC网络继承了一般无线移动网络的特性。和常见的无线局域网及有线固定网络相比，具有以下特征（1）无中心和自组织性ADHOC网络没有严格的控制中心，所有节点地位平等，是一个对等式网络。网络中的节点通过分布式算法来协调各自的行为，无需人工干预和任何其它预置的固定网络设施，网络中的节点可以随时随地的加入或离开网络，任何节点的故障都不会影响网络的整体运行，具有很强的抗毁性。（2）动态变化的网络拓扑ADHOC网络中，节点能够以任意速度和任意方式在网中移动，并可以随时关闭电台，加上无线传播条件随时间和空间不断改变，无线发送装置的天线类型多种多样、无线信道间的互相干扰、发送功率的变化、地形和天气等综合因素的影响，这些都使网络拓扑结构变化频繁和不可预测。移动终端间通过无线信道形成的网络拓扑随时可能发生变化，而且变化的方式和速度都难以预测。（3）有限的无线链路带宽由于ADHOC网络采用无线传输技术作为底层通信手段，而无线信道本身的物理特性决定了它所能提供的网络带宽要远低于有线信道。此外，考虑到竞争共享无线信道产生碰撞、多址接入、多径信号衰减、噪音干扰和信道间干扰等因素，移动终端最终得到的实际带宽远远小于理论上的最大带宽值，以致在网络中出现拥塞情况。（4）安全性较差由于采用无线信道、有限电源、分布式控制等技术，无线移动ADHOC网络更加容易受到被动窃听、主动入侵、拒绝服务、剥夺“睡眠”等网络攻击。这些情况在军事应用中都要得到高度的重视。因此，信道加密，抗干扰，用户认证，密钥管理，访问控制和其它安全措施都需要特别考虑。（5）移动终端的有限性ADHOC网络中的移动终端具有便携、轻便灵巧等优点，但是也存在固有缺陷。例如依赖电池供电、能量十分有限、内存较小、CPU处理能力低，从而给应用程序设计开发带来一定的难度。同时屏幕等外设较小、功能受限，不利于开展功能较复杂的业务。（6）网络的可扩展性不强INTERNET网络由于采用了TCP/IP协议中的子网技术，使其具有很强的网络可扩展性。而动态变化的拓扑结构使得具有不同子网地址的移动节点可以同时处于一个ADHOC网络中，所以，子网技术所带来的可扩展性无法应用于ADHOC网络环境中。（7）多跳路由ADHOC网络的节点因发射功率的限制，节点的覆盖范围有限。当它要与其通信覆盖范围之外的节点进行通信时，需要中间节点的多跳转发。不需要专用的路由设备，每个节点都可以充当路由器。33移动ADHOC的拓扑结构随着移动网络技术的迅速发展，网络功能越来越强大，网络规模和网络结构越来越复杂。那么，对一个移动ADHOC网络实现网络管理如系统配置、性能、故障处理等情况，首先就要知道整个网络的全局拓扑图。拓扑结构图作为一个系统的重要模型，在整个网络的控制和管理上起到重要的基础性作用。根据ADHOC网络的特点和作战环境需求，有中心控制节点的拓扑结构显然不适合，所以ADHOC网络不适合采用集中式控制结构，一般采用两种分布式结构平面结构（如图31）和分级结构（如图32、图33）。在平面结构中，所有节点地位平等，也被称为是对等式结构。与之相对的分级结构中，网络被划分为很多个簇（CLUSTER），每个簇由一个簇头和多个簇成员组成。这些簇头又构成了一个高一级的网络，在高一级的网络中，又可以分簇，形成更高一级的网络，直至最高级。任意两个不在同一个簇内的簇成员之间的通信都要通过各自的簇头中继。簇头可以预先指定，也可以由节点使用算法自动选举产生。图31平面结构图32单频分级结构图33多频分级结构平面结构平面结构的无线移动ADHOC网络比较简单，无需任何的结构维护过程。源节点和目的节点之间可以存在多条路径，因此可以选择最佳路由进行数据传输，进而能够将网络带宽充分利用。网络中所有节点对等，不存在瓶颈，健壮性也很好。但其最大的缺点是网络规模受限。在平面结构中，每一个节点都需要知道到全网节点的路由信息，如果网络的规模很大，节点很多，那么要进行网络的管理和路由维护等工作需要耗费大量的开销。当网络的规模到达一定程度时，几乎网络的所有带宽都用于拓扑维护，使得网络的扩充性很差。分级结构分级结构的网络又可以分为单频分级和多频分级两种。单频率分级网络所有节点使用同一个频率通信，为了实现簇头之间的通信，要有网关节点（同时位于两个簇头通信范围内的节点）的支持。不同级采用的通信频率不同。高级的节点同时处于多个级中，有多个通信频率，用不同的频率实现不同级的通信。在一个两级网络中，簇头节点都有两个频率。一个频率用于簇头与本簇成员之间的通信。而另一频率用于簇头之间的通信。分级网络中的每个节点地位平等，都可以通过适当的簇头选举算法成为簇头。分级结构的优点是，网络规模不受限，可扩展性好，必要时可以通过增加簇头的个数和级数来扩充网络容量。在分级结构中，节点的功能简单，不需要维护到全网所有结点的路由信息，所以进行网络管理的开销小。但其也有缺点，首先，网络要执行簇头节点选举算法，这就增加了计算复杂性其次，普通节点之间通信是通过簇头来进行中继转发，这样得到的路由不一定是最佳路由再者，簇头作为中继转发节点可能成为网络的瓶颈。综上所述，当网络的规模小时，可以采用简单的平面结构；网络规模较大，需要实现的功能复杂时，可以采用分级结构。34移动ADHOC网络拓扑形成算法拓扑形成算法是指发现网络中的各个元素单元，且确定各个元素单元之间的互连关系，包括路由器、网桥、交换机、以及主机和子网等各种互连设备，也称为网络初始化算法。拓扑形成首先要发现如下的信息节点地位置信息、每个节点与其邻节点的关系、节点所属的簇、簇头之间的关系、节点的剩余电源情况、数据链路情况以及节点的失效状况等信息。拓扑形成算法应该使网络拓扑满足以下一个或几个特征（1）连通性连通性是拓扑形成算法中优先考虑的问题，为了实现节点间的互相通信，生成的拓扑必须保证连通性，即任意两个节点之间都存在用于发送消息的路径。连通性是任何拓扑形成算法都必须保证的一个性质。目前，对连通性的研究主要有两种方法基于概率统计的方法和基于图论的方法。（2）对称性对称性指如果从节点S到节点D有一条边，那么一定存在从节点D到节点S的边。（3）平面性平面性指生成的拓扑中没有两条边相交。（4）节点度数有上界度数是指在生成的拓扑中节点的邻居个数。结点度为N意味着该结点得有N套收发信机。N值大，系统成本高；N值小，网络的连通性就差，网络出现隔离的概率也大。因此需要研究在给定网络结点总数N的情况下，每个结点的度N为多少比较合适的问题。（5）健壮性由于ADHOC网络的拓扑是动态变化的，故要求拓扑形成算法不仅能在初始时建立满足某种优化目标的网络拓扑结构，而且在拓扑发生变化时，算法能够重构网络，保障网络的连通性，这一点对于移动ADHOC网络尤其重要。常用的拓扑形成算法有RNG（CONSTRAINEDRELATIVENEIGHBORHOODGRAPH），GG（GABRIELGRAPH），MST（MINIMUMSPANNINGTREE）等。35移动ADHOC网络的路由协议要求ADHOC网络是一个多跳的临时性自治系统，具有动态拓扑、有限带宽、终端受限、存在单向信道等特点。网络中结点的无线通信覆盖范围有限，但每个节点都具有路由器的功能，可以为两个无法直接通信的移动结点进行分组转发来实现数据通信。网络内结点之间通过多跳数据转发机制进行数据交换，需要路由协议进行分组转发决策。所以，路由问题成为ADHOC网络研究与应用的关键和难点，路由协议的设计也提出了许多具体而严格的要求，主要有以下几点（1）收敛迅速ADHOC网络的拓扑结构是动态变化的，这就要求所设计的路由协议必须对拓扑的变化具有快速反应能力，路由算法能够快速收敛，收敛是所有路由器对最佳路径达成一致的过程。收敛的快慢就决定了目的节点是否可达。（2）控制管理开销小ADHOC网络中无线传输带宽有限，实现分组转发的控制管理难免会消耗掉一部分带宽资源，为了有限资源的有效利用，路由协议应能高效的提供其功能，尽量减少不必要的开销。（3）避免无穷计算由于移动ADHOC网络的特殊性，网络中会经常出现链路中断或链路连接失败的情况，这就要求需要多次执行的路由算法能够避免无穷计算。（4）满足稳定性、健壮性稳定性是指当网络出现超负荷或者因局部出现故障某条路径不通时，依然可以通过其他路径进行数据通信，不会造成网络拥塞或虚电路中断的情况。健壮性（鲁棒性）是网络系统生存的关键，是指网络在异常和危险情况下，网络中的某些参数发生摄动，但网络仍能维持某些性能不变的特性。（5）提供无环路由ADHOC网络拓扑结构的动态变化，会使网络中节点路由信息更新不一致，这时运行路由算法会容易产生路由环路。所设计的路由协议应能尽量避免这种情况。（6）对终端性能无过高要求ADHOC网络中的移动终端具有便携、轻便灵巧等优点，但也有能量有限、内存较小、CPU处理能力低等缺点，因此，所设计的路由协议不能对终端性能要求过高。4FSO网络拓扑形成及路由策略41FSO网络特征分析在FSO网络中，网络的每一个结点都有N套收发设备。结点每发现一个相邻结点或跟某个相邻结点建立连接后就跟踪不放，直到结点移动出天线的射程范围。本文考虑网络规模小，网络结点之间的相对移动性缓慢的情况，由此，我们得出FSO网络的特征（1）网络规模比较小；（2）拓扑动态变化，但变化比较缓慢；（3）采用无中心网络结构；（4）能随时随地以自组织的方式进行独立组网；（5）具有良好的隐蔽性，不易被敌方截获；我们知道，FSO网络采用移动ADHOC网络的组网方式，但它与传统的移动ADHOC网络不完全相同。FSO网络采用方向性强的自由空间光通信技术实现网络物理层信号的收发，而传统的ADHOC网络的物理层则采用信号功率全向散布的RF技术来实现信号收发的。这种物理层技术的不同使得网络特性也不同，以下我们对FSO网络和传统的基于RF的移动ADHOC网络两种网络技术进行了深入分析，并以表格的形式给出两者之间对比关系如表41所示。42FSO网络拓扑形成算法421算法模型在现代通信领域，通过激光器发出的直线激光束进行的通信被称为无线光通信或自由空间光通信。这种技术的主要优点是高数据率和安全性。实验证明，一个结点的发射机可以发射波长非常小、方向性好的窄激光束（如1550NM的光波），通过APT技术指向接收机。根据不同的天气和大气的遮盖，激光束可以从几米到数公里。并且具有很强的抗截获性。我们将整个FSO网络抽象成由基站和基站间的点到点的光链路组成。在这个模型里最初，在网络中的任何点之间没有点到点的激光链路；每个结点能够接收和发射简单的由信标光（全向或定向信标）或其他的信号系统（GPS）发射的信号，来检测潜在邻居结点的位置。每个网络节点有个鱼眼镜头，用来检测指定距离内的信标（BEACONS）。利用信标和GPS系统的目的是为了建立潜在链路图，从其中推导出最小度生成树；表41FSO网络与传统ADHOC网络对比FSO网络基于RF的传统移动ADHOC网络信道特性带宽丰富的独享信道带宽很有限的广播信道，存在信道竞争和结点间碰撞的问题安全性信号功率仅在目标结点所在方向的小范围内散布，通信的隐蔽性强，且不会给其他方向的邻结点通信带来干扰信号功率全向散布，易于被窃听和恶意干扰，因此安全性差，并且会给邻结点带来干扰能量制约终端几乎不需考虑能量问题移动终端靠电池供电，需节能措施，网络各层协议设计都要等能量因素的制约节点的计算和处理能力较强弱节点的度每个结点处有N套收发信机，结点的度为定值结点度是变化的。因为每个结点处仅有一套收发信机，任一时刻仅能与一个邻结点通信，会发生碰撞节点的成本与复杂性高低每个结点可以通过它的鱼眼镜头发现那些能够接收到它的信标信号发出的HELLO信息的节点。根据尺寸、重量、功率以及与移动平台有关的成本参数的情况,每个结点的收发器数量是受限的。如果每个节点代表一个飞机或其它移动物体，度的限制更严格每个发射机与接收机配对，并且每对发射机和接收机指向同一方向，这样使得每条链路都是双向的。FSO网络的连通性问题可以转换成图表问题，就是最小度生成树问题。给定一个可行的图表G（V，E）（V代表顶点个数，E代表潜在的链路数），来建立一棵生成树，并且这棵生成树的最大度数在G的所有生成树里最小。422算法步骤“自下而上”的算法FUEL解决使用定向天线进行网络初始化的问题。首先我们做如下假设（1）所有节点都有一个全网唯一的ID；（2）所有节点都可以通过一定方式获取周围一定范围内其它节点的信息，包位置和ID；（3）如果节点A通过上文中的方式可以“看到”节点B，则节点B也可以“看到”节点A；（4）每个节点的度（即最大连接数）为K；具体的算法描述如下第一步每个节点寻找另外两个节点进行连接与自己有潜在链路的较小最大ID的节点和较大最小ID的节点，并将自己和天线指向该节点。较小最大即所有比自己M小的节点中ID最大的节点，较大最小即所有比自己M大的节点中M最小的节点。如果这些边能够形成生成树，则算法终止，否则会形成几个组，算法进入第二步。在第一步里，通过信标信号，每个节点能够记录与它有潜在链路的节点的ID和位置信息。信标信息包括了节点ID和位置信息。通过在第一步中的信标信息的交换，每个节点能够通过最大最小选择算法来找到与它有潜在链路的较大最小M和较小最大ID节点。结果如上两所示，虚线代表潜在链路，实线表示收发器到收发器链路（树的边）。第二步经过第一步之后，网络中所有的节点会分成若干组，如图43所示。我们给每个组分配一个M，不失一般性，我们将每个组中所有节点的最小ID作为组ID。组内节点通过已经建立好的定向连接交换信息，这样每个节点都可以获得组内各节点的信息。之后进行下面的步骤A到D，每个组寻找其他组来形成一棵树。在每次迭代中，每个组Z选择其他两个组S和L作为潜在组来合并，在选择组S时也包括了要选择Z,S两个组进行连接的节点，同理L也一样。A标记备选节点组内所有剩余度为K1或可以通过“改善”（当度是2的时候，这步可以跳过，因为将一个节点的度从2减少到1是没有意义的）将自己的剩余度变为K1的节点称为备选节点，如果一个备选节点可以“看到”其它组的备选节点，则该节点称为“真备选节点”（简单起见，下面的备选节点即指“真备选节点”）。在此步骤中，一个备选节点会发送一个简单的信标信号。不同组之间的节点通过信标信号只交换备选信息。一旦它们意识到自己是真备选节点，这些真备选节点会将标有“真备选”标签的自己的M通过高数据率激光通信链路发送给同组中其他节点。B选择组由于组内所有节点都获取了全组节点的信息，这样就可以计算出所有与本组的备选节点有潜在链路连接的组ID，从这些组中选出与本组相比，较小最大和较大最小的组，并设较小最大的组为S，较大最小的组为L。信标发送通过一个备选节点包括它的组ID和“我是备选节点”信号。在步骤B里，每一个备选节点都应该告诉其他的备选节点，哪些属于同一个组，哪些组与它有备选到备选的链路。然后，备选节点会比较这些组ID，得到最小较大ID组和最大较小ID组。这样选出来的组ID将会被告诉给每一个备选节点。所有这些信息通过高数据率激光通信链路发送。C选择节点选择好要合并的组之后，每个组要指定两个节点执行与选择的组进行合并的任务。设本组ID为Z，选择的方法如下组Z中与组L有备选到备选链路的最大ID节点为A，组L中与A有备选到备选链路的最小ID节点为C，A与C互相通信。这一步分为两小步，第一步，如果A的度为K，它的度可以减少到K1，通过“改善”，删除与A关联的一条边。第二步，A指向C。组S中与Z有备选链路的最大ID节点为R,Z中与R相连的最小ID的备选节点为B，则B指向R（如果B的度为K，减为K1后再指向R）如果在同一个组中，A和B重叠，且节点的度大于K2,B服从A，若B和A的度均为K，且不能同时减少，B服从A。D判决更新组信息，如果形成了生成树，则终止，否则，判断是否能够以K再次合并其他组，是则重复以上步骤，否则，将度增加1，重复以上步骤。从步骤A到D的一次迭代，每个组（组Z）能够决定它的唯一的节点A和节点B。然后，节点A会决定组L中与它连接的唯一的节点C，节点C再决定组S中与它进行连接的唯一节点R。同时，组L（被组Z选出）将它自己视为“组Z”并且选择组Z为它的“组S”。在组Z中被视为节点C的节点在组L中被当作节点B。根据我们的算法，这个节点B将会决定组Z中的节点A作为“节点R”。43FSO网络路由算法从设计网络层路由协议的角度上讲，我们应依据网络的底层特性，决定具体的路由策略，不能不考虑网络底层特性而盲目进行路由协议的设计。因此，FSO网络的路由协议应采用主动式平面路由协议，特点是（1）主动式路由策略使得获取路由时延小；（2）网络中各个结点处拓扑信息一致、路由协议收敛快；（3）各结点地位平等，不存在瓶颈结点，从而网络鲁棒性强。FSO网络运行初始化算法进行组网，建立完整的网络拓扑。每个节点对于自己相连的N条链路状态进行实时跟踪，利用APT技术实时维持这N条链路。并且周期性的进行信息交互，实时跟踪到每个已建立连接的邻结点的链路的状态，尽力保持链路的连通状态，直到邻结点移出本地结点天线的射程范围。同时，根据网络拓扑的变化，适时调整网络拓扑，均衡网络流量，避免产生热点。5算法实现与分析51算法实现（1）确定网络结点的度网络结点的度的问题，也就是一个结点最多可以维持几个邻结点的问题。在基于FSO的移动ADHOC网络中，结点度为N意味着该结点得有N套收发信机。N值大，要求每个结点处的收发信机套数就多，进而导致系统成本高N值小，网络的连通性就差，随着拓扑的动态变化或者网络结点总数的略微增加，网络就会以很大的概率出现隔离。因此需要研究在给定网络结点总数N的情况下，每个结点的度N为多少比较合适的问题。关于网络结点的度问题人们已经研究了许多年。考虑到FSO链路的特性类似于有线链路，所以有线网络中结点度的数据对本系统结点的度的选取有一定的参考价值。现有因特网中，考虑不同网络规模结点的度的平均值为2142。本论文在对算法的验证时，以理论分析和现有因特网和移动ADHOC网络结点的度的研究为参考，综合考虑网络连通性、系统成本等因素，最终将网络结点的度K设为3，网络节点总数设为200。（2）验证过程我们将算法在VISUALC环境中实现，程序流程图如图51所示52算法正确性证明自下而上的算法不仅是一个计算过程。它也包括了收发机能借此改变它们各自方向的物理过程。本小节主要证明算法的近似值保证、传统最坏情况下的时间复杂度以及实际的收发机转动次数的复杂度。521近似值分析这部分将证明“存在性”和“近似性”。自下而上算法保证当输入的图G是可连接的图时，能够形成生成树，并且生成树的度是最优的。定理1给定一个图G，自下而上算法保证能够形成生成树。证明每组只增加一条将其与其它组相连的边，并且两个组之间只有一条潜在的边可以加入到树中，这就保证了树中没有冗余的边在每次迭代过程中，只要没有超过度的限制，至少会有一条边会被加入，当所有节点都加入到树中时，算法中止。所以，算法能够保为调试方便，将节点位置固定，将每个点的ID和位置坐标写入到全局变量“全网节点信息”中每个节点选择通信节点时，将被选择的节点计入到自己的相应结构体成员变量中，节点被分成组每个节点从信息库中读取所有节点的位置信息，计算潜在链路，写入到全局“潜在链路表”中更新每个节点的度值、所在组号、组总数等变量值，找出备选节点确定进行合并的组，并找出组之间进行连接的点验证两个组是不是同时满足相互连接的条件初始化合并组，将被合并组的节点设为本组成员，并更新组号、组总数组总数1是否能以3继续合并生成树形成，算法结束度最大值加一是否否是图51程序流程图证形成生成树并且最后能够终止。定理2假设自下而上算法产生的生成树的度为D，则D最多为（XL），X是最小度生成树的度。证明算法终止之前，度的限制从D1增加到D，两个组之间的每个备选到备选连接至少有一个度为D1，现在通过图G中的一条边将两个组合并，应当有下面的情景一个度为D1的节点和另外一个度为D1的节点连接；一个度为D1的节点和另外