一種新的無線傳感器網(wǎng)絡拓撲發(fā)現(xiàn)算法

(解放軍理工大學 指揮自動化學院 計算機系南京 210007)

摘 要：GBGD是一種面向攻擊的隱蔽性較強的拓撲發(fā)現(xiàn)算法，通過分析發(fā)現(xiàn)，該算法對實際網(wǎng)絡進行了過于理想化的假設，導致無法在實際中應用。在GBGD算法工作模式的基礎上，對實際網(wǎng)絡提出了合理假設，設計實現(xiàn)了一種新的網(wǎng)絡拓撲發(fā)現(xiàn)算法，通過對報文向基站匯聚過程中每一跳轉(zhuǎn)發(fā)時延進行分析得出節(jié)點在路由樹中的層次關系，進而推算出網(wǎng)絡的拓撲。仿真實驗結(jié)果表明，該算法能準確推斷出網(wǎng)絡的拓撲，并在報文存在丟失較多的情況下具有較好的魯棒性。由Mica2節(jié)點組成的原型系統(tǒng)實驗結(jié)果表明，該算法能夠較好地應用于實際網(wǎng)絡。

關鍵詞：無線傳感器網(wǎng)絡；拓撲發(fā)現(xiàn);基站;GBGD

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2009)05-1868-03

Topology discovery algorithm for wireless sensor networks

SHEN Jun，QI Wangdong

(Dept. of Computer Institute of Command Automation PLA University of Science Technology Nanjing 210007 China)

Abstract:GBGD is an attack oriented topology discovery algorithm with high confidentiality. However，found that this algorithm could not be applied in actual network due to its unrealistic assumptions of real situations.This paper proposed reasonable assumptions of actual network based on the work pattern of GBGD furthermore，designed and implemented a new topology discovery algorithm. By analyzing the forwarding delay of every hop during message convergence process from nodes to base station，it could get the levels of the nodes in the topology tree from which could finally deduce the topology of the surveillance network. Analysis and simulations show that this algorithm can get the topology of the network exactly even when many messages lost during transmission.

Key words:WSNs(wireless sensor network); topology discovery; base station; GBGD

0 引言

無線傳感器網(wǎng)絡(WSNs)是由大量隨機分布的，集計算、通信、傳感器技術三為一體的廉價微型節(jié)點組成的分布式系統(tǒng)。它集合了傳感器技術、嵌入式計算、分布式信息處理技術和無線通信技術，能夠協(xié)作地實時感知環(huán)境信息。

無線傳感器網(wǎng)絡節(jié)點廉價、微型的特點使其在軍事偵察領域中有著重要的應用前景，已經(jīng)出現(xiàn)的應用系統(tǒng)如狙擊手定位系統(tǒng)、VigilNet無線傳感器偵察網(wǎng)絡系統(tǒng)、A Line in the Sand 無線傳感器偵察網(wǎng)絡等。如何發(fā)現(xiàn)并對敵方布設的偵察網(wǎng)絡進行攻擊在現(xiàn)實中具有重大的意義。目前針對無線傳感器網(wǎng)絡的攻擊方法有很多種 如虛假路由攻擊、匯聚節(jié)點攻擊、蟲洞攻擊等。不管是何種攻擊方式，攻擊對象與攻擊的效果是密切相關的。對基站及數(shù)據(jù)轉(zhuǎn)發(fā)的中間節(jié)點的攻擊顯然比對目標網(wǎng)絡邊緣節(jié)點的攻擊更加有效。

本文以發(fā)現(xiàn)敵方傳感器網(wǎng)絡的拓撲為目的，在目標網(wǎng)絡布設區(qū)域布置多個監(jiān)聽節(jié)點形成監(jiān)聽網(wǎng)絡對目標網(wǎng)絡的通信過程進行監(jiān)聽 通過對報文向基站發(fā)送過程中轉(zhuǎn)發(fā)時的時延來完成對目標網(wǎng)絡拓撲的分析。

