移动自组网ppt课件.ppt

移动自组网,分组网技术的发展,有设施的网络与无设施的网络,有基础设施的网络，如：因特网（交换机、路由器）WLAN（无线接入点AP）蜂窝移动网络（基站）无基础设施的网络称为自组织（ad hoc）网络，依靠节点之间的相互协作来完成网络的建立和维护。,有基础设施的网络,无线自组织网络,自组织网络的组成,自组织网络是由一群兼具终端及路由功能的设备通过无线链路形成的无中心、多跳、临时性自治系统。多跳：节点发射功率有限，远距离通信需要依靠其它节点的中继，从而每个节点既是终端又是路由器；无中心：网络中不存在任何控制中心，节点之间相互协作构成网络。临时性：专为某个特殊目的而建立，一般只是临时性的。当节点可移动时，称为移动自组网。,自组网的主要应用领域,军事领域：该技术的初衷是应用于军事领域，是美国军方战术网络技术的核心，”自愈式雷场系统“是其典型实例。民用领域：临时性工作场合的通信，如会议、庆典、展览等；灾难环境中提供通信支持野外工作中的通信，如科考、边防站等个人区域网络应用，实现PDA、手机等个人电子通信设备之间的通信。家庭无线网络、移动医疗监护系统等。,移动自组网的特点,带宽有限：频谱受限，共享链路。（带宽优化是关键）存在单向链路：传输功率及环境噪声差异可能在节点间形成单向链路。（传统路由算法一般基于对称链路假设）拓扑动态变化：节点移动、链路时变、节点失效等。（传统路由算法会出现路由振荡、难以收敛的问题）节点能量有限：节点使用电池供电，充电困难。（所有设计均要求节省能量，延长网络生存时间）安全性差：开放的无线信道，有限的电源供应，分布式控制。（易遭受窃听、主动入侵、拒绝服务等网络攻击 ）,移动自组网的主要研究问题,信道接入（MAC协议）：困难：多跳共享广播信道的介质访问控制。路由协议：困难：网络拓扑的动态变化导致路由信息收集困难，路由算法难收敛，路由经常中断需要重建。服务质量保证：困难：网络的动态性（链路质量、带宽、路由不稳定）及分布式控制很难保证传输质量。网络安全：困难：分布式认证与密钥管理，防御入侵。,1. 移动自组网的单播路由技术,因特网中的路由技术利用了静态网络拓扑的特性：网络拓扑信息在节点间主动传播，每个节点可以使用较低代价的算法预先计算好该拓扑下的路由；节点地址中隐含了路由线索（网络号）。这两种技术均不适合移动自组网：节点移动使得拓扑信息的有效性降低；永久性的节点地址无法包含动态的位置信息。对移动自组网有用的拓扑假设是：物理上靠近的节点在网络拓扑上也可能靠近。,移动自组网路由协议分类,移动自组网单播路由协议的分类,取决于路由决策所依据的信息：基于拓扑的路由：基于节点的连接关系计算路由表：基于地理位置的路由：根据节点的地理位置进行转发决策，不需要路由表。按照触发路由计算的条件，基于拓扑的路由分为：先应式路由：主动维护到网络中所有节点的路由。反应式（按需）路由：仅当节点间需要通信时才建立路由。,1.1 先应式路由协议-DSDV,Destination-Sequenced Distance Vector（DSDV）采用经典的距离矢量路由算法，保存到每个节点的最小跳数路由。因特网中的距离矢量算法：每个节点维护一张路由表，网络中每个节点在此表中占有一个表项。每个表项包括两部分内容：去往该目的节点的最佳输出线路（下一跳）以及估计到该目的节点的最短距离。每隔一段时间，每个节点向其所有邻居发送一个距离矢量，通报从本节点到其它各个节点的估算距离。每个节点利用从邻居节点收到的距离矢量来更新自己的路由表。,要解决的主要问题,什么时候发送路由更新：周期性更新 + 触发式更新，异步更新；如何区分路由更新消息的新旧：使用消息序号，由发送节点产生；如何区分路由的新旧：每条路由携带一个目的序号，由目的节点产生和发布，其它节点不能修改。,路由选择的原则,采用目的序号最新的路由，丢弃较早序号的路由；若目的序号相等，采用较小跳数的路由被采纳的路由跳数加1，目的序号不变， 在下一次路由更新中发布。,检测链路中断,当节点检测到与某个邻居节点的链路中断时，将以该邻居为下一跳的所有路由的跳数标记为，并为这些路由分配新的序号。为与目的节点产生的序号相区分，规定目的节点产生的序号为偶数，中间节点产生的序号为奇数。当节点收到一个跳数，随后又收到一个序号更高的、具有有限跳数的路由时，节点用“真实”的序号代替该路由，并触发一次路由更新广播。,如何减少路由更新的开销？,为减少路由更新的开销，DSDV定义了两种路由更新分组：Full dump：携带完整的路由表Incremental：只携带上一次full dump之后变化的路由信息协议假设节点能够根据路由变化的重要程度来决定是否触发一次增量更新，根据增量更新的数据量来决定是否进行一次full dump 。,环路与计数至无穷问题,已有的距离矢量路由算法（如RIP）没有解决好路由环路及计数至无穷的问题。DSDV使用目的序号解决了该问题：节点总是使用最新最好的路由，避免路由环路的发生；使用奇数序号表示链路中断，避免了计数至无穷的问题。DSDV的缺点：消息开销大，限制了网络的规模节点需要维护大量当前不活跃的路由，浪费了不少资源,1.2 反应式路由协议-AODV,Ad-hoc On-demand Distance Vector（AODV）也是基于距离矢量的路由协议，但是仅当需要一条路由通信时，才由源节点启动路由发现过程。与DSDV相比，不在活跃路径上的节点不维护任何路由信息，也不参与任何周期性的路由表交换，因此可极大地减小路由消息的开销。,AODV的基本思想,当源节点希望向某个目的节点发送数据，但当前路由表中并无该节点的路由信息时，启动路由发现过程；源节点向其邻居广播一个RREQ（路由请求）消息，进行路由探测；每个收到RREQ消息的节点向其邻居扩散该消息，直至消息到达一个知晓目的节点路由的节点（中间节点或目的节点）；该中间节点或目的节点向源节点发送一个RREP（路由响应）消息，当RREP消息到达源节点时，建立起源节点到目的节点的路由。,要解决的问题,如何使RREP返回源节点：所有转发RREQ消息的节点要记录到源节点的路径（反向路径）；如何区分路由的新旧：路由序号。RREQ消息包含6个域：二元组唯一标识一个RREQ源序号：用于维护反向路径的新鲜性目的序号：可被源节点接受的正向路径的新鲜程度跳数：每次转发RREQ时，将跳数加1,RREQ的处理和反向路径建立,源节点发送一个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消息，以确保建立的是一条新路由。,基于拓扑的路由算法的扩放性,对路由算法扩放性影响最大的两个因素：网络拓扑的变化频率路由域中的节点数目直观上，拓扑改变产生的更新开销等于状态改变频率乘以节点数量。因此，基于拓扑的路由算法一般而言对于节点移动的适应性较差。,1.3 基于地理位置的路由,假设：节点能够通过GPS或其它方式知道自己的位置坐标；源节点知道目的节点的位置坐标，并将其标记在数据包头中；每个节点知道其所有一跳邻居的位置；基于地理位置的路由决策：物理上最靠近目的节点的邻居为下一跳。优点：只需要局部位置信息而不管整个网络规模，扩放性好；不需要网络的拓扑信息，从而允许近乎无状态的转发。,1.3.1 转发策略（GPRS）,Greedy Perimeter Stateless Routing是一个典型的基于地理位置的路由算法，包括两种转发策略：贪婪转发：只要有可能，总是使用这种转发策略；边缘转发：贪婪转发不可用时，使用边缘转发。,贪婪转发,转发节点根据本节点位置、邻居节点位置和目的节点位置进行局部最优决策：与目的节点距离最近的邻居成为下一跳。,局部最大问题,转发节点比任何邻居节点都更靠近目的节点，形成空洞。,边缘转发,GPSR使用右手法则按（x-w-v-D-z-y-x）的顺序沿着空洞行进，直至到达比x更靠近D的节点（包括D本身）。,1.3.2 位置服务,使用地理位置路由的前提是，源节点必须知道目的节点的位置，即网络中应当有位置服务机制。位置服务必须是可扩放的：位置服务本身只依靠地理位置转发就能实现任何一个节点不能成为瓶颈一个节点的失效不应当影响其它许多节点的可达性对附近节点的位置查询应当仅依靠本地通信就能满足实现位置查询和更新的开销小，且每个节点实现位置服务的开销随节点总数的增长而少量增长,GLS（Grid Location Service）,每个节点将其当前位置保存在网络中的一组节点（称位置服务器）上；（容错）每个节点都是其它一些节点的位置服务器；（分摊）节点的位置服务器在离它较近的区域分布较密集，较远的区域分布较稀疏；（从近到远逐渐稀疏的位置分布原则）为使网络中不包含特殊节点，使用一致性哈希（consistent hashing）为每个节点（ID）建立位置服务器层次；为使位置服务的分布是均匀的，网络中的节点ID必须是一个随机分布，GLS使用一个强哈希函数从节点的唯一名字得到节点ID；位置更新和位置查询应使用相同的算法和输入参数。,网络的全局划分,由逐渐增大的正方形组成的分层网格结构：最小的正方形称为一阶正方形；4个n阶正方形组成一个(n+1)阶正方形；n阶正方形的左下角坐标为(a2n-1, b2n-1)。,位置服务器的选择规则,节点从其所在的一阶正方形开始，在每个与其相邻的n-阶正方形中，选择最近的一个节点作为其位置服务器。在ID空间中与节点X最近的节点，其ID是大于X的最小ID。ID空间是循环的。,B选择位置服务器的例子,位置服务器的查询方法,位置服务器的招募,为使B将位置发送到一个n-阶正方形的合适节点，唯一要求的是该正方形中的所有节点已经在该正方形中发送了它们的位置。假设B希望在某个n-阶正方形中寻找一个位置服务器，B采用地理位置转发向那个正方形发送一个分组。,位置服务器的招募（续）,在那个正方形中第一个收到分组的节点启动一个位置更新过程，该过程非常类似于对B的一个查询过程，只不过这个更新分组一直携带着B的位置。最终这个更新分组在离开该n-阶正方形之前会到达一个大于B的最小节点，这个节点就是这个更新分组的正确目的地。该目的节点记录下B的位置，成为B的一个位置服务器。,算法的有效性分析,可以证明 ：若源节点和目的节点包含在一个n-阶正方形中，则一个位置查询不超过n个查询步就可到达目的节点，而且查询不会离开包含起点的n-阶正方形。开始时，查询请求利用本地路由协议被转发到本地一阶正方形中的最佳节点；此后，每一步都将查询推进到包含该正方形的下一阶正方形中的最佳节点；当下一个较大正方形包含目的节点时，最佳节点（与目的ID最近）必定是目的本身，查询的下一步到达目的节点。由于查询步推进到包含源节点的越来越大的正方形中，查询将始终停留在包含源节点和目的节点的最小正方形中。,节点21的二阶正方形中没有ID介于1721之间的节点。若三阶正方形中有ID介于1721之间的节点X，X肯定选择21为其位置服务器，即21知道三阶正方形中ID值介于1721之间的所有节点，包括满足该条件的最小节点。以此类推，节点20知道其四阶正方形中ID值介于1720之间的所有节点。由于节点17和20在同一个四阶正方形中，因此节点20知道节点17，于是查询结束。,2. 移动自组网的MAC协议,移动自组网的MAC协议主要解决：信道访问冲突的问题由于节点移动和不可靠时变信道引起的问题CSMA及其为有线网络开发的CSMA/CD不能直接应用于多跳无线网络，需要研究新的MAC协议。,隐藏终端与暴露终端,MAC协议分类,基于竞争的MAC协议分类,发送者启动 vs. 接收者启动的MAC协议单信道 vs. 多信道MAC协议功率认知（Power aware）的MAC协议基于有向天线的MAC协议基于单向链路的MAC协议QoS认知（QoS aware）的MAC协议,2.1 常规MAC协议,常规假设：单一共享信道全向天线对称链路发射功率已知且固定，不考虑节能措施不考虑QoS这一类协议主要基于MACA（Multiple Access with Collision Avoidance）协议解决隐藏终端和暴露终端问题。,（1）MACA Multiple Access with Collision avoidance,A向B发送RTS消息，给出随后将要发送的数据长度；B返回一个CTS消息，给出将要发送的数据的长度；A收到CTS后，立即发送数据。,MACA（续）,任何监听到RTS消息的节点推迟传输，直至CTS被A收到；任何监听到CTS的节点推迟发送，直至数据被B收到；接收到RTS但没有接收到CTS的节点，在CTS之后可以开始传输。若A没有收到CTS，A最终将超时重发。,隐藏终端与暴露终端的解决,MACA小结,与CSMA避免在发送端产生冲突不同，MACA避免在接收端产生冲突。 MACA使用RTS-CTS交换解决了一部分的隐藏终端和暴露终端问题。缺点：仍不能完全解决隐藏终端问题；不对数据传输提供确认；建立在对称链路假设的基础上，在有大量单向链路的多跳无线网络中不适用。,（2）MACAW（MACA for Wireless）,MACAW使用RTS-CTS-DS-DATA-ACK传输序列 A向B发送RTS消息B收到RTS后，发送CTS消息作为响应A收到CTS后，发送DS（Data Sending）消息A发送DATA帧B收到DATA帧后，发送ACK消息进行确认若A有多个数据帧，在每一次成功传输之后必须等待一个随机时间，然后使用RTS/CTS机制重新竞争信道。,RRTS（Request for RTS）,在A、B通信过程中，D向C发送RTS，C由于推迟发送不能及时响应CTS，导致D进入回退状态，在A、B通信结束后不能及时捕获信道。节点C在当前传输结束后使用RRTS要求D立即发送RTS，以便尽快捕获信道。,D和C之间可能的交互序列,D向C发送RTS一段时间后，C向D发送RRTSD发送RTSC发送CTSD发送DSD发送DATAC发送ACK,未解决的问题,MACAW未解决暴露终端的问题：暴露在发送端传输范围中的节点，无法接收到其它节点向它发送的RTS，无法利用RRTS机制来提高这部分节点使用信道的公平性。,MACAW小结,使用RTS-CTS-DS-DATA-ACK五阶段交互与MACA相比，引入ACK确认机制提高了错误恢复的速度引入RRTS机制，提高了隐藏终端获取信道的公平性仍不能完全解决暴露终端的问题,（3）802.11的MAC协议,802.11的MAC层有PCF和DCF两种操作模式：PCF模式只能用于有基础设施的无线网络DCF模式既可用于自组织网络也可用于有基站的无线网络，所有协议实现都必须支持DCF模式。DCF模式采用CSMA/CA作为MAC层协议，每个节点在发送前都要监听信道，当信道空闲时有两种操作方法：使用RTS-CTS机制预约信道不使用RTS-CTS预约机制。,使用RTS-CTS信道预约机制,较长的帧可分片传输,802.11的帧间距,在SIFS到来时，只有以下节点允许发送：收到RTS的节点可以发送一个CTS；正确收到一个数据帧或分片的节点可以发送一个ACK；收到ACK的节点可以继续发送下一个数据分片。,不使用RTS-CTS信道预约机制,当一个节点有帧要发送时，首先侦听信道： 1）若一开始就侦听到信道空闲，则在等待了DIFS时间之后发送该帧； 2）若信道忙，选取一个随机的回退值，并在侦听到信道空闲时开始递减该值；在此过程中若侦听到信道忙，则停止递减并保持计数值不变。 3）当计数值减为0时（仅可能发生在侦听到信道为空闲时），节点发送整个帧并等待确认。 4）收到确认帧后，若还要发送下一个帧，进入第2步；若未收到确认，进入第2步中的回退阶段，并从一个更大的范围内选取随机值。,CSMA/CA与CSMA/CD的比较,使用的传输介质不同：CSMA/CD应用于有线介质，节点在发送的同时可以监听信道；CSMA/CA应用于无线介质，节点在发送的时候无法监听信道。隐藏终端与暴露终端问题：CSMA/CD应用于单跳共享网络，所有通信过程及冲突可以检测到；CSMA/CA应用于多跳共享网络，有些通信过程检测不到。,未解决的问题,802.11的MAC协议不适合多跳自组网，因为它假设节点的时钟是同步的。,（4）接收端启动的协议-MACA-BI,MACA-BI要求接收端使用一个RTR消息请求发送端发送数据，从而是一个RTR-DATA的两阶段交互过程。发送端在数据分组中携带包队列长度及数据到达速率等信息，接收端预测发送端积累的数据，决定是否发送RTR。当发送端缓存溢出时，发送端发送一个RTS，这时协议回复到MACA。MACA-BI适合于流量模式可预测的网络，当流量突发性较大时，性能退化到MACA。,MACA-BI不会产生直接的数据冲突,当A正向B发送数据时，在B处发生冲突有以下两种可能：（1）C正向B发送一个数据帧：不可能，因为B每次只邀请一个节点发送。（2）C正向D发送一个数据帧：仅当C没有监听到B发送给A的RTR时，这种情况会发生。发生这种情形有两种可能： 1）当C正在发送（RTR或数据）时，B向A发送一个RTR：不可能，因为B应当监听到C的发送，从而B不会发送RTR。 2）当C正在接收时，B向A发送一个RTR：不可能，因为D发给C的RTR将会与B发送的RTR冲突，从而C不会向D发送。,2.2 功率认知的MAC协议,节省能量和有效利用能量应贯穿移动自组网设计的全过程。设计功率有效的MAC协议的一般性指导方针是：尽可能避免冲突只要有可能，无线收发器应关闭发射器的功率应调整到确保目的节点正确接收的最低水平 功率认知MAC协议的两种设计方法：通过休眠调度节省能量通过调节发送功率来节省能量,（1）DPSM（Dynamic Power Saving Mechanism）,802.11的PSM：每个节点在信标间隔开始时监听信道一段固定的时间（ATIM窗口），发送节点通过ATIM帧通告将要发送的数据，接收节点用ATIM-ACK帧进行响应，ATIM窗口结束后发送数据。,DPSM（续）,在一个信标间隔内只给每个节点发送一个ATIM，并在后续发送的每一个数据帧中包含待发送的数据帧数量。若在当前信标间隔内无法将所有通告的数据包发完，双方进入下一个信标间隔继续传输剩下的数据帧，不需要再发送ATIM。传输结束后，节点进入休眠状态。设计了ATIM帧的回退算法，使用CSMA/CA机制发送ATIM帧。标记在当前ATIM窗口中未成功发送的数据帧（最多重发三次）；每个帧最多可以在两个信标间隔中通告和发送，仍未成功则丢弃。,DPSM（续）,每个节点在发送的数据帧中捎带ATIM窗口大小，发送节点优先向ATIM窗口较小的目的节点发送数据。动态调整ATIM窗口大小：在当前窗口中来不及通告的帧太多，增大窗口；自己的ATIM窗口小于其它节点的窗口两个等级，增大窗口；在ATIM窗口结束后收到ATIM帧，增大窗口；收到标记的数据帧，增大窗口；在一个窗口中成功通告所有的帧，且没有以上四个条件产生，减小窗口。,在ATIM窗口结束后收到ATIM帧,收到标记的数据帧,未解决的问题,DPSM不适合多跳自组网，因为它建立在802.11的帧间距基础之上，要求节点时钟同步。,（2）PCM（Power Control MAC）,D用功率PD-max发送RTS给E，RTS中包含PD-max；E测量信号强度Pr，计算D的最小发送功率PD-suff，使用功率 PE-max发送CTS发送给D，CTS中包含PE-max和PD-suff ；D用相同的方法计算E的最小发送功率PE-suff，用功率PD-suff发送数据包，将PE-suff值携带在数据包中。E使用功率PE-suff发送ACK包。,PCM的问题,PCM方案需要对接收信号强度有相当精确的估计，因此由信道衰减、遮蔽等因素引起的无线信号传播的动态性会影响性能；在不同发送功率之间频繁切换，在实现上是很困难的。,2.3 多通道协议,使用单一共享信道的问题是，随着节点数量增加，冲突概率增加，系统性能下降。多通道协议的种类：使用分开的控制信道和数据信道：发送节点在控制信道上发送忙音，在数据信道上传输数据。使用多个数据信道：同时传输多路信号，提高数据传输速率，减少冲突。多通道MAC协议要解决的问题：在不同的节点间实时分配信道，决定一个节点在哪个时隙可以访问哪个信道。,Multi-channel CSMA,将可用带宽（W）划分成N个大小为W/N的信道，信道划分方法可以是FDMA或CDMA。发送节点侦听信道:如果上次使用的信道空闲，使用该信道；如果上次使用的信道不空闲，随机选择一个空闲信道；如果没有空闲信道，回退等待，然后重试。实验表明：多通道CSMA比单通道CSMA更有效，但在低负载或只有少量活跃节点时性能不如单通道CSMA。,MMAC（Multi-channel MAC）,MMAC将时间划分成若干固定长度的信标间隔，每个信标间隔开始是一个ATIM窗口；每个节点维护一个首选信道列表PCL；在每个信标间隔的开始，无线收发器被调谐到交换ATIM的信道；发送节点发送一个ATIM帧，包含自己的PCL；接收节点比较双方的PCL，选择一个合适的信道放入ATIM-ACK中发回；若发送节点接受该信道，发送一个ATIM-RES帧；双方在选择的信道上交换RTS和CTS，然后交换数据；若发送节点不接受所选的信道，在下一个信标间隔尝试另一个信道。任何监听到ATIM-ACK和ATIM-RES的节点更新其PCL。,未解决的问题,MMAC比IEEE 802.11的吞吐量高，但延迟较长；MMAC也不适合多跳自组网，因为它假设节点是同步的。,2.4 有待进一步研究的问题,隐藏终端和暴露终端问题：大多数解决隐藏终端问题的MAC协议都没有有效处理暴露终端。干扰受限模型：节点的冲突模型（圆形阶跃冲突模型）过于简单，与实际情况不符。节能：目前提出的功率认知的MAC协议均有缺点。多通道协议是否真的有效？多跳网络：不少MAC协议不适合多跳网络。使用有向天线：如何效利用智能天线。QoS问题。,3. 移动自组网跨层设计,分层设计是计算机网络的一个重要设计原则，但应用到无线网络上的性能和效率却很低。研究表明，移动自组网中路由协议、MAC协议、节点速度以及数据包注入速度之间存在相互作用，孤立地讨论某个问题没有意义。跨层设计的要点是允许位于不同层上的协议相互合作，在保持分层的前提下共享网络状态信息，从而达到优化整个系统性能的目的。,3.1 路由协议与MAC协议的相互作用,6研究了路由协议、MAC协议、运动模型、节点速度和数据包注入速度对系统性能的影响。选取了：3个路由协议：DSR、AODV、LAR3个MAC协议：CSMA/CA、MACA、802.113个节点移动模型：grid mobility model、random waypoint mobility model、exponential correlated random mobility model,性能评估标准,延迟（秒）：数据包平均端到端延迟，包括由缓存、传输、排队、回退等各种因素造成的延迟；正确接收的数据包比例：丢包率；吞吐量（b/s）：单位时间内接收到的不重复数据包的总量；协议的长时间公平性：分配给每个活跃连接的资源比例。,3个基本实验,构造了3个基本实验，每个实验对应一种运动模型。在每一个基本实验中，选取MAC协议、路由协议、节点速度、数据包注入速度4个输入变量，每个变量有3种不同的等级值。输入变量的每一种组合对应一种实验场景，每种场景运行10次；即每个基本实验共有81种场景，需运行810次。针对实验产生的大量数据，论文设计了析因实验（factorial experiment），采用统计的方法进行分析。,（1）如何研究变量之间的相互作用,从统计的角度说，两个因素之间存在相互作用，如果一个因素对响应变量的作用可以被另一个因素极大地改变。另一种说法，如果两个因素之间有相互作用，则一种因素取不同等级值时对响应变量作用的差异，在另一种因素变化时不能保持恒定。,示例1,注入速率和节点速度之间的相互作用,示例2,（2）如何研究算法之间的相互作用,算法之间的相互作用存在于网络节点中运行的协议（算法）之间。”相互作用“表示协议栈中一个协议的行为严重依赖于其上层或下层的协议。算法之间的相互作用很复杂，一个响应变量的变化可能是由相互影响的协议之间复杂、偶然的依赖造成的。有两种相互作用，分别存在于：运行于不同节点上的同种协议之间；运行在相同或不同节点上的异种协议之间。,路由对MAC协议的影响,MAC层和路由层之间的相互作用,在静态网格网络中建立两条连接：(1,0)-(1,6)和(5,0)-(5,6)。考虑四种MAC协议/路由协议组合：802.11/AODV、MACA/AODV、802.11/DSR、MACA/DSR。统计每一种组合下产生的MAC层信令包和路由信令包的数量，由此研究协议之间的相互作用。,不同路由协议/MAC协议组合下的信令开销,信令包在空间的分布,（3）实验设置（1）,Grid Mobility Model：77个节点形成网格网络，方格边长100米；每个节点只能运动到相邻的8个节点之一；节点ID为0-48，从上到下按行编号；ID(mod 4)=0的节点开始向南运动，ID(mod 4)=1的节点开始向北运动，ID(mod 4)=2的节点开始向东运动，ID(mod 4)=3的节点开始向西运动。节点速度：10m/s、20m/s和40m/s三种。 在对角线上建立两条连接。模型特点：节点运动有关联,实验结果（1）,针对不同响应变量的实验：延迟：路由协议、MAC协议和节点速度三者之间存在相互作用；接收的数据包数量：路由协议、MAC协议、节点速度和注入速率之间存在相互作用；公平性：存在路由协议-MAC协议、MAC协议-注入速率两种相互作用。协议比较：CSMA和MACA表现不好，低速下802.11比CSMA和MACA好得多；AODV表现得比DSR或LAR好。,实验设置（2）,Random Waypoint Model：77的网格网络，节点从当前位置向一个随机生成的新位置移动；到达该位置后，重新随机计算一个新位置，立即向该位置移动，中间没有停留时间。模型特点：节点运动完全随机，节点度和连通性随时间变化很大。,实验结果（2）,针对不同响应变量的实验：延迟：MAC协议-注入速率、路由协议-节点速度、路由协议-MAC协议存在相互作用；接收的数据包数量：除路由协议-节点速度之外，其它二者之间都有相互作用；公平性：MAC协议-注入速率、路由协议-MAC协议之间有相互作用。协议比较：CSMA和MACA表现很差，802.11的性能取决于所使用的路由协议，与AODV一起使用时性能最好。,实验设置（3）,Exponential Correlated Random Mobility Model：49个节点随机均匀放置于格点上，按放置顺序编号，ID(mod 4)= i 的节点属于第 i 组。各组遵循以下指数相关随机模型运动:X(t)为 t 时刻一个组的位置（r,），s为组速度矢量；四组节点分别向南、北、东、西四个方向运动，到达边界时运动方向取反。当所有节点方向取反后，组开始向相反方向移动。模型特点：同一个组中各节点之间的相对距离大致稳定，节点度和节点间连能性大致相同。,实验结果（3）,针对不同响应变量的实验：延迟：路由协议、MAC协议和节点速度三者之间有相互作用；接收的数据包数量：除路由协议-注入速率、路由协议-节点速度之外，其它二者之间都有相互作用；公平性：只有路由协议和MAC协议之间有相互作用。协议比较：802.11的性能非常好，MACA的性能比第二个实验有很大改善，而CSMA的性能非常差。同一个组中节点有关联地运动有助于路由选择，并减少了MAC层和路由层上的控制包数量。,结论,没有哪个MAC协议或路由协议绝对优于其它协议，也没有哪个MAC协议和路由协议的组合绝对优于其它协议组合。一般来说，AODV和802.11的组合要比其它组合好。孤立地谈论一个MAC协议或路由协议的好坏没有意义，可以通过设计合适的路由协议来改进某个MAC协议的性能，或通过设计合适的MAC协议来改进某个路由协议的性能。分布式路由协议更适合移动网络。MAC协议在不同的移动模型下性能不同，不仅仅是节点速度影响性能，节点度和连通性也影响协议性能。,3.2 跨层设计的研究现状,分层设计：将网络任务划分到不同的层上，高层协议只使用低层的服务，不关心服务实现的细节，也不需要任何在参考架构中未出现的接口。跨层设计定义为违反某个分层参考架构的协议设计：在层间创建新的接口重新定义层边界基于其它层次的细节来设计某层协议联合调整多个层上的参数,（1）跨层设计的动机,为什么无线链路会刺激设计者违反分层结构的设计原则？无线链路产生的特殊问题在无线链路上机会通信的可能性由无线介质提供的新的通信模式,无线链路的特点,时变信道：由于节点移动、物理环境改变、信道衰落、干扰等引起无线信道随时间和空间而变化，信道条件时好时坏，信道支持的数据速率也随时间而变化。多用户差异：由于不同节点所处的位置、运动速度等的不同，不同用户的信道条件差异很大。,利用物理层信息跨层设计的例子,无线链路上的TCP协议：路由器利用ECN（Explicit Congestion Notificaton）比特显式指示网络中拥塞的发生。CDMA2000：基站根据用户信道的状态进行智能调度，选择信道条件好的用户发送。MAD（Medium Access Diversity）：一种速率自适应方案，通过信道探测了解各个接收端的信道条件，智能调度接收端的发送以最大化链路利用率，并维护节点之间的公平性。,经典冲突模型 VS. 多分组接收模型,到目前为止，随机访问理论都建立在经典的冲突模型基础上，即当只有一个发送器发送时，分组无错误地到达接收节点。随机访问协议被看成是冲突解决方案或冲突避免技术。冲突模型对物理层做了一个简单的抽象，不再适用于无线多址访问信道。 多分组接收模型描述了多用户物理层特性，当k个传输同时进行时，有j个传输能够成功。,MPR模型,由MPR矩阵描述的MPR模型：当有k个用户同时传输时，成功接收的数据包的平均数量是：,基于MPR模型的MAC协议,在物理层上使用MPR模型极大地改变了随机访问问题，传统MAC协议不再适用于MPR信道。service room协议：根据接收历史计算网络状态的后验概率，允许一组用户访问信道。dynamic queue协议：也是一个针对MPR信道设计的随机访问协议。将MPR模型应用于随机访问是当前的一个研究领域，还存在着许多开放的理论问题和实际问题。 MPR的局限性：对称模型，没有考虑多用户差异。,（2）跨层设计方案的分类,7将各种跨层设计方案按照层间耦合的方法分为四类：创建新的接口：用于运行时层间信息共享，按信息流动方向进一步分为向上、向下和双向流动三个子类。相邻层合并：将几个层一起设计，模糊层的边界。设计耦合：设计时耦合两层或多层，但不创建新的接口用于信息共享。跨层垂直调校：联合调谐多个层次的参数。,不同类型的跨层设计,跨层设计的实现,层间直接通信：一层上的变量对另一层是可见的，如使用协议头传递信息。跨层共享数据库：共共享数据库向所有层提供信息存储和获取服务。新的抽象：比如用堆而不是用栈来组织协议。这种协议组织方法允许协议构造块之间更丰富的交互能提供较大的灵活性，但要求全新的系统级实现。,跨层设计的实现类型,（3）开放的问题,对不同跨层设计方案的量化比较研究，从一般性观点推进到特定的整体解决方案。不同跨层设计方案的共存。 什么时候调用一个特定的跨层设计？ 接口的标准化。 物理层应当发挥多大的作用？ 恰当的通信模型。,参考文献,1 Charles E. Perkins, Pravin Bhagwat. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computer. In Proc. of ACM SIGCOMM, Sept., 1994.2 Charles E. Perkins, Elizabeth M. Royer. Ad-hoc On-Demand Distance Vector Routing. IETF RFC 3651,July 2019.3 Brad Karp, H. T. Kung. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In Proc. of MobiCom 2000.4 Jinyang Li, et al. A Scalable Location Service for Geographic Ad Hoc Routing. ?5 Sunil Kumar, Vineet S. Raghavan, Jing Deng. Medium Access Control protocols for ad hoc wireless networks: A survey. sciencedirect.6 Chris Barrett, et.al. Characterizing the Interaction Between Routing and MAC Protocols in Ah-hoc Networks. In Proc. of MobiHoc02, June 9-11, 2019.7 Vineet Srivastava, et. al. Cross-Layer Design: A Survey and the Road Ahead. IEEE Communications Magazine, December 2019.,