自由空间光通信网络拓扑形成及路由算法研究课程设计.docx
《自由空间光通信网络拓扑形成及路由算法研究课程设计.docx》由会员分享，可在线阅读，更多相关《自由空间光通信网络拓扑形成及路由算法研究课程设计.docx（27页珍藏版）》请在冰点文库上搜索。
自由空间光通信网络拓扑形成及路由算法研究课程设计
兰州交通大学
课程设计
中文题目：
自由空间光通信网络拓扑形成及路由算法研究
英文题目：
FreeSpaceOpticalCommunicationNetwork
TopolopyFormationandRoutingAlgorithmResearch
课程：
现代传输技术
学院：
电子与信息工程学院
专业：
通信工程
摘要
自由空间光通信（freespaceopticalcommunicationFSO）是一种采用红外激光承载高速信号的无线传输技术，具有成本低、容量大、设计简单、接入方便等优势。
FSO网络既具有传统移动AdHoc网络的自组织性、独立组网能力、无中心抗毁性强等优点，又能利用FSO高质量的定向无线传输特性，实现网络物理层的收发控制。
因此，在无线通信领域，FSO网络技术受到了越来越多的关注。
本文在研究传统移动AdHoc网络拓扑及路由的基础上，结合当前FSO网络技术发展前沿，深入研究了FSO网络的初始化算法。
主要分析了一种分布式拓扑形成算法，它通过迭代建立连接，直至形成一颗树形拓扑结构，目的是在军事应用中提供快速连通性。
本文对该算法在VisualC++环境下进行模拟与仿真，并对其结果进行分析，提出改进方案，最终得到了最优拓扑。
在此基础上又提出了一种有效的路由算法，并进行了图解说明。
最后通过对算法的正确性论证，得出对于度受限的FSO网络初始化，自下而上最小度生成树算法是首选方法。
关键词：
自由空间光通信，初始化算法，生成树，路由算法
Abstract
Freespaceopticalcommunication（FSO）iswirelesstransmissiontechnologythatsignalconveybyinfraredlaser,Ithaslowcostbutgreatcapacityitisdesignedtobesimpleandexpedientlyaccessed.FSOnetworkhasthesameadvantageswithtraditionalmobileAdHocnetworkself-organization,independentnetworkingcapacity,nocenter,andinvulnerability,alsotakingadvantageofFSOwirelesstransmissioncharacteristicsofhigh-qualitydirectionalforphysicallayertransceiverscontrol.Ithasattractedmoreandmoreattentioninwirelesscommunication.
Inthispaper,basedonthestudyoftraditionalMobileAdHocnetworktopologyandrouting.Combinedwiththecutting-edgedevelopmentofthecurrentFSOnetworktechnology,FSOnetworkinitializationalgorithmisresearcheddeeplyMainlyanalyzesadistributedtopologyformationalgorithm,whichformaconnectedtopologybyiterations.Thisalgorithmisdesignedtoensure“fastconnectivity“ratherthanoptimizingothermetrics.ThesimulationenvironmentisimplementedinVisualC++,buttopologyobtainedisnotideal,Thispaperproposestheimprovementprogramandeventuallyobtaintheoptimaltopology.Alsoproposedanefficientroutingalgorithm,andhadillustratedinstructions.Finally,proofofcorrectnessofthealgorithm,Thebottom-upMinimum-DegreeSpanningTreealgorithmisafirstsolutionfortheinitialconfigurationofDegree-constrainedFreeSpaceOptical（FSO）networks.
Keyword：
FreeSpaceOpticalcommunication，Initializationalgorithm，Spanningtree，Routingalgorithm
目录
1.绪论5
1.1自由空间光通信网络的研究背景5
1.2国外自由空间光通信网络的研究概况6
1.3国内研究状况7
1.4自由空间光通信的技术特点8
2.自由空间光通信系统原理及关键技术8
2.1FSO系统组成及各部分功能8
2.2激光天线技术9
2.3APT技术9
2.4高功率光源及高码率调制技术10
3.移动AdHoc网络拓扑及路由研究11
3.1移动AdHoc网络简介11
3.2移动AdHoc网络的特点12
3.3移动AdHoc的拓扑结构13
3.4移动AdHoc网络拓扑形成算法16
3.5移动AdHoc网络的路由协议要求17
4.FSO网络拓扑形成及路由策略18
4.1FSO网络特征分析18
4.2FSO网络拓扑形成算法19
4.2.1算法模型19
4.2.2算法步骤20
4.3FSO网络路由算法22
5.算法实现与分析23
5.1算法实现23
5.2算法正确性证明24
5.2.1近似值分析24
5.2.2时间复杂度26
5.2.3物理复杂度26
5.3算法总结27
总结28
参考文献29
1.绪论
1.1自由空间光通信网络的研究背景
人类对光通信的研究起源于20世纪70年代，经过一百多年的发展，光通信已经成为当今社会信息传播的最重要、最常规的手段。
光通信具有灵活、经济等优点，它的迅猛发展，使得21世纪将成为无线光通信大展宏图的辉煌时代。
根据传输介质的不同，光通信又可以分为光纤通信，自由空间光通信和水下光通信。
其中自由空间光通信（freespaceopticalcommunication,FSO）又称为无线光通信（wirelessopticalcommunication,WOO），是一种基于光传输方式、采用红外激光承载高速信号的无线传输技术，具有高带宽、部署迅速、费用合理等优势。
它是以激光束作为信息载体，在大气中传送激光信号来实现点对点、点对多点或多点对多点间语音、数据、图像信息的双向通信技术。
FSO技术具有与光纤相同的带宽传输能力，使用相似的光学发射器和接收器，甚至还可以在自由空间实现波分复用（WDM）技术，因此又有“虚拟光纤”之称。
广义的FSO系统包括闷星际间光通信、星地间光通信和大气间光通信，狭义的FSO系统就是指大气间的无线传输。
按现代网络的功能模块划分，整个电信网可以分为三个部分：
接入网、交换网和传输网。
在90年代的光纤网络建设浪潮中，人们把研究重点主要放在光纤骨干网上。
目前，我国许多城市已基本实现光纤到路边/小区。
但用户接入网仍多为模拟双绞线技术所主宰，存在信号传输速率低、管子压力大、资源利用率低、配置不便等问题。
这些都限制了电信新业务的发展，成为电信网优化的“瓶颈”，即“最后一公里”问题。
为了适应这种需要，各种高数据速率的接入方式纷纷登场，其中既有传统技术又有新兴技术，如光纤电缆混合网（HFC）、数字用户环线（xDSL）、电缆调制解调器、以太网无源光网络（EPON）、吉比特无源光网络（GPON）、光纤、直播卫星系统（DBS）和本地多点分配业务（LMDS）系统等。
其中（HFC）和（xDSL）的接入部分是采用带宽低得多的现有铜线设施，存在严重的瓶颈问题。
解决这个问题的办法就是采用光纤和光无线，但光纤敷设的较长周期及高额投资限制了其普及，并且一旦用户离开，业务提供商想要收回投资就变得十分困难;LMDS技术日渐成熟，传输距离远，但这种接入方式需要高额的初始投资（频谱许可证），对业务提供商而言，这种接入技术并不经济。
相比较而言，FSO技术既能提供类似光纤的速率，又无需在频谱等稀有资源方面有很大的初始投资。
另外，激光技术的进步已经使耐用可靠的器件变得很便宜，大大降低了FSO设备的造价。
因此，在目前许多企业和机构都不具备光纤线路，但又需要较高速率的情况下不失为一种解决“最后一公里”瓶颈问题的最可行的解决方案。
自由空间光通信最初的研究，主要是用于科学研究目的，而在商业方面的应用最近几年才兴起。
作为当今十大电信热点技术之一，FSO技术受到越来越多企业以及运营商的重视，将成为今后构筑电信网的一项重要技术。
1.2国外自由空间光通信网络的研究概况
国际上自由空间光通信技术的研究是综合地面、飞机、卫星等方面进行的，从事这方面研究的主要机构在欧洲、日本、美国、韩国、俄罗斯等一些国家。
比较有代表性的有欧洲航天局（EuropeanSpaceAgency）、美国宇航局（NASA），Lightpoint公司、AstroTerra公司、Terabeam公司、Airfiber公司等。
美国是世界上最早研究星际与自由空间光通信系统的国家，也是技术最前沿的国家。
主要研究组织是美国空军和美国国家航空航天局（NASA）。
从20世纪80年代到1994年期间，美国空军支持麻省理工学院林肯实验室建立起了高速星间光通信实验装置LITE（LaserInter-SatelliteTransmissionExperiment）。
该实验采用8英寸口径的望远系统和30mw的半导体激光器，模拟星际间通信距离可达40000km，数据率达220Mb/s。
由空间与导弹防御司令部和弹道导弹防御组织共同资助的STRV2星一地激光通信计划的两个地面实验终端已加工装配完成。
计划在低轨道卫星与固定地面站间建立光链路，数据率将达到1Gb/s。
美国宇航局于70年代初也开始了激光通信的研究，主要从事GEO-GEO链路高码率通信和低空链路的低码率通信的研究。
在低码率通信中涉及到定位系统、光信道、激光器、探测器等技术领域，以后逐步扩展到LEO-LEO,LEO-GEO,LEO一地面站和LEO-飞机的光通信链路，又进行了一些其他演示系统和关键技术的研究，其代表性光通信演示系统LCDS-Laser传输数据率750Mbps，空对地演示系统、大气能见度监测计划等。
目前正在进行光通信演示系统以及窄带激光滤波器、高功率激光器及空间和地面的激光卫星跟踪网络的研制。
1.3国内研究状况
和国际相比，我国的研究相对单一，就目前的水平来说，相距国外还有一段距离，特别是在移动中的FSO技术，还没完成突破。
但对激光大气通信技术的研究起步并不晚，早在20世纪70年代就开始了大气激光通信的研究。
进入90年代后，随着国际上大气激光通信的复苏以及市场的需求，大气激光通信得到有关专家和决策者的重视，也逐渐加紧了这方面的研究。
1971年，中国电子科技集团公司第三十四所开始了激光大气通信技术的研究，1974年推出了ND。
YAG激光大气通信系统实验样机并成功进行了外场实验，通信距离约13Km。
1997年4月三十四所曾派人员到俄罗斯，就激光大气通信技术及应用情况进行了实地考察。
它的样机在2001年2月由主管部门进行设计定型，现在已经有部分投入试用。
中国电子科技集团公司第三十四研究所经过近几年的努力，已成功开发出了一系列的FSO设备，如：
专用网接入系列、以太网专用系列、图像传输专用系列、GSM信号传输系列等。
随后，北京邮电大学、电子科技大学，武汉邮电研究院以及合肥、大连、长春、北京等地的部分单位也相继展开了对大气激光通信的研究。
目前，中国宽带服务供应商长城宽带网络公司（GWBN）宣布将选用Terabeam的自由空域光通信产品FSO来拓展其在中国的15个城市的宽带网络，通过Terabeam的系统，GWBN将为大中型商业用户和大型住宅社区提供可靠的宽带服务，尤其是光纤和光缆很难到达或者敷设起来成本昂贵的地方。
中科院成都光电技术研究所引进外国公司先进的激光器及其附属电路，利用自己在光学器件上的优势，研发出了工作波长为850nm、能够传输1公里和4公里两种距离的两款产品。
1.4自由空间光通信的技术特点
相比于微波通信、铜缆、光纤等其他通信方式，FSO的主要优势是：
（1）频带宽、速率高、容量大
（2）频谱资源丰富、无需频率许可
（3）透明的传输协议
（4）传输安全、保密性好
（5）部署链路
（6）成本低廉
自由空间光通信技术的不足：
（1）传输距离有限
（2）天气影响通信质量
（3）对准困难
（4）激光信号对人体安全的威胁
2.自由空间光通信系统原理及关键技术
2.1FSO系统组成及各部分功能
一个FSO通信系统的设备组成，根据通信距离，激光器调制方式的不同而有所不同，结构的繁简程度也有很大差别。
根据自由空间光通信的技术特点及要求，光学通信终端主要由激光发射系统、接收系统、光学天线、ATP系统等组成。
本文所研究的FSO系统主要由链路信道设备、通信控制器、交换机和用户终端等组成。
信道设备包括激光波段的发射机、接收机、天线及APT系统，对应每个链路一套，主要实现物理层的功能；通信控制器主要实现链路层的功能；交换机主要实现网络层的功能；用户终端实现运输层和应用层的功能。
2.2激光天线技术
作为空间光通信中光束控制系统的重要组成部分之一的光学天线，直接影响空间光通信的工作质量。
光学天线是一个通过折射一反射光学实现的物镜系统，可视为一个能够接收自由空间特定波长微弱光信号的物镜。
其基本要求是：
（1）光天线有较大的入口直径，能最大限度地收集来自光源的信号。
（2）光学天线的分辨率与探测器的分辨率应该相匹配。
（3）选择合适的视场，大视场加大口径，使得通光口径更大，有利于接收更多的光辐射。
（4）光探测器是一个具有低通特性的装置，所以光学天线应该具有较好的低频响应特性。
（5）光天线应该有消除杂散光的设置。
系统要维持通信链路的高质量通信，需要较高的发射功率，但从人眼的安全方面考虑，激光的发射功率又不能太大。
综合考虑简单易实现的单发单收和抗衰减干扰不易实现的多发多收等情况，我们采用多个发射天线一个接收天线，即同一基带信号调制到多个功率较低的光束上同时发射。
由于发射的光束具有一定的发散角，这几个光束在较远的地方合在一起能满足通信要求的功率，而在较近的地方光束是相互分开的，也就不会对人眼造成伤害。
多个发射光束还有其他好处，如可以减小障碍物（如鸟）的阻挡，降低大气湍流闪烁效应的影响等。
2.3APT技术
自由空间光通信链路是点到点的链路，它可以作为固定设备安装在高楼之间进行通信，也可作为无线移动设备随时开通。
一个自由空间光通信系统在进行数据传送之前，必须确定发送端光信号被接收端光检测器正确接收，这意味着在需要克服传输通道上的各种效应之的同时，还必须使被发送的光场正确对准接收机。
同样接收机探测器也必须按照发送光场的到达角度进行调节。
接收机确定入射光束到达方向的操作被称为捕获（Acquisition），使发送机瞄准一个恰当方向的操作叫做瞄准（Pointing），在接下来的整个通信期间保持对准和捕获的操作称作跟踪（Tracking），三者简称为APT技术。
APT系统的主要技术指标要求有：
系统搜索范围、搜索对准时间、信标光束散角、信号光束散角、光束对准精度，系统频率响应（带宽）以及天线安装初始误差。
APT技术是保证实现空间远距离光通信的核心技术之一。
2.4高功率光源及高码率调制技术
（1）光源的选择
激光器光源用来产生激光信号，并形成激光束射向向量空间。
为提高通信性能指标，往往采用加大光源发射功率的方式。
但这样也会带来很多坏处，如对人眼的伤害以及光源使用寿命等问题。
所以，光源的选择非常关键，一般在选择时主要考虑以下几个方面：
波长应该选择在通过率良好的大气窗口；发射光功率要考虑到人眼的安全；要考虑激光器的输出频率稳定性、光束方向稳定性、输出光功率的稳定性；光源的工作寿命；出射光束窄、质量好、工作频率高等。
目前用于空间光通信的激光器主要有三类：
二氧化碳气体激光器，输出功率最大，但体积大，寿命短，比较适合于卫星与地面之间的无线光通信；激光泵浦ND：
YAG固体激光器，工作波长1064nm，但难于实现，是未来光通信的研究方向之一；二极管激光器，具有高效率、体积小、重量轻、结构简单等优点，可以采用直接调制方式，并且可以借助于已经成熟的光纤通信技术。
所以目前很多自由空间光通信系统都采用这种激光器作为光源，但因其发射光功率低，所以只适合短距离的无线光通信系统使用。
（2）调制方式的选择
目前，无线光通信系统可采用的调制方式主要有两类，即广泛采用的内部IM/DD制式和相干调制制式。
现分述如下：
内部IM/DD制式
采用此种调制方式的无线光通信系统设备是在其光发射机中直接用准备传输的信号调制光源的某个参数，即用准备传输的信号去调制半导体激光器的电流，从而实现对光源的直接调制;在接收端则对接收信号做直接检测。
相干调制制式
相干调制是相干光通信系统的核心技术，相干光通信是在发送端采用相干调制，在接收端采用外差解调的光通信系统。
也即外调制/外差检测制式。
3.移动AdHoc网络拓扑及路由研究
3.1移动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网络同时具备移动通信网络和计算机网络的特点，可以看作是一种特殊的移动计算机网络。
3.2移动AdHoc网络的特点
无线AdHoc网络继承了一般无线移动网络的特性。
和常见的无线局域网及有线固定网络相比，具有以下特征：
（1）无中心和自组织性
AdHoc网络没有严格的控制中心，所有节点地位平等，是一个对等式网络。
网络中的节点通过分布式算法来协调各自的行为，无需人工干预和任何其它预置的固定网络设施，网络中的节点可以随时随地的加入或离开网络，任何节点的故障都不会影响网络的整体运行，具有很强的抗毁性。
（2）动态变化的网络拓扑
AdHoc网络中，节点能够以任意速度和任意方式在网中移动，并可以随时关闭电台，加上无线传播条件随时间和空间不断改变，无线发送装置的天线类型多种多样、无线信道间的互相干扰、发送功率的变化、地形和天气等综合因素的影响，这些都使网络拓扑结构变化频繁和不可预测。
移动终端间通过无线信道形成的网络拓扑随时可能发生变化，而且变化的方式和速度都难以预测。
（3）有限的无线链路带宽
由于AdHoc网络采用无线传输技术作为底层通信手段，而无线信道本身的物理特性决定了它所能提供的网络带宽要远低于有线信道。
此外，考虑到竞争共享无线信道产生碰撞、多址接入、多径信号衰减、噪音干扰和信道间干扰等因素，移动终端最终得到的实际带宽远远小于理论上的最大带宽值，以致在网络中出现拥塞情况。
（4）安全性较差
由于采用无线信道、有限电源、分布式控制等技术，无线移动AdHoc网络更加容易受到被动窃听、主动入侵、拒绝服务、剥夺“睡眠”等网络攻击。
这些情况在军事应用中都要得到高度的重视。
因此，信道加密，抗干扰，用户认证，密钥管理，访问控制和其它安全措施都需要特别考虑。
（5）移动终端的有限性
AdHoc网络中的移动终端具有便携、轻便灵巧等优点，但是也存在固有缺陷。
例如依赖电池供电、能量十分有限、内存较小、CPU处理能力低，从而给应用程序设计开发带来一定的难度。
同时屏幕等外设较小、功能受限，不利于开展功能较复杂的业务。
（6）网络的可扩展性不强
Internet网络由于采用了TCP/IP协议中的子网技术，使其具有很强的网络可扩展性。
而动态变化的拓扑结构使得具有不同子网地址的移动节点可以同时处于一个AdHoc网络中，所以，子网技术所带来的可扩展性无法应用于AdHoc网络环境中。
（7）多跳路由
AdHoc网络的节点因发射功率的限制，节点的覆盖范围有限。
当它要与其通信覆盖范围之外的节点进行通信时，需要中间节点的多跳转发。
不需要专用的路由设备，每个节点都可以充当路由器。
3.3移动AdHoc的拓扑结构
随着移动网络技术的迅速发展，网络功能越来越强大，网络规模和网络结构越来越复杂。
那么，对一个移动AdHoc网络实现网络管理如系统配置、性能、故障处理等情况，首先就要知道整个网络的全局拓扑图。
拓扑结构图作为一个系统的重要模型，在整个网络的控制和管理上起到重要的基础性作用。
根据AdHoc网络的特点和作战环境需求，有中心控制节点的拓扑结构显然不适合，所以AdHoc网络不适合采用集中式控制结构，一般采用两种分布式结构：
平面结构（如图3-1）和分级结构（如图3-2、图3-3）。
在平面结构中，所有节点地位平等，也被称为是对等式结构。
与之相对的分级结构中，网络被划分为很多个簇（cluster），每个簇由一个簇头和多个簇成员组成。
这些簇头又构成了一个高一级的网络，在高一级的网络中，又可以分簇，形成更高一级的网络，直至最高级。
任意两个不在同一个簇内的簇成员之间的通信都要通过各自的簇头中继。
簇
升级会员 