一種基于無線網(wǎng)絡的改進自穩(wěn)定領導者選舉算法

帖軍，劉江，王曉華

(中南民族大學 計算機科學學院，武漢430074)

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

關鍵詞自穩(wěn)定領導者選舉算法；無線網(wǎng)絡；概率模型

收稿日期2014-11-20

作者簡介帖軍(1976-)，男，副教授，博士，研究方向:移動數(shù)據(jù)庫，物聯(lián)網(wǎng)應用，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

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

1改進自穩(wěn)定領導者選舉算法

利用IISLE算法的思想，本文提出一種適用于無線網(wǎng)絡的改進自穩(wěn)定領導者選舉算法( ISLEABWN).新的算法改進了樹標識的擴展過程，能夠適應無線網(wǎng)絡環(huán)境下的自穩(wěn)定領導者選舉.

1.1無線網(wǎng)絡體系結構

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

圖1　無線網(wǎng)絡體系結構 Fig.1　Wireless network system structure

1.2移動主機斷接概率模型

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

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

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

(3)每個MH之間相互獨立，對MH本地數(shù)據(jù)的更新由MSS中的代理MHA完成，與其他移動主機無關；

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

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

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

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

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訪問出錯事件：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被更新的次數(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é)點的訪問出錯率:

1.3算法描述

本文基于IISLE算法思想，對IISLE算法進行了改進，給出了適用于無線網(wǎng)絡的改進自穩(wěn)定領導者選舉算法.利用代理MHA代替MH與MSS之間的通信，解決MH頻繁斷接時的通信問題.同時，修改了IISLE算法的樹擴展機制，將MH斷接率概率模型應用到IISLE算法當中，將訪問出錯率低的MH選舉出來.

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

本文給出的改進的算法主要是針對READ_Neighborij過程和REMOVE-CYCLEi過程的改進.READ_Neighborij是在新的無線網(wǎng)絡體系結構下完成，使用本地代理來實現(xiàn)節(jié)點間的可靠通信.REMOVE-CYCLEi過程使用新的樹標識擴展過程來完成.

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

每個節(jié)點Nodei上運行的算法用到的變量說明如下：

(1)sidi表示Nodei所屬的樹的標識；

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

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

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

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

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

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

統(tǒng)計仿真結果得到MH訪問出錯率和選舉算法執(zhí)行時間，如圖2和圖3所示.

圖2　訪問出錯率-斷接概率 Fig.2　Access error rate-disconnection probability

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

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

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

3總結

本文給出了一種基于無線網(wǎng)絡的改進自穩(wěn)定領導者選舉算法，該算法結合了IISLE算法的優(yōu)點，針對無線網(wǎng)絡環(huán)境改進了算法樹標識擴展過程.通過模擬仿真實驗，與AG算法、IISLE算法的性能進行了對比，實驗結果顯示：在無線網(wǎng)絡環(huán)境下，ISLEABWN算法的選舉時間要短于AG算法和IISLE算法.

參考文獻

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

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

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

[4]林克旺.基于分層網(wǎng)絡實現(xiàn)高效的自穩(wěn)定的選舉算法[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]林克旺.一個基于命名網(wǎng)絡的自穩(wěn)定的選舉算法[J].基建優(yōu)化，2006,27(4):60-64.

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

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