一種基于無(wú)線網(wǎng)絡(luò)的改進(jìn)自穩(wěn)定領(lǐng)導(dǎo)者選舉算法

一種基于無(wú)線網(wǎng)絡(luò)的改進(jìn)自穩(wěn)定領(lǐng)導(dǎo)者選舉算法

帖軍，劉江，王曉華

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢430074)

摘要對(duì)IISLE算法進(jìn)行了分析，IISLE算法的時(shí)間復(fù)雜度為O(n)，針對(duì)無(wú)線網(wǎng)絡(luò)環(huán)境的高斷接概率，改進(jìn)了IISLE算法，提出了一種適用于無(wú)線網(wǎng)絡(luò)的改進(jìn)自穩(wěn)定領(lǐng)導(dǎo)者選舉算法(ISLEABWN).該算法結(jié)合移動(dòng)主機(jī)斷接概率模型，修改了IISLE算法的樹(shù)擴(kuò)展機(jī)制.仿真實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)：改進(jìn)的算法在無(wú)線網(wǎng)絡(luò)環(huán)境下具有良好的性能.

關(guān)鍵詞自穩(wěn)定領(lǐng)導(dǎo)者選舉算法；無(wú)線網(wǎng)絡(luò)；概率模型

收稿日期2014-11-20

作者簡(jiǎn)介帖軍(1976-)，男，副教授，博士，研究方向:移動(dòng)數(shù)據(jù)庫(kù)，物聯(lián)網(wǎng)應(yīng)用，E-mail：Tiejun@mail.scuec.edu.cn

基金項(xiàng)目國(guó)家民委科研基金資助項(xiàng)目(CMZY13010)

中圖分類號(hào)TP312文獻(xiàn)標(biāo)識(shí)碼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

隨著分布式系統(tǒng)發(fā)展的需要，自穩(wěn)定性成為分布式系統(tǒng)的設(shè)計(jì)目標(biāo)[1-4].目前，研究人員對(duì)自穩(wěn)定選舉算法做了諸多研究，并發(fā)表了許多相關(guān)的選舉算法.文獻(xiàn)[5]介紹的AG算法能在O(n2)的時(shí)間復(fù)雜度下解決領(lǐng)導(dǎo)者選舉問(wèn)題.文獻(xiàn)[6]介紹的DIM算法能在O(節(jié)點(diǎn)最大度*樹(shù)的深度*logn)的時(shí)間復(fù)雜度下解決領(lǐng)導(dǎo)者選舉問(wèn)題.文獻(xiàn)[7]介紹的IISLE算法利用DIM算法的基本思想，對(duì)AG算法進(jìn)行了改進(jìn).IISLE算法不用考慮網(wǎng)絡(luò)大小，同時(shí)改進(jìn)了DIM算法的樹(shù)標(biāo)識(shí)的擴(kuò)展過(guò)程，將樹(shù)標(biāo)識(shí)擴(kuò)展過(guò)程的時(shí)間復(fù)雜度降至O(1)，該算法的時(shí)間復(fù)雜度為O(n)(n為網(wǎng)絡(luò)直徑).但是，該算法在無(wú)線網(wǎng)絡(luò)環(huán)境下沒(méi)有較好的性能.本文對(duì)現(xiàn)有的自穩(wěn)定選舉算法進(jìn)行了分析，給出了一種適用于無(wú)線網(wǎng)絡(luò)的改進(jìn)自穩(wěn)定選舉算法.

1改進(jìn)自穩(wěn)定領(lǐng)導(dǎo)者選舉算法

利用IISLE算法的思想，本文提出一種適用于無(wú)線網(wǎng)絡(luò)的改進(jìn)自穩(wěn)定領(lǐng)導(dǎo)者選舉算法( ISLEABWN).新的算法改進(jìn)了樹(shù)標(biāo)識(shí)的擴(kuò)展過(guò)程，能夠適應(yīng)無(wú)線網(wǎng)絡(luò)環(huán)境下的自穩(wěn)定領(lǐng)導(dǎo)者選舉.

1.1無(wú)線網(wǎng)絡(luò)體系結(jié)構(gòu)

