一種新的基于粗糙集理論的ＷＳＮ分簇算法
2009-01-01 00:00:00羅俊薛勝軍趙娟娟談冉
計算機應用研究 2009年1期
(武漢理工大學 計算機科學與技術學院， 武漢 430063)
摘 要：利用粗糙集理論解決不確定性問題的優勢，首次將粗糙集理論應用到無線傳感器網路分簇算法中，提出了一種新的分簇算法：CRSWSN。主要從簇的形成和簇頭的產生兩個方面進行研究，并結合粗糙集的相關理論給出了詳細的設計方案，成功地解決傳統分簇算法的弊端。最后預測了粗糙集理論在無線傳感器網路中的發展趨勢。
關鍵詞：粗糙集; 上近似集; 下近似集; 無線傳感器網路; 簇; 簇頭; 模糊集
中圖分類號：TP301.6 文獻標志碼：A
文章編號：10013695(2009)01012103
New clustering algorithm based on rough sets for
wireless sensor networks
LUO Jun， XUE Shengjun， ZHAO Juanjuan， TAN Ran
(College of Computer Science Technology， Wuhan University of Technology， Wuhan 430063， China)
Abstract:This paper presented a new clustering algorithm， called CRSWSN for short. It based on the advantages of solving uncertain problems with the theory of rough sets. And it was also the first time to combine with wireless sensor network. The paper analyzed the specific design methods in the way of the forming of cluster and the cluster head. Finally proposed the future of rough sets in the wireless sensor networks.
Key words：rough sets; upper approximation; lower approximation; wireless sensor networks; cluster; cluster head; vague set
0 引言
自20世紀80年代初波蘭數學家Z.Pawlak針對G.Frege的邊界線區域思想提出粗糙集(rough sets)的概念[1]以來，利用粗糙和模糊的思維方式處理不明確問題的方法引起了全世界包括數學領域、計算機領域和控制工程領域等眾多學科領域科學家的濃厚興趣和廣泛關注。粗糙集理論作為一門獨立的學科，在很短的時間里取得了快速發展，并不斷被完善。隨著對粗糙集理論的不斷探索和研究的逐步深入，粗糙集理論作為一種新興的數據處理工具，被廣泛應用于計算機領域的機器學習、模式識別、專家系統、數據挖掘和圖像處理等；經濟商業領域的市場分析、股票數據分析和銀行數據分析等；工程技術領域的故障診斷、控制策略等；生物醫學領域的醫療診斷、DNA數據分析、全球氣候分析、決策支持和預測建模等[2]。但是，由于無線傳感器網絡(wireless sensor networks， WSN)自身的復雜性及其研究的局限性，粗糙集理論還沒有具體應用到WSN領域。盡管文獻[3]中將粗糙集理論應用于WSN中智能信息處理，但這只是在WSN環境下的知識獲取和數據挖掘，WSN的構建過程和路由協議的制定等核心技術都沒有涉及到粗糙集理論，因而粗糙集理論的優勢也沒有得到充分的體現。無線傳感器網絡中存在的一系列不精確、不確定的數據問題，迫切需要將粗糙集理論應用于WSN領域。本文利用粗糙集理論，結合WSN的特點提出了一種新的分簇算法。
1 相關基本概念
1.1 粗糙集理論
一般地，一個信息表知識表達系統S可以表示為S=(U，R，V，f)。這里U是樣本的集合，也稱為論域；R=C∪D是屬性集合，子集C和D分別稱為條件屬性和決策屬性；V=∪r∈RVr是屬性值的集合，Vr則表示r∈R的屬性值范圍；f：U×R→V是一個信息函數，它指定U中每一個樣本x的屬性值[4~6]。
定義1 對于每個屬性子集BR，定義一個不可分辨關系IND(B)={（x，y）}｜(x，y)∈U2，b∈B(b(x)=b(y))}或INB(B)=∩b∈BINB({b})。
不可分辨關系是粗糙集理論的一個關鍵概念，它通常是與一個屬性集合聯系在一起的。
定義2 一個決策表是一個信息表知識表達系統S=(U，R，V，f)。其中，R=C∪D是屬性集合，子集C和D分別成為條件屬性和決策屬性，D≠。
定義3 令XU并且X能用屬性子集Y確切地描述屬性子集(即是屬性子集Y所確定的U上的不分明集的并)時，稱X是Y可定義的，否則稱X是Y不可定義的。Y可定義集又稱做精確集，Y不可定義集又稱做Y非精確集或Y粗糙集。
一個樣本子集根據一個條件屬性子集所確定的不可分辨關系，有可能能夠準確地判定一些樣本是否屬于該樣本子集，也可能不能夠判定某些樣本是否屬于該樣本子集。為了描述這個問題，粗糙集理論采用了上近似集、下近似集的概念。
定義4 給定知識表達系統S=(U，R，V，f)，對于每個子集XU和不可分辨關系B，X的上近似集和下近似集分別可定義由B的基本集定義如下:
B*(X)=∪{Yi∈U｜IND(B)∧YiX}
B*(X)=∪{Yi∈U｜IND(B)∧Yi∩X≠}
定義5 集合BNB(X)=B*(X)-B*(X)稱為X的B邊界；POSB(X)=B*(X)稱為X的B正域;NEGB(X)=U-B*(X)稱為X的B負域。
B*(X)是根據知識B(屬性子集B)，U中所有一定能歸入集合X的元素構成的集合，即所有包含于X集合的并；B*(X)是根據知識B、U中所有一定能及可能歸入集合X的元素構成的集合，即所有與X的交不為空集的并。BNB(X)是根據知識B、U中既不能肯定歸入X又不能肯定歸入集合U-X的元素構成的集合；正域POSB(X)是根據知識B，U中所有能確定一定歸入集合X的元素的集合；負域NEGB(X)是根據知識B、U中所有不能確定一定歸入集合X的元素的集合；邊界域BNB(X)是某種意義上論域的不確定域，邊界域中的元素既不能肯定地屬于集合X，也不能肯定地屬于U-X。圖1表示了粗糙集理論中各個概念之間的關系。
定義6 假設集合X是論域U上的一個關于知識B的粗糙集，定義B精度(簡稱精度)為dB(X)=｜B*(x)｜/｜B*(X)｜。其中:｜X｜表示X中元素的個數。顯然，精度值是介于[0，1]上的實數。
粗糙集理論僅利用數據本身提供的信息，不需要先驗知識。粗糙集是一個強大的數據分析工具，它能表達和處理不完備信息，在保證關鍵信息的前提下對數據進行化簡并求得知識的最小表達式；它還能識別并評估數據之間的依賴關系，揭示出概念簡單的模式并獲取規則知識等[7]。
1.2 無線傳感器網絡
無線傳感器網絡是由一組傳感器以Ad hoc方式構成的無線網絡，其目的是協作地感知、采集和處理網路覆蓋的地理區域中感知對象的信息，并發布給觀察者[8，9]。在無線傳感器網絡體系結構中，網絡層的路由技術對無線傳感器網絡的性能好壞有著重要影響。隨著國內外傳感器網絡的研究發展，許多路由協議被提了出來，從網絡拓撲結構的角度，可以大體把它們分為平面路由協議和分簇路由協議[10]。
在平面路由協議中，所有網絡節點的地位是平等的，不存在等級和層次差異，它們通過相互之間的局部操作和信息反饋來生成路由。在這類協議中，匯聚節點(sink)向監測區域的節點(sensor)發出查詢命令，監測區域內的節點收到查詢命令后向目的節點發送監測數據。平面路由的優點是簡單、易擴展，無須進行任何結構維護工作，所有網絡節點的地位平等，具有較好的健壯性。典型的平面路由算法有DD(directed diffusion)、SAR(sequential assignment routing)、SPIN(sensor protocols for information via negotiation)、Romor routing等。平面路由的最大缺點在于網絡中無管理節點，缺乏對通信資源的優化管理，自組織協同工作算法復雜，對網絡動態變化的反應速度較慢等。
在分簇路由協議中，網絡通常被劃分為簇(cluster)。所謂簇，就是具有某種關聯的網絡節點集合。每個簇由一個簇頭(cluster head)和多個簇內成員(cluster member)組成，低一級網絡的簇頭是高一級網絡中的簇內成員，由最高層的簇頭與匯聚節點通信，如圖2所示。這類算法將整個網絡劃分為相連的區域[10，11]。
LEACH(low energy adaptive clustering hierarchy)是最早提出的分簇路由協議[10，11]，它的成簇思想貫穿于它之后提出的大部分分簇路由協議中，具體包括三個階段，即簇的形成、簇頭的產生和簇的路由[12]。下面主要討論粗糙集理論在前兩個階段的具體應用，并提出一種新的分簇算法——CRSWSN(clustering based on rough sets for wireless sensor networks)。
2 CRSWSN的具體思想
不管是LEACH算法、GAF(geographical adaptive fidelity)算法、TopDis(topology discovery)算法以及它們的改進算法，都只考慮了每個節點所具有的能量和所處的地理位置等信息，并且都假定所獲取的信息是精確的，并沒有考慮到WSN是一個動態性的網絡，并隨之帶來的一系列的不確定性因素：由于環境因素或電能耗盡可能造成的傳感器節點出現故障或失效；環境條件變化可能造成的無線通信鏈路帶寬變化，甚至時斷時通；傳感器網絡的傳感器、感知對象和觀察者這三要素都可能具有移動性和變化性；新加入的節點信息的不確定性等。這些不確定因素都會對簇的形成以及簇頭的形成產生影響，不同的因素可能會導致截然不同的分簇結果。而粗糙集理論中的上近似集和下近似集等相關知識正好可以解決這些不確定因素所導致的問題。
在對WSN中的節點進行簇的劃分時，有必要考慮各個節點的總能量、剩余能量、地理位置、信號感知能力、可擴展性、穩定性、通信代價和信號強度等信息。為了更好地說明和理解CRSWSN分簇算法，舉例進行模擬和說明。
本文給出六個節點，各個節點的信息(決策表)如表1所示。
表1 決策表
節點編號總能量剩余能量地理位置信號強度
有了上述決策表后，再根據具體的需求確定應該重點考慮的屬性。在此例中，選擇剩余能量和地理位置兩項作為劃分簇的重要指標，標記屬性子集A={剩余能量，地理位置}。有了屬性子集A，就可以對節點進行劃分，劃分的結果為{{1，2}，{3}，{4}，{5，6}}。將地理位置比較近的節點放在同一個簇，將能量高的節點盡量不要放在同一個簇是劃分簇的一個重要參考指標。根據上述討論，如果能將B={1，3，5，6}劃分為一個簇是比較理想的。顯然B是A的一個粗糙集，且POSA(B)=A*(B)={3，5，6}，A*(B)={1，2，3，5，6}，BNA(B)={1，2}，dA(B)=3/5=0.6。
可以發現，如果將A*(B)作為簇中的一部分成員，當dA(B)值比較大(即dA(B)>0.5)并且所考慮的屬性的重要性很高時，再從BNA(B)中任意取出一個節點(這里取了節點1)后構成一個新的簇，這樣就可以實現預期的目標，將節點1、3、5、6劃分到一個簇，記為簇1。對于剩下節點2、4，由于C={4}是精確集，即A*(C)=A*(C)={4}，毫無疑問應該單獨劃分為一個簇，記為簇2。至于節點2，它是BNA(B)中的一個成員，既可以劃分到簇1，也可以單獨劃分為一個簇，以便于以后的集成和擴充。
可以把簇的形成過程歸納為以下幾個步驟，直至所有的節點都加入到簇中：
a）將還沒有劃分到簇中的節點按照屬性集A進行劃分；
b）從剩余的節點中挑選出那些最可能組成一個合理的、符合需求的簇的節點，假設這些節點的集合記為S1；
c）求出A*(S1)、A*(S1)、BNA(S1)和dA(S1)；
d）求出A中所有屬性的重要性；
e）將A* (S1)中的元素劃分成一個簇，并根據步驟d）中計算出的屬性重要性以及精確度，考慮是否將BNA(S1)中部分或全部因素加入到簇中；
f）從節點集中刪除新加入簇中的節點，得到的節點集中如果為空集，則退出；否則繼續執行a)。
除此之外，如何選擇簇頭是一個關鍵，因為簇頭需要協調簇內節點的工作，負責時間的融合和轉發，能量消耗相對其他簇成員較大。目前簇頭的選擇算法一般基于以下一些準則：a)簇頭的剩余能量；b)簇頭到基站的距離；c)簇頭的位置分布，包括簇頭的連接度和覆蓋度；d)節點的密集度；e)簇內通信代價等。而這五條準則中都存在著很多不確定和模糊的因素，如簇頭的剩余能量雖然可以具體計算出來，但是由于WSN中節點的安置都具有很大的隨機性，剩余能量多并不代表該節點使用的時間越長，節點附近的環境也是決定其壽命的重要參考條件；簇頭到基站的距離更是模糊不定的，垂直距離和水平距離難以具體衡量，并且實際網絡中節點之間距離的鄰近并不代表節點之間可以直接通信；至于簇內通信代價，也只能從能量的損耗等少數幾個因素進行考慮，這些都使得簇頭的形成具有很大的不確定性。粗糙集理論可以對所有存在這些不確定因素的節點進行劃分，然后根據需要重點考慮的屬性將節點分別歸入到上近似集和下近似集中，再通過綜合比較找出合適的簇頭。
CEFL(clusterhead election using fuzzy logic)采用Mamdani模糊邏輯方法選擇簇頭。CEFL的輸入變量是節點能量、節點密集度和節點向心性。節點密集度是指節點所在位置周圍節點的密度；節點向心性是指節點靠近簇的中心程度，用該節點到簇內其他節點的距離平方和來度量。節點能量和節點密集度被安排成三種等級的隸屬度:高(high)、中(medium)、低(low)。節點向心性也被安排成三種等級的隸屬度：近(close)、中間(adequate)、遠(far)；模糊輸出集合包括七種結果:very small、small、rather small、medium、rather large、large、very large，表示節點當選簇頭的可能性。CEFL采用重心法(center of gravity)進行解模糊判決，從模糊輸出隸屬函數中找出一個最能代表模糊集合的精確量。該算法適合中等規模網絡。實驗結果表明，該簇頭選擇算法比LEACH更能延長網絡生命周期[12，13]。
3 結束語
針對WSN分簇路由，近年來不少研究人員都取得了卓越的成就。僅簇的形成算法就包括ACMWN(adaptive clustering for mobile wireless networks)[14]、PEGASIS (powerefficient gathering in sensor information systems)[15]、ACE (algorithm for cluster establishment)[16]、HYENAS(hybrid energyaware sensor networks)[17]和EECS(energy efficient clustering scheme)[18]等算法；簇頭的產生算法包括上文提到的LEACH算法以及它的改進算法DAEA(data aggregationexact and approximate)[19]和HEED(hybrid energyefficient distributed clustering)[20]等算法。這些算法為研究WSN分簇路由協議作出了巨大的貢獻，也使得分簇路由協議得到了不斷的完善與提高。但是，如果這些算法進一步考慮WSN中的不確定性和模糊性因素，結合本文提出的分簇算法CRSWSN，將粗糙集理論應用到分簇算法的三個階段，可以大大提高通信質量，減少網絡通信中能量的使用，延長傳感器節點的使用壽命。對于動態WSN，還可以結合神經網絡學科，使WSN網絡學會自動生成簇和簇頭。除此之外，CEFL算法還利用了Mamdani模糊邏輯方法生成簇頭。在未來的幾年里，將粗糙集理論、模糊集理論和神經網絡等多門學科與無線傳感器網絡結合起來共同研究是一個新的發展趨勢。
參考文獻：
［1］PAWLAK Z. Rough setstheoretical aspects of reasoning about data[M]. Norwell: Kluwer Academic Publisher， 1991.
[2]石紅，沈毅，劉志言，等.關于粗糙集理論及應用問題的研究[J]. 計算機工程，2003， 29(3):13.
[3]戴志鋒，李元香，余琍，等.粗糙集在無線傳感器網絡中的智能信息處理研究[J].計算機應用研究，2007，24(10):7578.
[4]王國胤.Rough集理論與知識獲取[M].西安:西安交通大學出版社，2001.
[5]張文修，吳偉志，梁吉業，等.粗糙集理論與方法[M].北京：科學出版社，2001.
[6]王玨.粗糙集理論及其應用[D].西安:西安電子科技大學，2007.
[7]PAWLAK Z. Vagueness and uncertainty：a rough set perspective[J]. Computational Intelligence， 1995，11(12):227232.
[8]TILAK S， HEINZELMAN W. A taxonomy of wireless microsensor network models[J]. Mobile Computing and Communications Review， 2002，1(2):18.
[9]任豐原，黃海寧，林闖.無線傳感器網絡[J].軟件學報，2003，14(7):12821291.
[10]王帥.分簇的無線傳感器網路中瓶頸節點問題研究[D].濟南:山東大學，2007.
[11]孫利民，李建中，陳渝，等.無線傳感器網路[M].北京:清華大學出版社，2005.
[12]沈波，張世永，鐘亦平.無線傳感器網絡分簇路由協議[J].軟件學報，2006，17(7):15881600.
[13]GUPTA I， RIORDAN D， SAMPALLI S. Clusterhead election using fuzzy logic for wireless sensor networks[C]//Proc of the 3rd Annual Communication Networks and Services Research Conference. Washington DC: IEEE Computer Society， 2005:255260.
[14]LIN C R， GERLA M. Adaptive clustering for mobile wireless networks[J]. IEEE Journal on Selected Areas in Communications， 1997，15(7):12651275.
[15]LINDSEY S， RAGHAVENDRA C S. PEGASIS: powerefficient gathering in sensor information systems[C]//Proc ofIEEE Aerospace Conference. San Francisco: IEEE Computer Society， 2002:11251130.
[16]CHAN Haowen， PERRIG A. ACE: an emergent algorithm for highly uniform cluster formation[C]//Proc of the 1st European Workshop on Wireless Sensor Networks. Berlin:Springer， 2004:154171.
[17]TILLAPART P， THUMTHAWATWORO T， PAKDEEPINIT P， et al. Method for cluster heads selection in wireless sensor networks[C]//Proc of IEEE Aerospace Conference. San Francisco: IEEE Press， 2004:36153623.
[18]YE Mao， LI Changfa， CHEN Guihai， et al. EECS: an energy efficient clustering scheme in wireless sensor networks[C]//Proc of the 24th IEEE Int’l Performance Computing and Communications Conference. New York: IEEE Press， 2005:535540.
[19]ALKARAKI J N， ULMUSTAFA R， KAMAL A E. Data aggregation in wireless sensor networksexact and approximate algorithms[C]//Proc of IEEE Workshop on High Performance Switching and Routing. New York:IEEE Press， 2004:241245.
[20]YOUNIS O， FAHMY S. A hybrid， energyefficient， distributed clustering approach for Ad hoc sensor networks[J]. IEEE Trans on Mobile Computing， 2004，3(4):660669.