1 無線傳感器網(wǎng)絡的拓撲發(fā)現(xiàn)算法

根據(jù)面向的應用不同，無線傳感器網(wǎng)絡的拓撲發(fā)現(xiàn)算法可分為以下兩種：

a）面向網(wǎng)絡管理的拓撲發(fā)現(xiàn)算法^[1~3]。它在于發(fā)現(xiàn)網(wǎng)絡中節(jié)點的活動性、節(jié)點間的鏈路狀態(tài)、節(jié)點的剩余能量等信息，進而為最大限度地延長整個網(wǎng)絡系統(tǒng)的壽命提供條件。

b）面向攻擊的拓撲發(fā)現(xiàn)算法^[4，5]。利用無線傳感器網(wǎng)絡應用中數(shù)據(jù)整體上向基站匯總的趨勢特征為基礎，采用被動監(jiān)聽目標網(wǎng)絡通信報文的方式來分析目標網(wǎng)絡的拓撲。

Traffic analysis^[4]中，攻擊者通過監(jiān)聽通信流量和數(shù)據(jù)轉(zhuǎn)發(fā)路徑來推斷出目標網(wǎng)絡的拓撲信息。越接近基站，需要轉(zhuǎn)發(fā)的報文越多，因此網(wǎng)絡的通信流量越大，如圖1所示。攻擊者根據(jù)報文多跳地向基站匯聚的特點，沿著數(shù)據(jù)匯聚的方向追蹤基站的位置，但由于無線傳感器網(wǎng)絡往往數(shù)量較大，從數(shù)據(jù)的源節(jié)點到基站的過程中轉(zhuǎn)發(fā)的次數(shù)較多，采用移動追蹤報文的轉(zhuǎn)發(fā)路徑是不切實際的；另一方面，一個攻擊者只能獲得網(wǎng)絡的局部信息，僅僅依靠這些信息來推斷網(wǎng)絡的拓撲是不夠的。文獻[5]中提出的GBGD算法通過布設大量監(jiān)聽節(jié)點協(xié)作地對目標網(wǎng)絡進行監(jiān)聽，如圖2所示。在目標網(wǎng)絡的覆蓋區(qū)域內(nèi)布設一定數(shù)量的監(jiān)聽節(jié)點組成監(jiān)聽網(wǎng)絡。通過較多的監(jiān)聽節(jié)點被動地監(jiān)聽目標區(qū)域的通信情況，依據(jù)路由建立過程中路由建立報文轉(zhuǎn)發(fā)及數(shù)據(jù)匯報過程中報文沿路由樹向基站匯聚的特點，集中地對目標網(wǎng)絡進行分析。這種方式能夠較大范圍地對目標網(wǎng)絡的通信情況進行監(jiān)聽，因而能更好地對目標網(wǎng)絡的拓撲進行刻畫。

GBGD算法無法直接應用于實際中，因為GBGD算法的前提假設無法在實際中成立。這些假設主要有：

a）通信報文中攜帶有發(fā)送節(jié)點的地址。對無線網(wǎng)絡擴散樹路由協(xié)議及數(shù)據(jù)匯報過程進行分析發(fā)現(xiàn)，這兩種通信過程中的消息報頭中并不攜帶發(fā)送節(jié)點地址。

b）通信信道沒有錯誤發(fā)生，即所有的監(jiān)聽記錄報文均能可靠地進行傳送。在無線傳感器網(wǎng)絡開放無線通信環(huán)境下，發(fā)生報文錯誤與報文丟失是很常見的。因此GBGD算法中依賴于能監(jiān)聽到目標網(wǎng)絡的所有通信報文的假設無法成立。

c）監(jiān)聽節(jié)點能夠接收到監(jiān)聽范圍內(nèi)目標網(wǎng)絡節(jié)點的所有通信報文。

