一种基于无线网络的改进自稳定领导者选举算法

一种基于无线网络的改进自稳定领导者选举算法

帖军，刘江，王晓华

(中南民族大学 计算机科学学院，武汉430074)

摘要对IISLE算法进行了分析，IISLE算法的时间复杂度为O(n)，针对无线网络环境的高断接概率，改进了IISLE算法，提出了一种适用于无线网络的改进自稳定领导者选举算法(ISLEABWN).该算法结合移动主机断接概率模型，修改了IISLE算法的树扩展机制.仿真实验结果发现：改进的算法在无线网络环境下具有良好的性能.

关键词自稳定领导者选举算法；无线网络；概率模型

收稿日期2014-11-20

作者简介帖军(1976-)，男，副教授，博士，研究方向:移动数据库，物联网应用，E-mail：Tiejun@mail.scuec.edu.cn

基金项目国家民委科研基金资助项目(CMZY13010)

中图分类号TP312文献标识码A

An Improved Self-Stabilizing Leader Election

Algorithm Based on Wireless Network

TieJun,LiuJiang,WangXiaohua

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

AbstractThis paper analyses IISLE algorithm, and finds out that IISLE algorithm time complexity is O(n). According to the high disconnection probability of wireless network environment, this paper improves IISLE algorithms, and gives an improved self-stabilizing leader election algorithm based on wireless network (ISLEABWN). Combined with the mobile host disconnection probability model, ISLEABWN algorithm modifies the tree expanding mechanism. The emulation experiment results show that the improved algorithm has good performance in wireless network environment.

Keywordsself-stabilizing leader election algorithm；wireless network；probability model

随着分布式系统发展的需要，自稳定性成为分布式系统的设计目标[1-4].目前，研究人员对自稳定选举算法做了诸多研究，并发表了许多相关的选举算法.文献[5]介绍的AG算法能在O(n2)的时间复杂度下解决领导者选举问题.文献[6]介绍的DIM算法能在O(节点最大度*树的深度*logn)的时间复杂度下解决领导者选举问题.文献[7]介绍的IISLE算法利用DIM算法的基本思想，对AG算法进行了改进.IISLE算法不用考虑网络大小，同时改进了DIM算法的树标识的扩展过程，将树标识扩展过程的时间复杂度降至O(1)，该算法的时间复杂度为O(n)(n为网络直径).但是，该算法在无线网络环境下没有较好的性能.本文对现有的自稳定选举算法进行了分析，给出了一种适用于无线网络的改进自稳定选举算法.

1改进自稳定领导者选举算法

利用IISLE算法的思想，本文提出一种适用于无线网络的改进自稳定领导者选举算法( ISLEABWN).新的算法改进了树标识的扩展过程，能够适应无线网络环境下的自稳定领导者选举.

1.1无线网络体系结构

本算法采用的无线网络体系结构(如图1)在移动支持基站(MSS)上对移动主机增加了代理支持.为MSSi覆盖范围内的所有移动主机的集合{MH1,MH2,MH3,…,MHj,…}设置了代理{MHA1,MHA2,MHA3,…,MHAj,…}. 这样可以统一管理节点间的数据通信，每个MHA都与无线网络中的一个MH相对应.MHAi负责MHi处于断接状态时与MSS交互的一切任务，主要包括缓存MSS发给MHi的数据信息，缓存MH发给MSS的数据信息以及MH之间的数据通信.当MH处于断接状态时，MHAi代替MHi与MSS之间的一切交互任务，这样就实现了MH与固定网络之间高质量的数据通信[8,9].

图1　无线网络体系结构 Fig.1　Wireless network system structure

1.2移动主机断接概率模型

首先对模型环境做如下假设：

(1)整个系统中MSS的数量为R；

(2) 每个MSS管辖区MH的数量为S；

(3)每个MH之间相互独立，对MH本地数据的更新由MSS中的代理MHA完成，与其他移动主机无关；

(4)Server对CDB(中心数据库)中任意一个DataItem的写操作服从系数为1/u的指数分布；

(5)MH对EMDB(嵌入式移动数据库)中任意一个DataItem的读操作服从系数为γ的泊松分布；

(6)MH处于频繁断接状态，假设MH处于断接状态的概率为p.

根据以上假设，我们可以估算相关概率：

P[X=0]=pt，其中X=0表示MH处于断接状态，X=1表示MH处于连接状态.

P[X=0,State=Q]=pγe-pγt，其中State=Q表示查询，State=U表示更新操作.

MH访问出错事件：MH要访问的DataItem在MH断接的这段时间被Server修改过至少一次.

P[Y=0]=e-ut，其中Y=0表示Server没有更新DataItem，Y=1表示Server更新了DataItem.

P[Z≥1]=1-e-ut,其中Z表示DataItem被更新的次数.

P[Z≥1，X=0]=(1-e-ut)p,

P[X=0,State=Q,Z≥1]=p2γe-pγt(1-e-ut).

则节点的访问出错率:

1.3算法描述