本算法采用的無(wú)線網(wǎng)絡(luò)體系結(jié)構(gòu)(如圖1)在移動(dòng)支持基站(MSS)上對(duì)移動(dòng)主機(jī)增加了代理支持.為MSSi覆蓋范圍內(nèi)的所有移動(dòng)主機(jī)的集合{MH1,MH2,MH3,…,MHj,…}設(shè)置了代理{MHA1,MHA2,MHA3,…,MHAj,…}. 這樣可以統(tǒng)一管理節(jié)點(diǎn)間的數(shù)據(jù)通信，每個(gè)MHA都與無(wú)線網(wǎng)絡(luò)中的一個(gè)MH相對(duì)應(yīng).MHAi負(fù)責(zé)MHi處于斷接狀態(tài)時(shí)與MSS交互的一切任務(wù)，主要包括緩存MSS發(fā)給MHi的數(shù)據(jù)信息，緩存MH發(fā)給MSS的數(shù)據(jù)信息以及MH之間的數(shù)據(jù)通信.當(dāng)MH處于斷接狀態(tài)時(shí)，MHAi代替MHi與MSS之間的一切交互任務(wù)，這樣就實(shí)現(xiàn)了MH與固定網(wǎng)絡(luò)之間高質(zhì)量的數(shù)據(jù)通信[8,9].

圖1　無(wú)線網(wǎng)絡(luò)體系結(jié)構(gòu) Fig.1　Wireless network system structure

1.2移動(dòng)主機(jī)斷接概率模型

首先對(duì)模型環(huán)境做如下假設(shè)：

(1)整個(gè)系統(tǒng)中MSS的數(shù)量為R；

(2) 每個(gè)MSS管轄區(qū)MH的數(shù)量為S；

(3)每個(gè)MH之間相互獨(dú)立，對(duì)MH本地?cái)?shù)據(jù)的更新由MSS中的代理MHA完成，與其他移動(dòng)主機(jī)無(wú)關(guān)；

(4)Server對(duì)CDB(中心數(shù)據(jù)庫(kù))中任意一個(gè)DataItem的寫(xiě)操作服從系數(shù)為1/u的指數(shù)分布；

(5)MH對(duì)EMDB(嵌入式移動(dòng)數(shù)據(jù)庫(kù))中任意一個(gè)DataItem的讀操作服從系數(shù)為γ的泊松分布；

(6)MH處于頻繁斷接狀態(tài)，假設(shè)MH處于斷接狀態(tài)的概率為p.

根據(jù)以上假設(shè)，我們可以估算相關(guān)概率：

P[X=0]=pt，其中X=0表示MH處于斷接狀態(tài)，X=1表示MH處于連接狀態(tài).

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

MH訪問(wèn)出錯(cuò)事件：MH要訪問(wèn)的DataItem在MH斷接的這段時(shí)間被Server修改過(guò)至少一次.

P[Y=0]=e-ut，其中Y=0表示Server沒(méi)有更新DataItem，Y=1表示Server更新了DataItem.

P[Z≥1]=1-e-ut,其中Z表示DataItem被更新的次數(shù).

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

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

則節(jié)點(diǎn)的訪問(wèn)出錯(cuò)率:

1.3算法描述

本文基于IISLE算法思想，對(duì)IISLE算法進(jìn)行了改進(jìn)，給出了適用于無(wú)線網(wǎng)絡(luò)的改進(jìn)自穩(wěn)定領(lǐng)導(dǎo)者選舉算法.利用代理MHA代替MH與MSS之間的通信，解決MH頻繁斷接時(shí)的通信問(wèn)題.同時(shí)，修改了IISLE算法的樹(shù)擴(kuò)展機(jī)制，將MH斷接率概率模型應(yīng)用到IISLE算法當(dāng)中，將訪問(wèn)出錯(cuò)率低的MH選舉出來(lái).

IISLE算法主要分為3個(gè)部分：讀取鄰節(jié)點(diǎn)信息READ_Neighborij、環(huán)路消除REMOVE-CYCLEi和生成樹(shù)合并.

本文給出的改進(jìn)的算法主要是針對(duì)READ_Neighborij過(guò)程和REMOVE-CYCLEi過(guò)程的改進(jìn).READ_Neighborij是在新的無(wú)線網(wǎng)絡(luò)體系結(jié)構(gòu)下完成，使用本地代理來(lái)實(shí)現(xiàn)節(jié)點(diǎn)間的可靠通信.REMOVE-CYCLEi過(guò)程使用新的樹(shù)標(biāo)識(shí)擴(kuò)展過(guò)程來(lái)完成.

改進(jìn)的自穩(wěn)定算法，對(duì)環(huán)路消除部分進(jìn)行了改進(jìn)，主要對(duì)(SID_SET, HEIGHT_SET)上定義的偏序關(guān)系≥進(jìn)行了修改，當(dāng)兩個(gè)節(jié)點(diǎn)所屬樹(shù)的標(biāo)識(shí)符相等時(shí)，我們選取訪問(wèn)出錯(cuò)率低的節(jié)點(diǎn)作為父節(jié)點(diǎn)，另外一個(gè)節(jié)點(diǎn)作為子節(jié)點(diǎn).

每個(gè)節(jié)點(diǎn)Nodei上運(yùn)行的算法用到的變量說(shuō)明如下：

