第07次课-移动计算技术--Ad-hoc分群技术

授课教师：赵蕴龙Email：[e-mail]移动计算技术——MANETs专题：分群技术无线自组网分群技术Adhoc网络结构平面结构分级结构无线自组网分群技术平面结构网络中所有的节点的功能和地位平等无需任何结构维护过程源节点和目的节点之间可存在多跳路径原则上不存在瓶颈而比较健壮，相对安全网络规模受限，可扩充性差无线自组网分群技术分级结构为了提高adhoc的可扩展性采用分布式的控制方式常用的方式是分级分布式——网络分级结构借助节点的自组织功能来完成无线自组网分群技术分级结构在分级结构中，网络被分为群每个群有一个群首和多个群成员组成群首形成了高一级的网络高一级的网络又可以分成群在分级结构中，群首和群成员的身份可动态变化，节点仍然自动组网无线自组网分群技术分级结构在分级结构中，群首节点负责群间的数据转发、协调和管理，使群内节点合理工作群首可以预先指定，也可以由节点使用分群算法自动选举产生群首与基站的区别是没有专有的硬件，本身也可以是一个移动的节点与普通节点相比，要处理额外的工作，因此可能成为系统的瓶颈无线自组网分群技术单频分级所有机点使用一个频率通信为了实现群首之间的通信，要有网关节点的支持网关节点同时属于两个群群首和网关形成高一级的网络——虚拟骨干网无线自组网分群技术多频分级不同级采用不同的频率低级节点的通信范围小高级节点的覆盖范围大无线自组网分群技术无线自组网分群技术分级结构的优点分级有较好的扩展性，网络的规模在很大程度上不受限制路由和控制开销相对较小分级结构通过路由信息的局部化提高系统的吞吐量分级结构中的节点的定位比平面结构简单得多，群首节点知道群成员的位置无线自组网分群技术分级结构的缺点维护分级结构需要节点执行复杂的群首选举算法群首节点可能会成为网络的瓶颈群间信息通过群首寻路，不一定能使用最佳路由无线自组网分群技术分群算法满足假设：在网络初始化时，每个节点可以通过交互控制消息通知其邻节点的ID号一个节点发出的消息能够被其所有的邻居节点在很短的时间正确接收在分群算法执行期间，网络的拓扑不发生改变无线自组网分群技术分群管理与分群路由分群算法为路由算法提供了一个逻辑拓扑可以从路由算法中获得反馈，以便对拓扑进行调整进而做出新的分群判断无线自组网分群技术分群路由节点大致分为3类，群首节点、普通节点、网关节点网络中的所有节点可以充当群首、普通和网关节点群首节点只能够保存整个群的节点信息普通节点只了解其邻居节点的信息同一分群内的相邻节点分组数据直接传送，非相邻节点间数据分组经过群首转发无线自组网分群技术跨群分组首先经群首确认为跨群分组群首通过网关节点用按需路由的方式建立路由无线自组网分群技术无线自组网分群技术分群管理与分群路由的比较分群管理仅仅是引入群首作为中间节点，以减小消息的开销目标与路由分群不同，功能比路由分群弱分群路由中的群首节点负责跨群分组的路由分群的基本目标是维护路由无线自组网分群技术分群算法能够以很少的控制开销是实现快速部署典型的分群算法最小的ID算法需要每个节点发送两次控制信息最大连接度算法需要每个节点发送三次控制信息•最小的ID分群算法•最大的连接度分群算法无线自组网分群技术链路分群算法最小ID分群算法链路分群最大连接度分群基本最小ID分群基于最小的ID算法的移动分群无线自组网分群技术链路分群算法一个比较分散的区域中有N个节点，标识为1,2,3,……,N采用分布式控制方案一个节点通过探询方式获得与其邻近节点的信息广播探询信号获得探询信号的节点向该节点发送应答信号无线自组网分群技术通过这种方法可以得到节点的邻接矩阵当第i个节点与第j个节点不邻接时，aij=0当第i个节点与第j个节点邻接时，aij=1假设不存在单向信道，那么aij=aji无线自组网分群技术设N={1,2,…..,N}为网络的总节点集Nabj（i）表示与节点i相邻节点的集合Ntotal（i）表示包括节点i本身以及其所有相邻节点的集合Ci表示第i个链路分群无线自组网分群技术链路分群算法LCA（LinkedClusterAlgorithm）任意选取节点i作为第一个群首节点集Ntoatal（i）中所有的节点均处于第一个链路分群Ci，所有这些节点都成为Ci的成员从节点N-Ntoatal（i）中再选取一个节点j作为第二个群首Cj无线自组网分群技术节点集依次类推，直到每一个节点都成为某个群的成员，链路分群过程结束构成群Cj无线自组网分群技术LCA存在以下不足对自组网的组网问题没有进行系统模型化的数学描述，不利于组网算法的设计、优化和实现群首或群的数目过多，不利于在给定条件下获取简单的网络结构网关节点选取的模糊性无线自组网分群技术最大的连接度算法算法思想：尽量减小群的数目节点之间经过交互控制消息，知道相邻节点的数目该节点和相邻节点中连接度最大的节点被选为群首度数相同选最小的ID节点群首节点的一跳邻居节点则成为该群的普通节点无线自组网分群技术节点i的度数DN(i)定义为如果节点k满足无线自组网分群技术则节点k被选为第一个群首C1令如果无线自组网分群技术那么k’被选为第二个群首C2每个节点广播它可以听到的所有节点的列表（包括自己）依此类推，直到链路分群划分完毕在其所有尚未被覆盖的邻居节点中具有最大接结度的节点被推为群首未推举其群首的节点为尚未被覆盖节点，否则为覆盖节点已推举其它节点为群首的节点不应再作为群首无线自组网分群技术当两个相邻的链路分群交叠时，如果公共节点多于一个按照连接度最小的原则选一个节点作为两个群的网关节点当两个群相邻且不相交，从两个群中各选一个节点构成网关节点对两个节点度数之和最小无线自组网分群技术最大连接度算法的优点群的数目较少，减少了分组的投递时延由于群的数目较少，信道的空间重用率低在群内信道资源通常由群内节点按照轮寻的方式共享如果群内节点数过多，每个节点的吞吐量将急剧下降节点移动将导致群首身份的变化，引起大量的维护开销无线自组网分群技术最小ID分群算法基本最小ID分群算法给网络的每个节点分配唯一的ID号节点与相邻节点交换所听到的ID号，选择最小的ID号节点作为群首节点计算量小，实现方便，算法收敛较快群首更新频率较慢，维护群所花费的开销较小无线自组网分群技术基本最小ID分群算法描述一个节点只有在听到的所有节点的ID号都大于自己的ID号时才能成为群首节点把所听到的具有最小ID号的节点作为其群首，除非该最小ID号的节点明确放弃群首身份可以听到两个或多个群首的节点为网关除此以外，节点作为普通节点无线自组网分群技术算法的特点ID号越小，成为群首的可能性越大每个节点成为群首的可能性时不同的较小ID的节点将消耗更多的电池能量缩短了整个网络出现分割的时间没有考虑负载平衡等因素的影响无线自组网分群技术最小ID和最大连通度算法群首不直接相连群内任意节点距离最多相距两跳群内所有的节点和群首直接相连无线自组网分群技术分群算法的性能假定节点随机移动和预定义移动类型两种情况下改变群首身份的节点数拓扑结构变化后分群结构的变化最小ID算法的性能均优于最大连接度算法无线自组网分群技术无线自组网分群技术基于最小ID算法的移动分群算法为了支持移动性,采用无群首的分群结构全网节点以任意顺序发送一轮控制分组节点了解邻居节点的情况执行分群算法因移动发生拓扑结构变化时,采用分群保持的策略无线自组网分群技术算法描述(1)如果本节点ID为所有邻居节点中ID最小,则宣布成立新群,群号为本节点的ID；否则执行(2)或(3)(2)一直等待直道收到邻居节点中宣布成立新群的控制消息，将该节点加入新群并广播这一中情况(3)在(2)中，如果发现比自己ID小的节点都已经宣布加入其他群而自己又未被包括在这些群中，则宣布自己成立新群无线自组网分群技术分群保持移动性支持是adhoc网络要主要考虑的因素之一分群保持路由保持无线自组网分群技术分群保持的要求拓扑变化引起的分群结构的变化最小可以用很小的控制开销恢复稳定的通信结构分群变化后分群保持策略引起的变化最小无线自组网分群技术移动分群保持若节点发现本群内的节点出现3跳开始实行分群保持策略判断哪个节点该离开原群的方法•根据节点本身在群内的一跳邻居节点数、三跳节点数和它们的ID号的大小判断无线自组网分群技术三种情况若节点i在本群的一跳邻居节点数小于在该群的三跳节点数，则节点i出群若节点i在本群的一跳邻居节点数大于在该群的三跳节点数，则节点i不出群若节点i在本群的一跳邻居节点数等于在该群的三跳节点数，比较节点i和它在群中的邻居节点、三跳节点的ID大小，将最小ID的节点及其邻居节点保留在原群中，其余节点出群无线自组网分群技术算法的特点有群首的分群协议比无群首的分群协议要处理的节点变化的情况多节点交换的控制开销多移动分群协议在相同条件下只对最少的节点变化进行处理移动分群协议的群的生存时间要比有群首的协议的生存时间长无线自组网分群技术