本文提出一種新的基于報文發(fā)送時間分析的網(wǎng)絡拓撲發(fā)現(xiàn)算法，該算法利用報文向基站轉(zhuǎn)發(fā)的時間先后關系推斷報文到達基站的路徑。由于不依賴于GBGD算法的假設，它能應用于現(xiàn)實環(huán)境中。

2 拓撲發(fā)現(xiàn)算法描述

2.1 無線傳感器網(wǎng)絡報文發(fā)送模式

無線傳感器網(wǎng)絡工作時報文的傳遞模式主要有兩種：

a）洪泛(flooding)的報文傳遞模式。在這種模式中，基站向其鄰居節(jié)點廣播某個報文；收到這個報文的節(jié)點將報文以同樣的方式廣播出去，一直到網(wǎng)絡中所有的節(jié)點都收到這個報文為止。這種模式廣泛運用于無線傳感器網(wǎng)絡的眾多協(xié)議過程中，如路由建立、時間同步過程采取的就是這種模式。

b)節(jié)點到基站之間的報文傳遞，即通過路由樹多跳地將報文發(fā)送到目的地。節(jié)點采樣數(shù)據(jù)之后向基站匯報的過程多采用這種模式，在文中簡稱為數(shù)據(jù)轉(zhuǎn)發(fā)模式。

在實際應用中，報文并不直接攜帶發(fā)送節(jié)點的地址，且洪泛過程采用廣播發(fā)送方式發(fā)送報文，因此無法直接利用洪泛過程來對目標網(wǎng)絡的拓撲作出判斷。但是在轉(zhuǎn)發(fā)模式中的報頭中攜帶有目的地址信息，因此可利用目的地址及報文轉(zhuǎn)發(fā)的時間先后關系推斷出目標網(wǎng)絡節(jié)點在數(shù)據(jù)報文向基站轉(zhuǎn)發(fā)過程的傳輸路徑上的先后關系。在此作幾個假設：

假設1 監(jiān)聽節(jié)點能夠解讀報頭信息，進而獲得報文的類型及報文的目的地址。只要目標網(wǎng)絡采用的不是鏈路層的加密方式，就能獲得目標網(wǎng)絡報文的報頭信息，進而獲得報文的目的地址。

假設2 報文在向基站匯報的過程中，中間節(jié)點不改變報文的內(nèi)容，由此監(jiān)聽節(jié)點可以惟一地區(qū)別一個報文。

假設3 監(jiān)聽節(jié)點的監(jiān)聽半徑是以節(jié)點為中心的半徑R的圓形。

2.2 相關定義

在介紹具體的拓撲發(fā)現(xiàn)算法之前作如下定義：

定義1 如果節(jié)點A是節(jié)點B在數(shù)據(jù)向基站轉(zhuǎn)發(fā)路徑中的下一跳節(jié)點，則稱節(jié)點A是節(jié)點B的父親節(jié)點，節(jié)點B是節(jié)點A的子節(jié)點。

定義2 對于報文向基站轉(zhuǎn)發(fā)路徑中的相鄰兩個節(jié)點A和B，若A為B的父節(jié)點，記節(jié)點B發(fā)出的報文為M1，節(jié)點A收到M1后轉(zhuǎn)發(fā)的報文為M2，稱M2為M1的后繼報文。對于M1和M2，假設數(shù)據(jù)報文在轉(zhuǎn)發(fā)過程中內(nèi)容不變，因此M1和M2具有相同的報文類型、長度及內(nèi)容，只是報文的目的地址不相同；同時M1被監(jiān)聽到的時間在M2被監(jiān)聽到的時間之后的一定范圍內(nèi)。

2.3 算法描述

在報文由源節(jié)點向基站匯報的過程中，如果節(jié)點A接收到來自于其子節(jié)點B的報文并立即轉(zhuǎn)發(fā)出去，則可以觀察到節(jié)點B和節(jié)點A發(fā)送報文的時間間隔，并由此推斷出這兩個節(jié)點在路由樹中的父子關系。算法的基本思想正是通過獲得報文的目的地址及報文發(fā)送的時間推算報文在向基站發(fā)送過程中所經(jīng)過的路徑；最后依據(jù)基站一定是該報文轉(zhuǎn)發(fā)的終點且越靠近基站的監(jiān)聽節(jié)點所監(jiān)聽到的通信流量越大的事實推斷出基站的位置。詳細算法流程如圖3所示。