(1)sidi表示Nodei所屬的樹(shù)的標(biāo)識(shí)；

(2)heighti表示Nodei到根節(jié)點(diǎn)的距離；

(3)fi表示Nodei的父節(jié)點(diǎn)；

(4)Nbrs_Set(i)表示Nodei的鄰接節(jié)點(diǎn)集合.

算法NEW-REMOVE-CYCLEi過(guò)程描述如下.

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模擬仿真

選舉時(shí)間是衡量選舉算法性能的重要指標(biāo)，隨著節(jié)點(diǎn)數(shù)目的增加，選舉時(shí)間也會(huì)增加.為了能合理地分析ISLEABWN算法的性能優(yōu)劣，采用AG算法和IISLE算法作為ISLEABWN算法的對(duì)比算法.通過(guò)使用Sim C++仿真軟件包，基于表1給出的仿真實(shí)驗(yàn)參數(shù)進(jìn)行仿真實(shí)驗(yàn).仿真實(shí)驗(yàn)環(huán)境：Windows7 32位操作系統(tǒng)，Intel Core i5-2400 CPU @3.10GHz，4GB內(nèi)存.

表1　基本參數(shù)設(shè)置

統(tǒng)計(jì)仿真結(jié)果得到MH訪問(wèn)出錯(cuò)率和選舉算法執(zhí)行時(shí)間，如圖2和圖3所示.

圖2　訪問(wèn)出錯(cuò)率-斷接概率 Fig.2　Access error rate-disconnection probability

圖3　選舉時(shí)間-MH數(shù)目 Fig.3　Election time-mobile host quantity

分析圖2和圖3可知，訪問(wèn)出錯(cuò)率隨著MH斷接概率增加而增大，選舉時(shí)間隨著MH數(shù)目的增加而增長(zhǎng).3種算法的選舉時(shí)間都隨著MH數(shù)目的增加呈緩慢上升趨勢(shì)，相比之下，ISLEABWN算法的增幅率低于AG算法和IISLE算法.當(dāng)系統(tǒng)中MH的數(shù)目大于20時(shí)，3種算法的選舉時(shí)間增長(zhǎng)都很明顯，可見(jiàn)隨著移動(dòng)主機(jī)數(shù)量的增加，3種算法的性能都明顯降低，出現(xiàn)這種現(xiàn)象的主要原因是移動(dòng)主機(jī)數(shù)量增加，網(wǎng)絡(luò)通信量增加，導(dǎo)致網(wǎng)絡(luò)消息發(fā)送、接收延遲，造成選舉過(guò)程不能按時(shí)完成，在圖3中的表現(xiàn)為選舉時(shí)間的延

長(zhǎng).但是，我們還是可以看到ISLEABWN算法的性能要略優(yōu)于IISLE算法.

3總結(jié)

本文給出了一種基于無(wú)線網(wǎng)絡(luò)的改進(jìn)自穩(wěn)定領(lǐng)導(dǎo)者選舉算法，該算法結(jié)合了IISLE算法的優(yōu)點(diǎn)，針對(duì)無(wú)線網(wǎng)絡(luò)環(huán)境改進(jìn)了算法樹(shù)標(biāo)識(shí)擴(kuò)展過(guò)程.通過(guò)模擬仿真實(shí)驗(yàn)，與AG算法、IISLE算法的性能進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果顯示：在無(wú)線網(wǎng)絡(luò)環(huán)境下，ISLEABWN算法的選舉時(shí)間要短于AG算法和IISLE算法.

參考文獻(xiàn)

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

[2]趙致琢,黃小煒,吳文鑫.一種分布式計(jì)算中的容錯(cuò)選舉算法[J].計(jì)算機(jī)研究與發(fā)展，2008,45(Suppl):93-98.

[3]張剛,陳婧,張宇.分層Ad Hoc網(wǎng)絡(luò)中同步領(lǐng)導(dǎo)者選舉算法的研究[J].計(jì)算機(jī)仿真，2010,27(3):123-127.

[4]林克旺.基于分層網(wǎng)絡(luò)實(shí)現(xiàn)高效的自穩(wěn)定的選舉算法[J].計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展，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]林克旺.一個(gè)基于命名網(wǎng)絡(luò)的自穩(wěn)定的選舉算法[J].基建優(yōu)化，2006,27(4):60-64.

[8]王若瀅,李梁,張潤(rùn)洲,等.一種移動(dòng)數(shù)據(jù)同步算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2010,20(12):137-140.

[9]帖軍，馮忠雙.基于優(yōu)先級(jí)的多版本兩階段鎖并發(fā)控制協(xié)議[J].中南民族大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，33(1)：100-102.