无线自组织网络的关键技术及其应用(华南师范大学)new

无线自组织网络的关键技术及其应用华南师范大学：潘达儒2011年11月11日报告提纲一、背景、历史及应用领域介绍二、组网技术三、关键技术四、路由技术1.蚁群优化路由算法2.基于效用转交的多副本机会网络路由协议背景介绍InfrastructureNetworks:有基础设施网络常规有线网络GSM通讯系统用AP连接的WLANBSC:BaseStationControllerMSC:MobileSwitchingCenterInfrastructurelessNetworks:无基础设施网络AdHocNetworks背景介绍有设施的网络与无设施的网络有基础设施的网络，如：因特网（交换机、路由器）WLAN（无线接入点AP）蜂窝移动网络（基站）无基础设施的网络称为自组织（adhoc）网络，依靠节点之间的相互协作来完成网络的建立和维护。自组织网络的组成、特点自组织网络是由一群兼具终端及路由功能的设备通过无线链路形成的无中心、多跳、临时性自治系统。多跳：节点发射功率有限，远距离通信需要依靠其它节点的中继，从而每个节点既是终端又是路由器；无中心：网络中不存在任何控制中心，节点之间相互协作构成网络。临时性：专为某个特殊目的而建立，一般只是临时性的。当节点可移动时，称为移动自组网（MANET)。无线自组网的主要特点与无线局域网、3G等传统移动互联网的接入方式比较：单跳vs.多跳移动终端要承担路由的功能，替其他终端转发数据，路由协议是无线自组网的核心内容无线自组网的通信方式为P2P，但无线自组网主要由移动终端构成，不参与资源共享，仅提供路由功能FixedInfrastructure现有无线通信网络（有固定基础设施支持）交换机基站终端NoexistingInfrastructure无线自组网（无预先的基础设施支持）单跳vs.多跳蜂窝移动通信网络移动终端和固定基站互相通信移动终端不具备路由功能基站负责路由和交换功能，充当接入有线网络的网关AdHoc网络历史军事，美国DARPA1972年，分组无线网（PacketRadioNetwork）1993年，高残存性自适应网络（SURAN,SURvivableAdaptiveNetwork）1994年，全球移动信息系统（GloMo,GlobleMobileInformationSystems）1996年，联合战术无线网系统JTRS（JointTacticalRadioSystem）ARPANET无线分组网PRNET移动自组网（AdHoc）无线传感器网络（WSN）无线网格网络（WMN）军用/民用民用军用无线分组网ALOHANET局域网EthernetIEEE802.11WLAN民用民用民用军用军用因特网Internet民用AdHoc网络历史AdHoc网络历史民用，IETF&IEEE1991年，IETF成立了移动Adhoc网络工作组(MANET)1999年，RFC2501给出了MANET的应用场合2000年,IETF在公布了一系列的有关Adhoc路由的草案2000年，IEEE成立Adhoc技术分委员会MANET应用现状与前景军事应用紧急、临时等特殊场合个人使用14应用前景自组织网络商业：物联网无线城市智能家居会议会展抗震救灾军事应用智能家电C商务会议智能家电C商务会议无线自组织网络的地位从国家产业发展角度看，无线Adhoc网络是国家战略性新兴产业“网络信息”，以及“物联网”、“智慧地球”的核心技术和制高点之一。在国家安全（紧急服务、灾难救援和军用通信等）、环境监测、交通管理、空间探索等领域具有广泛应用前景。网络通讯核心技术之一。移动计算的基础。自组织技术在“云计算”等也有重要需求。网络自主性-自组网结构平坦结构节点对等适用于小型自组网网络管理开销小无线自组织网络的组网技术网络自主性-自组网结构层次结构基于簇或区域划分簇中分簇首和簇成员适用较大规模的自组网无线自组织网络的组网技术簇的形成和调整规则节点周期性交换状态信息若一个节点的邻居节点中没有簇首，则该节点为簇首若存在两个簇首相邻，则将标识号（地址）较小或邻节点多的簇首作为新簇首，另外一个作为簇成员AdHoc组网方式AdHoc单独组网网内节点进行通信，不与基础网络设施相连混合组网AdHoc与Internet整合AdHoc与蜂窝网整合无线自组织网络的组网技术和其它宽带网络的集成Wi-FiWi-FiWi-FiWi-FiWi-FiWi-FiWi-FiWi-FiInternet3G/HSDPA/WiMAXWi-FiWi-FiWi-Fi方便的宽带无线接入方案Internet光纤骨干网MESHWi-Fi接入网有线或WiMAXWirelessmeshnetworks(WMNs）Themeshroutersformameshofself-configuring,self-healinglinksamongthemselves.VANET车辆自组织网络VANET车辆自组织网络HotSpotHotSpotHighwayNetworkUrban“opportunistic”adhocnetworkingFromWirelesstoWirednetworkViaMultihop实现MANET关键技术路由协议安全问题功率控制QoS网络服务质量网络互联网络资源的管理•感知网络拓扑结构的变化•维护网络拓扑结构•高度自适应路由•广播与组播•信道接入技术•能耗节约机制•多个AdHoc网络互联•能内部节点访问Internet移动自组网的主要研究问题信道接入（MAC协议）：困难：多跳共享广播信道的介质访问控制。路由协议：困难：网络拓扑的动态变化导致路由信息收集困难，路由算法难收敛，路由经常中断需要重建。服务质量保证（QoS）：困难：网络的动态性（链路质量、带宽、路由不稳定）及分布式控制很难保证传输质量。网络安全：困难：分布式认证与密钥管理，防御入侵。移动自组网的路由技术因特网中的路由技术利用了静态网络拓扑的特性：网络拓扑信息在节点间主动传播，每个节点可以使用较低代价的算法预先计算好该拓扑下的路由；节点地址中隐含了路由线索（网络号）。这两种技术均不适合移动自组网：节点移动使得拓扑信息的有效性降低；永久性的节点地址无法包含动态的位置信息。对移动自组网有用的拓扑假设是：物理上靠近的节点在网络拓扑上也可能靠近。ExistingMANETprotocolsMANETroutingprotocolsdiscoverrouteson-demand(re-active)Maintainupdatedroutes(pro-active)SourceroutingTabledrivenVariationofdistantvector?Variationsoflinkstaterouting?DSRAODV,ABR,TORADSDV、CGSROLSR先应式路由反应式（按需）路由混合式路由（Hybrid）ZRP(局部先应，广域按需）其它：功率感知路由、地理位置信息路由、QoS路由、多播路由、可扩展路由反应式路由协议--AODVAd-hocOn-demandDistanceVector（AODV）也是基于距离矢量的路由协议，但是仅当需要一条路由通信时，才由源节点启动路由发现过程。与DSDV相比，不在活跃路径上的节点不维护任何路由信息，也不参与任何周期性的路由表交换，因此可极大地减小路由消息的开销。AODV的基本思想当源节点希望向某个目的节点发送数据，但当前路由表中并无该节点的路由信息时，启动路由发现过程；源节点向其邻居广播一个RREQ（路由请求）消息，进行路由探测；每个收到RREQ消息的节点向其邻居扩散该消息，直至消息到达一个知晓目的节点路由的节点（中间节点或目的节点）；该中间节点或目的节点向源节点发送一个RREP（路由响应）消息，当RREP消息到达源节点时，建立起源节点到目的节点的路由。要解决的问题如何使RREP返回源节点：所有转发RREQ消息的节点要记录到源节点的路径（反向路径）；如何区分路由的新旧：路由序号。RREQ消息包含源地址，源序号，广播ID，目的地址，目的序号，跳数6个域：源地址，广播ID二元组唯一标识一个RREQ源序号：用于维护反向路径的新鲜性目的序号：可被源节点接受的正向路径的新鲜程度跳数：每次转发RREQ时，将跳数加1RREQ的处理和反向路径建立源节点发送一个RREQ消息；邻居节点收到RREQ后，有三种可能：该RREQ已收到过：丢弃该消息；路由表中有到目的节点的路由，且该路由的目的序号不小于RREQ的目的序号：向收到RREQ的邻居发送一个RREP消息；其余情况：将RREQ的跳数加1，继续向邻居转发RREQ，并建立到源节点的反向路径（记录RREQ到来的前一跳邻居）。RREP的处理和正向路径建立RREP消息包含源地址，目的地址，目的序号，跳数，生存时间；收到RREP消息后：若为第一个RREP拷贝，建立到目的节点的正向路径（记录RREP到来的邻居节点），记录目的节点的最新序号，向源节点传播；若非第一个RREP，仅当目的序号大于之前的RREP，或目的序号相同但跳数更小时，才更新路由表项并传播新的RREP，否则丢弃RREP。路由表管理每个路由表项除包含常见的目的地址、下一跳、跳数等信息之外，还包括：目的序号：所有路由用目的序号进行标记；过期时间：该路由表项未被使用的时间；活跃邻居集合：在最近一段时间内向目的节点发送/转发过分组的邻居；正向及反向路径的超时时间：在该时间之后路由失效。每条反向路径有一个路由请求过期定时器，用于清除不在RREP传输路径上的节点保存的反向路径。路由重建如果在活跃的会话过程中源节点发生了移动，源节点可以发送RREQ重建路由。若目的节点或某个中间节点发生了移动（路由发生了中断）：断点上游的节点向所有活跃的上游邻居发送一个RREP消息，消息序号比之前知道的序号大1，跳数为∞；收到消息的节点向它的活跃邻居转发该消息，直至所有的活跃节点被通知；需要重建路由的节点发送目的序号比之前大1的RREQ消息，以确保建立的是一条新路由。移动自组网跨层设计分层设计是计算机网络的一个重要设计原则，但应用到无线网络上的性能和效率却很低。研究表明，移动自组网中路由协议、MAC协议、节点速度以及数据包注入速度之间存在相互作用，孤立地讨论某个问题没有意义。跨层设计的要点是允许位于不同层上的协议相互合作，在保持分层的前提下共享网络状态信息，从而达到优化整个系统性能的目的。QoS路由问题多个不相干可加度量的QoS(QualityofService服务质量)路由问题是一个NP完全问题，此类问题是当前数学界尚未解决的数学难题。对于QoS路由中的NP完全问题，关键在于如何针对相应问题的特殊性寻求其特定的可行解，即通过启发式算法进行求解。人工智能优化算法为解决QoS路由中的NP完全问题提供了新的思路QOS度量参数选择合理解决多参数问题，能够降低算法的复杂度，把NP问题转换成P问题（多项式时间问题）。单混合度量参数路由算法以多个度量参数为变量构建函数，以单一的函数值作为选路的度量标准。多度量参数路由算法A.选择主要度量参数法B.量化度量参数法C.参数定界法D.结合节点控制策略，相关化多个参数。单播路由链路约束问题(带宽约束路由)P问题链路最优化问题（带宽最佳路由）P问题路径约束问题（延时约束路由）P问题路径最优化问题（最小费用路由）P问题P问题（带宽约束缓冲区最佳路由）链路约束-链路最优化问题P问题（带宽缓冲约束路由）链路多约束问题P问题（带宽延时约束路由）链路约束-路径约束问题NP问题（延时约束费用最小路由）路径约束-路径最优化问题P问题（延时约束带宽最佳路由）路径约束-链路最优化问题NP问题（延时-抖动约束路由）路径多约束问题P问题（带宽约束延时最小路由