《【大学课件】信息通信专业 Energy Aware Algorithm in Ad Hoc Networks.ppt》由会员分享，可在线阅读，更多相关《【大学课件】信息通信专业 Energy Aware Algorithm in Ad Hoc Networks.ppt（72页珍藏版）》请在三一办公上搜索。
1、Energy Aware Algorithm in Ad Hoc Networks,我们一组在详细看了mesh网络相关文章之后，决定集中调研mesh网络中的一个子类：Ad Hoc网络。针对目前对于自组织网络的研究焦点集中在节能问题上，特别是在MAC层的节能研究，我们重点调研MAC层的节能机制以及网络层的节能路由机制，对其他方面的节能机制也作了相应调研。,MAC层节能机制研究,我们研究的网络都是基于802.11的无线网络模型，必然有一些最基础的与一般无线不网络相同。例如：RTS、CTS、ACK、CSMA/CA等等。要在MAC层实现节能，必须实行功率控制，或者针对不同功率进行调节。下面分别研究。,
2、Ad Hoc网络功率控制（一）,802.11使用CSMA/CA存在的缺点:空间利用率低，能量效率低，信道干扰大。改进方法：1、以最大功率传送RTS、CTS，然后以最小功率发送ACK 和数据。缺点：降低了吞吐量和传输速度。2、干扰限制的MAC层协议（Interference-Limited Media Access Control）。缺点：但是可能造成误判决；需要收、发两根天线；需要自适应。,3、POWMAC Protocol(power control MAC Protocol)。用滑动访问窗口（access window,AW）储存RTS、CTS序列，AW长度是自适应变化的，将避免碰撞的信息
3、放入CTS中，以确定可能干扰者发送功率的上限，而不是禁止它们发送数据（保持静默），而且干扰的边界也是自适应调整的。,Ad Hoc网络功率控制（二）,提高空间复用可以节约能量。方法：1、解决暴露终端问题。这个方法适用于多跳网络,而并不适于单跳网络。2、通过采用方向性技术。这种方法来提高空间复用的所需的代价太高。3、采用功率控制来提高空间复用。这是我们要研究的方法（DSR MAC协议）。,DSR MAC协议,使用传输的持续时长，状态间距离和通信间的冲突联系而不是第一个通信对作为传输准则。步骤：1、信道接入策略。2、基于距离的冲突推导与IIM设置。,Ad Hoc网络功率控制（三）,在大多数无线通信系
4、统中，信号冲突问题成了主要的限制问题，信号冲突比(SIR)也取代信噪比(SNR)成为系统主要的参数。为了提高SIR，提出一种传输功率控制的非线性优化算法。,传输功率控制的非线性优化算法,无线信道信号传输路径损失函数：P为传输功率，d为传输路径长度，d0为传输参考距离选取合适值使得系数K为1，为路径损失指数，在室内和室外环境中取26之间的数值。,对特定的结点i最大化SIR：N表示基站数，M表示移动终端数，考虑到路径衰减等因素加上权值。对上式分母除以分子后最小化分母即可实现SIR最大化。分母j项可以表示为,取对数 取不等式右端寻找 即可最小化分母实现SIR最大化目标。,控制功率对Ad Hoc网络的
5、影响,对于一个Ad Hoc网络，采用TDMA的介质访问控制协议，对节点划分功率等级，设定传输功率、信噪比等参数。建立SINR干扰模型。进行仿真实验。,网络吞吐量随节点的变化,跳数随节点数变化统计,协调冲突与竞争（一）,MAC层应该解决传输过程中的潜在的争用和冲突。单信道模式下，网络性能随着用户增多而下降，频发的冲突和竞争导致更多的能量损耗。解决方案：1、采用更复杂的多路访问机制。2、电源管理。,多通道思想,动态分配信道给需要的主机。采用RTS/CTS/RES等控制信息使主机得到信道。信道总量一定。不需要同步。我们将使用带电源管理的，动态信道分配控制(DCA-PC)协议。,带电源管理的，动态信道
6、分配控制(DCA-PC)协议,信道模型方面：1个控制信道和n个数据信道。这就要求每个主机有两个半双工的收发器。（一个用于数据信号，一个用于控制信号）。功率控制方面：控制信道采用Pmax传输，数据信道采用适当的P进行传输。,每个主机有三个数据结构：1、CUL：信道利用表。其中成员：host;主机名 Ch；主机所用的信道Rel_time;释放时间Int；是否被主机侦听到2、POWERid：当前主机对主机号为id的主机发送信息所采用的攻率为powerid。3、FCL：空闲的信道表。,通信过程1、计算如果成功握手后，信道是否会有空闲。根据CUL的rel_time进行计算。2、A给B发送RTS，采用Pm
7、ax。3、B收到RTS信号后，检查是否有空闲的数据信道。4、C收到RTS信号后，就隐藏自己一段时间。5、A等待B的CTS信号。,通信过程（续）6、A收到CTS后，执行以下操作：插入CULk，使(Dj为信道j)；广播RES（占用的信道，网络分配的RES的矢量，RES的功率(Pres)）；采用POWER(B)传输数据。7、C收到CTS后，更新CUL。8、C收到RES后，更新CUL。9、B收到整个数据包后，回复A。采用功率POWERA。,DCA-PC仿真实验,信道数量影响：总的DCA-PC的效果比DCA好，但是随着信道数的增加，功率控制的意义会下降。,固定信道带宽下，情况同上面的相似。,主机密度的影
8、响：主机密度大的时候，DCA-PC的效果好，从而说明了功率控制在主机密度大的时候非常有用。,功率级数数量的影响：采用更多的功率级数，使主机对外界的抗干扰能力增加，从而使信道利用率增加。,主机移动速度的影响：虽然DCA-PC，性能下降会快一些，但是仍然比DCA的性能要好。,协调冲突与竞争（二）,整个网络被部分脱节的广播域或碰撞域所分割。任意节点在确认自身的位置后将告知相邻节点信道的预定信息。节点仅在传输信息时竞争并分配信道和发送FI帧（Frame Information）。缺点：信道的状态信息不能及时更新。优点：节省能量；对任意进入信道中的状态做实时的维护。,能量节省率,MAC层路由协议（一）,
9、引入多类路由的概念(MC)具有骨干能力结点(backbone-capablenodes,BC nodes)：数据传输量大，健壮性好，处理能力强的结点。MC路由的主要思想就是让大多数路由由这些骨干结点来承担。,MC路由,优点：其更加稳定，纠错能力更强。可提供更大的传输量。因为骨干结点的处理能力更强降低了中间的跳转。因为骨干结点的传输半径大得多。,1、峰窝结构(Cell Structure)在每个Cell中，有一个从BC结点中挑选一个B结点，并且B结点可以与其相邻的Cell中的任意一个B结点直接通信。并假设这些结点只在限定的地方活动。,2、B结点的选择首先每个峰窝结构中，从BC结点中挑选出一个作为
10、B结点，如果B结点离开了所属的区域，就要重新从BC结点中选出一个B结点。B结点的离开，或者是G结点发现其所在的区域内没有B结点，那么，它们就会发出广播信息。收到广播信息的BC结点就会广播，其将成为新的B结点。,3、多类路由协议每个结点有其固定的id，每个区域也有其固定的id。B结点有它的第二个id，用于区域间的通信。B结点离开时，发出广播信信，让其它的BC结点竞选一个成为B结点。B结点间的路由：采用B结点的第二个id。用于CELL间的通信。寻路：假设S结点要给在不同区域的D结点发送数据，通过RR来寻路。寻路后，在所在的路上进行通信。路由修复：如果在上述路由中出现了故障，发现在路中有个区域没有B
11、节点，那么它就通过广播RE(route repair)数据包进行路由修复。普通结点的路由：结点首先通过在其区域内广播RR数据包来寻找其最近邻的B结点。B结点收到后，回复S结点一个RP信号。如果S没有收到RP信号，那么就可以确定该区域内没有B结点。,4、分发结点位置信息。在结点没有离开其所在的区域时，不用发送其位置信息；若结点离开了其所在的区域的话，发送位置更新信息的数据包给其所在的新的B结点，另处，B结点定期的将其所收集到的信息发送给一个B0结点。注意更新的信息不应太大，否则就不够精确，也不能太小。最好选择一个固定的B0结点。5、新的MAC层协议。,MAC层路由协议（二）,通过能量效率比较来选
12、取最佳邻居节点 定义P(I,J)为节点I向节点j传输数据所需要的传输功率,并且节点I拥有一张邻居节点表单,上面按传输功率大小排定I的所有邻居J1,J2假定I要发送数据给Jl,它并不急于选择直接向Jl发送数据,而是先在它的邻居表单里寻找是否有满足以下关系的节点存在,如果存在这样的节点jq,则I将jl从他的邻居节点表单里删除,并且发送数据给jq,通过jq转发给jl。,算法假定：网络的拓扑结构应为准静态的。每一个节点都能够对自己的相关位置进行评估。每个节点都可以调整他的传输功率,用以到达不同的邻居节点。,地址广播：每一个节点以他的全输出功率将自己的地址信息广播出去，每一个节点都形成一张如下图的表单,
13、Pat广播阶段：每一个节点将他之前形成的表单再次广播出去，每一个节点将之前的表单加以修改,变成如下的表单,SON阶段：采用下面的模型来进行最佳邻居选择 SON的两种分支 SCON和SEEON。对SCON来说,只要离他最远的邻居节点满足上面的不等式,则离他较近的不满足不等式的邻居节点继续保留在Pat表中,而SEEON则对其PAT表中的所有节点进行检查,剔除所有不满足上面不等式的邻居节点,平衡阶段：每一个节点都以全功率广播自己的邻居节点列表,当A接受到B的邻居列表并且发现自己不在其中时,A将把B从邻居列表中剔除。为了达到功率的最优化使用,如果只使用SON是不够的,节点必须按照发送距离的远近调整自己
14、的发送功率,才能最终实现能量的最优化使用。,仿真实验,设立了一个100节点，区域为500m*500M的ad hoc网络，相关参数如下表,没有进行Son之前的网络拓扑结构,SCON和SEEON后,可以发现网络结构大大简化,节点的平均通信功率发生了显著的下降,如下图,最终的能量节省,网络层节能路由协议（一）,在网络层需要设计特殊的路由协议达到节能目的。采用多信道最小能量路由（Multipath Minimum Energy Routing mechanism，简称MMER），利用多信道分流流量来使链路的能量代价总合最小。,多信道最小能量路由（MMER）,Ad Hoc网络有N个节点和L条链路组成。网
15、络中有W对源-目标节点对，每一对w=(s,d)，Pw为该对的通道集合，rw为源到目的节点的数据包传送速率，Xwp为Pw中一条信道p的传送速率。,总的能量损耗为 我们的目标是,基于分布式协调函数（Distributed Coordination Function，简称DCF）有两种访问方法：一种叫基本访问方法，另一种叫RTS/CTS访问方法。基本访问方法只有数据帧和ACK帧，会产生“隐藏终端问题”，为此我们用RTS/CTS访问方法。这种方法在传输庞大数据帧前优先使用小的RTS、CTS帧。,RTS/CTS访问方法,梯度投射算法：向量x在梯度相反的地方被迭代修正，以适应最佳化的问题 流量分配只需由一
16、对接点来决定而不需要考虑其他节点,仿真实验,网络结构,节点固定情况节点0处的调整情况,节点移动情况,网络层节能路由协议（二）,采用区域路由通信方案。用于Ad Hoc传感器网络。基于以下事实：每个节点有一个两跳范围的临近节点列表，两个触发式目标引导一个简单地分布式推理机制。使用TDMA通信机制。,区域路由通信,设想一个网络：每个节点可以唯一确定，并且可以和临近节点建立直接连接的链路；在一个给定的节点对中，每个节点可以是源节点、目的节点或者是中间节点；没有中心控制机制或者关于网络结构以及其他节点位置的先验信息；存在一个发现邻居节点的阶段，在该阶段中，邻居节点允许一个时隙的通信，该过程是分布式的；,
17、在发现阶段之后，每个节点只能在T个时隙之后才能与邻居节点通信，从而保持每个节点尽可能处于空闲状态中，这样每个节点只在T时间的一小步份时间内进行传送，如图Fig1所示的例子。W、Y、Z是节点X的邻居节点；,所有传感器是理想的同步的；有些节点是可移动的，因此任何路由都可能会改变，这意味着当某节点药通信时必须进行路由发现，后面会假设报文随着路由发现过程发送。,算法的描述：1、初始化阶段 邻居发现过程：每个节点在一个时隙内寻找自己的邻居节点,路由表修订过程：每个节点广播自己的一跳联系表，该过程结束时，每个节点拥有一个两跳范围节点的联系表,2、路由阶段 除去冗余，对可能的路由器进行评估。对可能的路径进行
18、评估。发送数据给可能节点或目的节点。,仿真实验,网络结构,第一列节点发送必要报文给最后一列任一节点的平均数量（有6列，每列10个节点）,每列20个节点的网络的相同仿真,各种算法到达目的节点的平均时隙数量,Ad Hoc网络有向性接收研究,采用一种传播策略根据端点服务等级来分配自身资源想实现信号发送和接收的全方向化 相比较一般的有向性传输或接收具有以下几个特点：假定传输和接收都具有方向性分布式，仅需要本地的资源根据需求对不同的连接分配不同的资源在邻结点发现和预留阶段进行功率控制，在数据传输阶段有效地减小过载,假定所有传输结点使用一种易于操纵天线的收发机，同步并且有以下性质：通信半双工，但可以根据需
19、要随时转变收发模式；在180度范围内可以有向地接收和发送；所有结点自身时间统一。,帧结构,发送方按照一定的方位顺序扫描邻结点，发送广播帧(Advertisement)，邻结点检测到以后回应帧，并等待确认帧他们的方位角和高度仰角满足如下关系 建立连接后选择发送或接收模式 3次握手信号 准备在将来某个时间段再保证连接和预留信息,Ad Hoc网络的分簇研究,建立拓扑结构，并对相距比较近的节点进行聚类，并把它们分类从每一类中根据功控算法或者其他算法挑出一些节点，组成主干连接节点集（connected dominating sets），路由器选择路由时会优先选择这里面的节点，剩余的节点就是普通节点，主干连接节点集中的节点也是轮流被路由器选中，以使各个使用的功率尽可能公平,其他,将有向性传输应用于分簇网络中，可以减少信道干扰，提高带宽利用率。利用CDMA的强抗干扰特性，减少信道干扰，并且可以使得多对数据在同一信道中传输，节省带宽。,Thank you!,2006.12.23,