3 算法性能分析

算法是以目標網(wǎng)絡的通信記錄為輸入完成對目標網(wǎng)絡拓撲的分析，本文在Mica2平臺上實現(xiàn)了算法，并用TinyOS自帶的仿真工具TOSSIM對算法的性能進行仿真。理想的情況下，如果監(jiān)聽節(jié)點能獲得其監(jiān)聽范圍內(nèi)所有的報文，則根據(jù)報文的先后關系就可恢復出多條完整的路徑。但是在實際網(wǎng)絡中，存在報文丟失、同一個報文被多個監(jiān)聽節(jié)點監(jiān)聽到等情況的出現(xiàn)，則可能推測出錯誤的路徑。因此，設定一個評價指標，稱為正確路徑百分比：

Pc=正確判斷的路徑跳數(shù)/目標網(wǎng)絡的實際跳數(shù)

構(gòu)造一個有40個節(jié)點的目標網(wǎng)絡，節(jié)點的通信半徑為10 m。如圖4所示，網(wǎng)絡中基站在(0，0)處，有三個數(shù)據(jù)源(菱形表示)，網(wǎng)絡采用擴散樹路由協(xié)議形成的拓撲用點線表示；圓形為監(jiān)聽節(jié)點所在位置，監(jiān)聽節(jié)點的監(jiān)聽半徑為目標節(jié)點通信半徑的兩倍。

3.1 與GBGD算法的比較

圖5為本文算法與GBGD算法在不同的報文丟失率情況下能正確判斷率的對比圖。從圖5中可以看出，在相同的報文丟失率下，本文算法的正確判斷率略低于GBGD算法，這是由于GBGD算法假設報文中能獲得源地址與目的地址，只要能監(jiān)聽到某個報文，則能肯定地判斷出該報文的發(fā)送者與接收者；而本文算法是假設在只能獲得目的地址的情況下，通過連續(xù)轉(zhuǎn)發(fā)的時延來判斷兩個節(jié)點間的父子關系，因此需要監(jiān)聽到報文的連續(xù)兩次轉(zhuǎn)發(fā)才能作出正確的判斷。故在同等的報文丟失情況下，本文算法性能略低于GBGD。但是在實際的網(wǎng)絡中，通過觀察知道報文一般不會同時帶有目的地址及源地址，因此GBGD算法無法應用于真實的網(wǎng)絡中。

3.2 報文丟失率對算法性能的影響

在實際情況中，監(jiān)聽網(wǎng)絡能完全監(jiān)聽到目標網(wǎng)絡的報文通信的可能性很小。如果報文丟失，則可能導致算法得出錯誤的結(jié)果；但是如果監(jiān)聽節(jié)點能多次地監(jiān)聽到數(shù)據(jù)從源節(jié)點經(jīng)過同一條路徑向基站發(fā)送的過程，則可以通過數(shù)據(jù)的冗余性獲得正確的結(jié)果。筆者考察了在不同報文從源節(jié)點到基站發(fā)送的輪數(shù)的情況下，報文丟失率對Pc影響，如圖6所示。

從圖6中可以看出，隨著監(jiān)聽網(wǎng)絡對目標網(wǎng)絡數(shù)據(jù)轉(zhuǎn)發(fā)報文經(jīng)過同一條路徑向基站轉(zhuǎn)發(fā)次數(shù)的增多，算法能正確推測出目標網(wǎng)絡節(jié)點路徑跳數(shù)的百分比越高。另一方面，考察不同丟失率下要達到對目標網(wǎng)絡轉(zhuǎn)發(fā)路徑的正確率達到80%以上所需的對報文沿同一條路徑轉(zhuǎn)發(fā)的次數(shù)。如圖7所示，在報文丟失率達到60%時，算法只需要監(jiān)聽到5次轉(zhuǎn)發(fā)過程便可以推算出提出報文轉(zhuǎn)發(fā)的路徑，這也從另一方面說明算法對實際情況的適應性較好。