本文基于IISLE算法思想，对IISLE算法进行了改进，给出了适用于无线网络的改进自稳定领导者选举算法.利用代理MHA代替MH与MSS之间的通信，解决MH频繁断接时的通信问题.同时，修改了IISLE算法的树扩展机制，将MH断接率概率模型应用到IISLE算法当中，将访问出错率低的MH选举出来.

IISLE算法主要分为3个部分：读取邻节点信息READ_Neighborij、环路消除REMOVE-CYCLEi和生成树合并.

本文给出的改进的算法主要是针对READ_Neighborij过程和REMOVE-CYCLEi过程的改进.READ_Neighborij是在新的无线网络体系结构下完成，使用本地代理来实现节点间的可靠通信.REMOVE-CYCLEi过程使用新的树标识扩展过程来完成.

改进的自稳定算法，对环路消除部分进行了改进，主要对(SID_SET, HEIGHT_SET)上定义的偏序关系≥进行了修改，当两个节点所属树的标识符相等时，我们选取访问出错率低的节点作为父节点，另外一个节点作为子节点.

每个节点Nodei上运行的算法用到的变量说明如下：

(1)sidi表示Nodei所属的树的标识；

(2)heighti表示Nodei到根节点的距离；

(3)fi表示Nodei的父节点；

(4)Nbrs_Set(i)表示Nodei的邻接节点集合.

算法NEW-REMOVE-CYCLEi过程描述如下.

Procedure NEW-REMOVE-CYCLEi

INPUT：sidi, heighti, fi, Nbrs_Set(i)

OUTPUT: NULL

1：l=max{j|(sidj,heightj),j∈Nbrs_Set(i)}

2：if fi= null and sidl> sidi

3：while sidl>sidi

4： EXSPAND-SIDi

5：if (sidl,heightl)≥(sidi,heighti)

6：sidi=sidl

7：heighti=heightl+ 1

8：fi=l

9：else

10：heighti= 0

11：fi=null

2模拟仿真

选举时间是衡量选举算法性能的重要指标，随着节点数目的增加，选举时间也会增加.为了能合理地分析ISLEABWN算法的性能优劣，采用AG算法和IISLE算法作为ISLEABWN算法的对比算法.通过使用Sim C++仿真软件包，基于表1给出的仿真实验参数进行仿真实验.仿真实验环境：Windows7 32位操作系统，Intel Core i5-2400 CPU @3.10GHz，4GB内存.

表1　基本参数设置

统计仿真结果得到MH访问出错率和选举算法执行时间，如图2和图3所示.

图2　访问出错率-断接概率 Fig.2　Access error rate-disconnection probability

图3　选举时间-MH数目 Fig.3　Election time-mobile host quantity

分析图2和图3可知，访问出错率随着MH断接概率增加而增大，选举时间随着MH数目的增加而增长.3种算法的选举时间都随着MH数目的增加呈缓慢上升趋势，相比之下，ISLEABWN算法的增幅率低于AG算法和IISLE算法.当系统中MH的数目大于20时，3种算法的选举时间增长都很明显，可见随着移动主机数量的增加，3种算法的性能都明显降低，出现这种现象的主要原因是移动主机数量增加，网络通信量增加，导致网络消息发送、接收延迟，造成选举过程不能按时完成，在图3中的表现为选举时间的延

长.但是，我们还是可以看到ISLEABWN算法的性能要略优于IISLE算法.

3总结

本文给出了一种基于无线网络的改进自稳定领导者选举算法，该算法结合了IISLE算法的优点，针对无线网络环境改进了算法树标识扩展过程.通过模拟仿真实验，与AG算法、IISLE算法的性能进行了对比，实验结果显示：在无线网络环境下，ISLEABWN算法的选举时间要短于AG算法和IISLE算法.

参考文献

[1]Dolev S. Self-stabilization[M]. Cambridge: The MIT Press,2000.

[2]赵致琢,黄小炜,吴文鑫.一种分布式计算中的容错选举算法[J].计算机研究与发展，2008,45(Suppl):93-98.

[3]张刚,陈婧,张宇.分层Ad Hoc网络中同步领导者选举算法的研究[J].计算机仿真，2010,27(3):123-127.

[4]林克旺.基于分层网络实现高效的自稳定的选举算法[J].计算机技术与应用进展，2006,20(12):840-844.

[5]Arora A, Gouda M. Distributed reset[C]// Nori K V, Veni Madhavan C E. Proceedings of the 10th Conference on Foundations of Software Technology and Theoretical Computer Science. Bangalore:Springer-Verlag,1990:316-331.

[6]Dolev S, Israeli A, Moran S. Uniform dynamic self-stabilizing leader election[J]. IEEE Transactions on Parallel and Distributed Systems,1997,8(4):424-440.

[7]林克旺.一个基于命名网络的自稳定的选举算法[J].基建优化，2006,27(4):60-64.

[8]王若滢,李梁,张润洲,等.一种移动数据同步算法[J].计算机技术与发展，2010,20(12):137-140.

[9]帖军，冯忠双.基于优先级的多版本两阶段锁并发控制协议[J].中南民族大学学报：自然科学版，2014，33(1)：100-102.