论文研究-Ad hoc网络分簇算法的研究 .pdf

所需积分/C币:6 2019-08-16 13:24:50 388KB .PDF

Ad hoc网络分簇算法的研究,袁俊春,李腊元,移动自组织网络(Mobile Ad Hoc Networks)作为一种特殊的多跳移动网络,有着广泛的应用。在一般应用中,Ad Hoc网络可以采用平面结构或分��
国科技论又在线 http://www.paper.edu.cn 2.节点发送信息可以在限定吋问内被所有邻居节点接收到 3.在算法执行时网络拓扑结构不变; 4每个节点记录自己和邻居节点的DD和CID 为了以后描述之便,先对算法中用到的一些符号作以下说明 F:节点和邻居节点ID的集合 my-ID:节点本身的ID; my-CID:节点所处簇的簇首的ID re-ID:接收到广播信息中包含的邻居节点的ID re-CID:接收釗广播信息中包含的邻居节点所处簇的簇首ID; ne-ID:节点记录中邻居节点的ID ne-CI:节点记录中邻居节点所处簇的簇首ID 网络初始化阶段,所冇的节点分别独立进行算法,首先是簇首选举阶段,每个节点的具 体执行过程描述如下: 1若节点ID是集合F中最小值,就将节点的my-CID设置为my-ID,同时向邻居节点广 播一数据包,包含信息(my-ID, my-CID),此节点的集合F减去myID 2节点接收到邻居节点的广擢数据包(re-ID, re-CID)后,将节点记录中的发送此信息的节 点对应的ne-CID设置为re-CID,若接收到的re-ID=re-CI,并且 my-CID未知或者大于 re-CID,将节点的my-CID设置为 re-CID,同时集合F减去re-D 3此时若my-D是集合F的最小值,并且 my-CID未知,就将my-CID设置为my-ID,并 且广播数据包(my-ID,my-CID),集合F减去my-ID,直到集合为空。 最小D簇首选举算法具有以下几个特点: 每个节点可以在其成为最小ID节点时决定其所在簇; 2.簇内每两个节点间最多有两跳 3算法中每个节点只发送一个广播消息,即在自己确定了归属哪个簇时发送广播消息; 4.每个节点只有在自己的ID集合为空时停止算法。 最大连接度法 最大连接度算法,也称为最大度算法( Highest-Degree heuristic)每个节点广播其邻居 节点列表,具有最大连接度(即具有最多邻居)的节点作为簇首,其覆盖范围内的节点作为它 的成员,即普通节点,凡是选择了簇首的节点( covered node)不再参与簇首的选举,木选择簇 首的节点称为“ uncovered node"。直到所有的 uncovered node都变成 covered node,至此簇生 成过程结束。 山由」 Ad hoc网络的拓扑结构总是不断变化,簇生成后,节点的随机移动,会导致在 初始化阶段生成的簇不再满足新的拓扑结枃,因而,需要重新选礻簇首。簇首的频繁更换, 大大影响了其他协议的性能。因而, Ching- Chuan Chiang提出了LCC算法,此算法簇首的 改变只发生在下列两种情况:一种是两个簇首互相处于对方的发射范国:另外一种是一个节 点不属于任何簇。具体操作如下: 1.用最小T或者最大连通法生戍初始的簇; 2.普通节点从一个簇移到另一个簇时,不会发生簇首变化,只是簇成员改变 国科技论又在线 http://www.paper.edu.cn 3.普通节点从当前簇移出,但是没有移入任何个己经存在的簇内时,自己作为簇首 4.簇首节点移入其他簇内时,两个簇首依据最小Ⅲ或者最大连通法竞争簇首职位 传统成簇算法在簇首选举结束后,需要启动簇维护过程来适应网络拓扑结构的变化。 节点权重法 每个节点都依据既定的规则被赋予权重,选举具有最大权重的节点作为簇首,如果节点 只有相同的权重,则选取只有最小ID的节点作为簇首。日目前己使用的作为权重的参量有节 点的移动速度、节点的储能等。我们用无向图G=(VE)来表小 Ad hoc网络拓扑模型,|V n,即有n个节点,(u,ν)是有向图的一条边,表示节点u,v分别在对方的通信范围内 也就是互为邻居节点。对于节点v∈V,r(y)衣示节点v的邻居节点集合。当然在 Ad hoc网络 中,这个有向图不是固定不变的,它会随着节点的移动而改变。网络中的每个节点被赋予唯 的ID,有自己的权重。 依据 Ad hoc网终的特点,成簇算法对网络划分遵循以下原则 1.普通节点的邻居节点中至少有一个簇首节点; 2.普通节点隶属于邻居簇首节点中权重最大的簇; 3.簇首节点不能互为邻居节点。 p首先做两个假定 1.每个节点发送的消息在限定时间内可以被其邻居节点接收到 2.每个节点知道自身和邻居节点的ID和 Weight. DCA算法是消息驱动的,节点依据收 到的消息来确定执行特定的过程,DCA中有两种消息类型:ch(v),节点ⅴ通知其邻居节点自 己要成为簇首join(w,u),节点ⅴ向邻居节点通告自己要加入以节点u为簇首的簇。在节点 中有下列记录(以节点v为例) cluster(v):以ⅴ为簇首的簇包含的节点集合,初始化为空,只有ⅴ为簇首吋才会更新此 Cluster head:节点ⅴ所处簇的簇首ID; ch(-):布尔变量,节点ⅴ发出chv)消息时,将ch(V)置为true,节点v收到其他节点(以 节点u为例)的ch(u消息时,将ch(u)置为tue; join(,-):当节点v收到节点u发来的消息join(αut)、(u∈r(v)t∈)时,将join(u,t)臂 为 true DCA执行的算法 L init过程。节点ⅴ检査在其邻居节点中是否存在比自己权重的节点,若不存在此类节点, 节点发送ch(v),向邻居节点宣布自己成为簇首;若存在此类节点,节点v不动作,等待比自 己权重的节点发送ch(-)消息。 2收到ch(u)消息处理过程。节点v收到一个邻居节点u发来的ch(u)消息后,首先检查 是否己经收到邻居节点中比节点u权重的所有节点发来的已经确定簇首的消息,这样做的 日的是判断当前发送消息的节点是否为最大权重节点(原因是如果收到这些消息,则证明不 会雨收到比u权重的节点发来的成为簇首的消息,也就是说日前节点u是其邻居簇首节点中 权重最大的节点)。若所有比节点u权重的邻居节点均已发出JON消息,则节点ⅴ加入以u 为簇首的簇,退出DCA算法;若仍有比u权重的节点没有确定其簇首,则将ch(u)记录在节 4 山国科技记又在线 http://www.paper.edu.cn 点ⅴ的记录中,等待权重节点发送CH(-)消息。 3收到JON(u,t)消息处理过程。节点v收到邻居节点u发来的JOIN(u,t)消息后,如果节 点ⅴ是簇首,并且消息中的节点t就是节点ⅴ本身,则节点v将u加入到自己的簇内,然后 检査所有权重比自己小的节点是否己经确定了所处簇,若已经确定,节点v退出DCA算法, 否则,再次向其发出CH消息;若节点t不是节点ⅴ本身,节点ⅴ不动作,如果节点ⅴ不是簇 首,节点查是否收到所有比自己权重的节点发来的JOⅣN消息,若收到,置自己为簇首, 冋时检查所有权重比自己小的节点是否己经确定了所处簇,如果已经确定,节点v退出DCA 算法;与此同时,节点ⅴ收到其他节点发来的CH消息,加入最大权重的簇,然后退出DCA 算法 上面介绍的DCA算法在簇生成过程中,节点不能移动或者只能有较小的移动,但 是在 Ad hoc网络中,节点总是在无规则地移动,因而,DCA不适用于Ad-hoc网络,鉴于 上述原因,提出了DMAC算法。在DMAC算法中,每个节点可以感知到连接的断开以及新 连接的建立,对DMAC算法,各个过程是“原子”的,不可以被中断。 节点记录包括以下符号 cluster(v):以ⅴ为簇首的簇包含的节点集合只有v为簇首时才会更新此项: Clusterhead:节点ⅴ所处簇的簇首ID; ch(-):布尔变量,节点v发出ch(v)消息时,将ch(v)置为true,节点v收到其他节点(以 节点u为例)的ch(u)消息时,将ch(u)置为rue; 簇生成之初和新节点加入之前, cluster(v), clusterhead和ch(-)分别设置为空,nl和 false DMAC使用的消息和DCA相同,即CH(-)和JON(-,-)消息,其含义相同。下面分别 介绍DMAC算法的五个执行子过程(对节点v而言)5: init过程。网终初始阶段和新节点加入网终时执行此过程,若邻居节点中存在比自己 权重的簇首节点,就加入此簇;否则,自身作为簇首。 2Link- Failure过程。节点ⅴ检测到与邻居节点u的链路断开时执行此过程,如果节点ⅴ 是簇首,并且节点u是以节点ⅴ为簇首的簇的成员,则节点ⅴ的记录 cluster(v减去u;若节 点ⅴ为普通节点,节点u是节点ⅴ的簇首,此时,节点ⅴ需要决定自己的角色,如果在节点 ⅴ的邻居节点中存在比自己权重的簇首节点z,则加入以节点z为簇首的簇,否则,自身作为 簇首。 3New-link过程。节点ⅴ检测到与节点u出现一条新链路时执行此过程,如果节点u是 簇首,并且比节点v的权重,则节点v加入到以节点u为簇首的簇内。 4收到CH(u)消息处珥过程。节点ⅴ收到节点u发来的CH(u)消息,如果节点u比v当 前所处簇的簇首节点的权重,节点ⅴ就加入以节点u为簇首的簇;否则,节点ⅴ不动作 5收到JOIN(u,以)消息处理过程。如果节点ⅴ是簇首,并且消息中u要加入的簇为簇ⅴ 则节点u加入本簇,若节点u原来属于本簇,现要加入的簇的簇首节点比节点ⅴ权重,则 节点u从木簇移岀;如果节点ⅴ是普通节点,只有节点u是簇首且节点ⅴ是以u为簇首的簇 的成员节点时,节点ⅴ才需要决定自己的角色,此时,节点ⅴ加入邻居簇首节点中最大杖重 的簇,若节点厝围没有簇首节点,置节点ⅴ本身为簇首。 国科技论又在线 http://www.paper.edu.cn 3MACA算法也是消息驱动的,使用三类消息CH(-)、JOIN(,-)消息的含义与DCA算 法相同, RESIGN(w)用来通知权重小于w的簇首节点辞职。节点记求和DCA算法的类似, 包括 cluster(-),ch(-)和 clusterhead。在MACA算法中,节点设置两个参数k和h来适应网终 拓扑的变化,每个节点可以有不同的k和h,并且可以在不同时刻改变他们的值。下面分别 介绍这两个参数 1.节点ⅴ移入以节点u为簇首的簇内时,只有满足wu> wclaster+h(这里h是一个大于 零的实数),节点ⅴ才需要加入簇u。h=0表小每个节点归属于权重最大的簇 2允许簇首节点的邻居节点中可以有不多于k(O≤k<n)个簇首节点,k-0时不允许簇首 节点互为邻居。 下面分别介绍DMAC算法的六个执行子过程(对节点ⅴ而言) Linit过程:簇生成或者有新的节点加入网络时执行此过程,如果节点ⅴ的邻居节点中 存在比自己权重的簇首节点,就加入其中权重最大的簇,否则,节点ⅴ本身作为簇首,然后 检查邻居节点中簇首节点的个数是否人于k个,若是,则发送 RESIGN(w)消息。注意:当簇 生成初始阶段或者同时有两个或两个以上的节点加入到网络时,具有较大权重的节点不能确 定其角色,不过,它终会发送CHG)消息,芍点ⅴ收到此消息时辞职或者加入到此簇。 2.Link- ailure过程:节点ν检测到与节点u的链路断廾时执行此过程,如果节点ⅴ是簇 首,并且节点u是以节点ⅴ为簇首的簇的成员,则节点ⅴ的记录 cluster(v)减去u;若节点v 为普通节点,节点u是节点ⅴ的簇首,此时,节点ⅴ需要决定自己的角色,如果在节点v 的邻居节点中存在比自己权重的簇首节点,则加入具有最大权重的簇,否则,自己作为簇首, 然后和Int过程相似,判断是否需要进行 RESIGN过程。 3.Nw-Link过程。节点ⅴ检测到与芍点u出现一条新链路时执行此过程,如果节点u是 簇首,并且其杈重比节点ⅴ当前所处簇的簇首权重加上门限值h还人,节点v就加入到以节 点u为簇首的簇。另外,如果节点ⅴ本身就是簇首,并且邻居节点中的簇首节点多于k个, 并且存在节点ⅹ的权重比节点的权重小,则节点ⅹ辞职,否则(邻居节点中不存在权重比 节点ⅴ小的簇首节点),节点ⅴ不能继续作为簇首,加入邻居中权重最大的簇。 4收到CH(u)消息处理过程。收到邻居节点u发来的CH(u)消息,并且节点u的权重比 节点ⅴ当前所处簇的簇首权重加上门限值h还大,节点ⅴ就加入到以节点u为簇首的簇。另 外节点ⅴ本身是簇首的话,处理过程与New-Link过程中的相应部分相同。 5收到JoN(u,η)消息处理过程。如果节点ⅴ是簇首,并且消息中u要加入的簇为簇v也 就是说,ⅴ-z),则节点u加入本簇,若节点u原来属于本籐,现要加入的簇的簇首芍点比节 点ⅴ权重,则节点u从本簇移出:如果节点ⅴ是普通节点,只有节点u是簇首且节点ⅴ是以u 为簇首的簇的成员节点时,节点ⅴ才需要决定自己的角色,此时,若节点ⅴ的邻居节点 中存在权重比自身权重大的簇首节点,节点ν加入此类簇首节点中具有最大权重的簇,若节 点周围没有簇首节点,置节点ⅴ本身为簇首,类似于上述3,4中提到的相应处理方法。 6收到 RESIGN(w)消息处理过程。如果节点ν是簇首并且杈重小于w,就辞抻簇首职位, 加入邻居中具有最大权重的簇首节点维护的簇内。 owCA簇首选取算法在系统启动时或者当前簇首不能覆盖其控制域内所有的节点时 被触发。簇首选举过程描述如卜 国科技论又在线 http://www.paper.edu.cn 1.节点发射范围内的邻居节点个数记为d; 2.计算Dv=ldv-MIM为事先设置的簇大小阀值 3.计算和所有邻居节点的距离和Ⅳv; 4.计算节点的平均速度,给出移动性的测定,记为Mv 5.计算节点作为簇首的时间Tv,此参数可以表示节点电池能量的消耗。时间越长 消耗越大。 6.计算节点总的权重I=c1Dv+c2Pv+c3My+c4Tv,参数c1c2c3和c4可以根据网 终特性选取不同的值 7.选取具有最小权重的节点作为簇首,所有包含在凵选簇首通信范围內的节点不再 参与簇首的选取。 8.重复2-7,直到所有的节点分配了所属簇。 现有成簇算法性能比较 表2对各种成簇算法的特点及性能作一总结 算法名称簇首选举依据簇更新成簇期间节点限制簇维护过程开销 最小ID法 节点ID 多 不能移动 小 最大连通法「节点的连接数较少 不能移动 较小 LCC 节点ID或者连接数少 不能移动 较小 DCA 节点权重 不能移动 较人 DMAC 节点权重 可以移动 有有有有无无无 较大 MACA 节点权重 可以移动 较大 WCA 节点权重 少 可以移动 大 总结 在ΔdHoε网络中,基」分簇算法的分级式结枃有利」提高网络的性能,在栘动管理、减 少路由维护代价、资源分配和提髙可扩展性等方面起着重要的作用,同时,分簇算法也会带米 额外的开销因此对特定应用环境选择合适的分簇算法很有必要。 参考文献 [IM Gerla, J TC TsaL Multicluster. mobile, multimedia radio network[J]. Wireless Networks, 1995; 1(3); 255-265 2]Sobrinho J L, Krishnakumar A S Quality of service in Ad Hoc carrier sense multiple access networks. IEEE Journal on selected areas in communication, August, 1999 [3]R Ramanathan, Jason Redi. A Brief Overview of Mobile Ad hoc Networks: Challenges and Directions. IEEE Communications Magazine, 50th Anniversary Commemorative Issue, 2002,(5) 14] Wenli Chen, Nitin Jain, Suresh Singh. ANMP: Ad Iloc network management protocol. IEEE Journal on selected areas in communication, 1999, 17(8) [S]程伟明,周新运.一个用于 Ad hoc刚络的分簇方法计算机学报,2005,28 「6郑少仁,王海涛等. Ad Hoc网络技术M.北京:人民邮电出版社.2005.1 国科技论又在线 http://www.paper.edu.cn Yuan Junchun, Li Dayuan WuHan university of Technology, Wuhan (430063) s a special mobile networks, Ad Hoc network has extensive application In commonly, Ad hoc network using plane structure But, when the scale of Network is very big and need the sustenance of Quality of Service, it using hierarchical structure. Clustering is a mechanism that divides nodes into several logic independent groups. The hierarchical structure resulted from applying clustering algorithm in Ad Hoc is very useful for improving overall performance of network. At First, this paper introduces the composition of clustering algorithm and the standard of evaluating performance of clustering algorithm, analyzes and compares several typical clustering algorithms, and summarizes the existing problems. Ad Hoc networks; clustering; clusterhead

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