3.3 監(jiān)聽節(jié)點覆蓋范圍對算法影響

監(jiān)聽網(wǎng)絡對目標網(wǎng)絡的監(jiān)聽覆蓋范圍與算法的性能有著密切的關系。覆蓋范圍越高則監(jiān)聽網(wǎng)絡所能獲得的目標網(wǎng)絡通信信息越豐富，算法獲得的目標網(wǎng)絡拓撲越細致。而覆蓋范圍與監(jiān)聽節(jié)點數(shù)目、節(jié)點監(jiān)聽半徑及節(jié)點的分布情況有關。由于傳感器網(wǎng)絡大都采用隨機拋散的方式布設，即使是同等數(shù)目的節(jié)點也會形成不同的覆蓋范圍。筆者對于特定的監(jiān)聽節(jié)點數(shù)及監(jiān)聽半徑隨機地選取幾種拓撲，考察它們的影響。圖8為隨機隨取的幾種拓撲所得結(jié)果的平均值。

圖8為算法在不同的監(jiān)聽節(jié)點數(shù)和不同的監(jiān)聽半徑下所正確判斷數(shù)據(jù)轉(zhuǎn)發(fā)過程的正確率。其中，a為監(jiān)聽節(jié)點與目標節(jié)點之比。從圖8中可以看出，在監(jiān)聽節(jié)點數(shù)目一定的情況下監(jiān)聽半徑越大判斷正確率越高；而在監(jiān)聽半徑一定時，監(jiān)聽節(jié)點越多，正確率越高。

4 結(jié)束語

本文以發(fā)現(xiàn)目標網(wǎng)絡拓撲為目的，采用多個監(jiān)聽節(jié)點組成網(wǎng)絡對目標網(wǎng)絡的通信行為進行監(jiān)聽，利用數(shù)據(jù)向基站轉(zhuǎn)發(fā)過程中報文轉(zhuǎn)發(fā)的先后關系推測出目標網(wǎng)絡數(shù)據(jù)轉(zhuǎn)發(fā)過程中報文經(jīng)過的路徑，再進一步獲得目標網(wǎng)絡的關鍵節(jié)點甚至是基站的位置，算法在Mica2平臺上得以實現(xiàn)。經(jīng)實驗證明該算法能較好地運用于實際中。 

本文中仍假定能獲知報文的目的地址，如果目標網(wǎng)絡采用鏈路層加密則難以獲知報文的目的地址。在下一步的工作中，將考慮在無法獲得報文目的地址的情況下通過目標網(wǎng)絡通信流量來對目標網(wǎng)絡的拓撲進行分析。

參考文獻：

［1］GEORGEFF I.A distributed topology discovery algorithm for wireless sensor networks[D].Perth:University of Western Australia，2004.

[2]DEB B，BHATNAGAR S NATH B.A topology discovery algorithm for sensor networks with applications to network management[C]//Proc of IEEE CAS Workshop on Wireless Communications and Networking.2002.

[3]藏傳真，范玉順.面向監(jiān)控和管理的無線傳感器網(wǎng)絡拓撲發(fā)現(xiàn)算法[J].計算機應用研究 2006，23(4):230-233.

[4]DENG Jing，HAN R，MISHRA S.Decorrelating wireless sensor network traffic to inhibit traffic analysis attacks[J].Elsevier Pervasive and Mobile Computing Journal:Special Issue on Security in Wireless Mobile Computing Systems，2006，2(2):159186.

[5]李楠，宋金玉，季曉君.GBGD：一種隱蔽的拓撲發(fā)現(xiàn)算法[C]//中國計算機大會論文集.2007:264.