◆李 琛 楊 松 于永學 裴小東

（海軍裝備研究院 北京 100036）

改進節(jié)點度分簇路由協(xié)議研究

◆李 琛 楊 松 于永學 裴小東

（海軍裝備研究院 北京 100036）

在移動自組網(wǎng)節(jié)點規(guī)模較大的情況下，采用基于分簇結構的路由協(xié)議。最高節(jié)點度簇首算法，能夠減少自組網(wǎng)簇的數(shù)量，提高自組網(wǎng)組網(wǎng)效率，減少簇間路由開銷。本文在該協(xié)議的基礎上，對簇首的選擇進行改進，考慮自組網(wǎng)節(jié)點位置和移動狀態(tài)的變化導致簇首的頻繁變更的問題，對最高節(jié)點度算法進行改進，提高網(wǎng)絡拓撲的穩(wěn)定性，降低節(jié)點路由維護開銷。

移動自組網(wǎng)；分簇路由協(xié)議；節(jié)點度；簇首

0 引言

傳統(tǒng)的有線網(wǎng)絡中路由器固定，組網(wǎng)后網(wǎng)絡拓撲穩(wěn)定，路由信息可長時間不用更新。移動自組網(wǎng)是無固定基礎設施、無中心的自組織網(wǎng)絡，網(wǎng)內(nèi)節(jié)點在移動狀態(tài)下組網(wǎng)，組網(wǎng)具有靈活以及不受地理環(huán)境限制的優(yōu)勢，所有節(jié)點具備路由功能，節(jié)點可以隨時加入或離開自組網(wǎng)而不會導致網(wǎng)絡癱瘓，因此，移動自組網(wǎng)路由協(xié)議是保證組網(wǎng)穩(wěn)定高效的關鍵技術之一。針對移動自組網(wǎng)不同網(wǎng)絡規(guī)模和任務需求，已經(jīng)發(fā)展大量的路由協(xié)議技術，其中在大規(guī)模節(jié)點情況下，普遍采用技術成熟的分簇路由協(xié)議實現(xiàn)高效組網(wǎng)。本文研究改進節(jié)點度的分簇路由協(xié)議，在原有最高節(jié)點算法的基礎上對簇首變更提出改進方法，降低簇首變更頻率，節(jié)省網(wǎng)絡維護資源，提高網(wǎng)絡拓撲穩(wěn)定性。

1 分簇路由協(xié)議研究現(xiàn)狀

圖1 分簇結構示意圖

分簇路由協(xié)議區(qū)別于平面路由協(xié)議。在平面路由協(xié)議中，所有組網(wǎng)節(jié)點地位平等，節(jié)點在功率覆蓋范圍內(nèi)可以互聯(lián)互通，距離較遠則多跳傳輸。平面路由協(xié)議適合節(jié)點規(guī)模較小的自組網(wǎng)，路由信息更新快，路由建鏈維護方便，但是節(jié)點數(shù)目增多會導致路由開銷大，造成網(wǎng)絡資源浪費。分簇路由協(xié)議基于分簇結構的自組網(wǎng)，簇的劃分主要根據(jù)網(wǎng)絡中結構功能類似的節(jié)點進行劃分，簇內(nèi)包含一個簇首和若干簇成員，組網(wǎng)示意如圖1所示。簇首一般根據(jù)最小ID、最高節(jié)點度、最低移動性、節(jié)點位置等條件進行選舉，主要控制并管理簇內(nèi)成員，協(xié)調簇成員報文傳遞，對簇內(nèi)信息收集以及數(shù)據(jù)處理，將信息數(shù)據(jù)共享給其他簇首。分簇路由協(xié)議相比平面路由協(xié)議能夠有效控制洪泛廣播信息，簇成員功能相對簡單，不需要維護復雜的路由信息，在跨簇傳播時主要在簇首層級傳播，網(wǎng)絡規(guī)模不受限制，在大規(guī)模節(jié)點情況下能夠實現(xiàn)降低節(jié)點能耗和提高網(wǎng)絡通信質量的目的，但是簇首的維護比較復雜，在網(wǎng)絡拓撲變化時，簇首的變更也會占據(jù)網(wǎng)絡路由開銷，而且，路由通過簇首尋路，因此所尋路徑不一定是最優(yōu)路徑。

2 最高節(jié)點度分簇路由協(xié)議

在分簇路由協(xié)議中，一個節(jié)點與相連一跳距離的節(jié)點（鄰居節(jié)點）數(shù)量稱為節(jié)點度。最高節(jié)點度算法根據(jù)最大節(jié)點度對自組網(wǎng)進行劃分。采用該算法的路由協(xié)議，將擁有最高節(jié)點度的節(jié)點選舉為簇首，度數(shù)相同則隨機選擇節(jié)點作為簇首，簇首的鄰居節(jié)點作為簇成員，簇首和簇成員一起組成簇，自組網(wǎng)對所有節(jié)點進行上述過程，直至所有節(jié)點身份確定。具體算法描述如下：

假設區(qū)域內(nèi)存在N個節(jié)點，每個節(jié)點分配標識為1，2，3，…，N。任意節(jié)點通過廣播問詢的方式與其他節(jié)點交互信息，得到該問詢信號的節(jié)點會向廣播問詢的節(jié)點發(fā)送應答信號，這樣每個節(jié)點都會得到一個判決矩陣，公式如下：

式中，當?shù)趇節(jié)點與第j個節(jié)點不臨相鄰時，aij=0；當?shù)趇個節(jié)點與第j個節(jié)點相鄰時，aij=1；同時定義i=j的情況下，aij=1。

判決矩陣A包含了本節(jié)點同其他節(jié)點的位置關系信息，反映了網(wǎng)絡的拓撲結構。矩陣中主要由0和1兩個元素構成，當aij=0時，表示節(jié)點i和j不相鄰；當aij=1時，表示兩節(jié)點相鄰。在已經(jīng)獲得判決矩陣信息的情況下，可以計算每一個節(jié)點的節(jié)點度，再根據(jù)節(jié)點度對自組網(wǎng)進行分簇。

節(jié)點i的度數(shù)DN（i）計算公式如下：

式中i=1，2，3，…，N。

在計算最大節(jié)點度后，按照節(jié)點度數(shù)值高低的依次選舉為簇首，選舉簇首后，判決矩陣需對與簇首節(jié)點相連的鄰居節(jié)點剔除判決矩陣，再重新選舉其他簇首。計算形式如下：

定義，第k個節(jié)點的度數(shù)為DN（k），公式如下：

節(jié)點k為第1個簇首H1，將DN（k）記錄并保存到選舉度S（k）=DN（k）中。令k’ ∈V-Ntotal（i），i’ ∈V-Ntotal（i），繼續(xù)在剩余節(jié)點中選擇簇首，公式如下：

節(jié)點k’被選為第2個簇首H2，保存選舉度S（k’），用同樣的方法繼續(xù)選擇簇首，直到自組網(wǎng)分簇完畢。

按照最高節(jié)點度算法將自組網(wǎng)劃分為不同簇區(qū)域，能夠盡量減少自組網(wǎng)簇的數(shù)目。業(yè)務報文簇內(nèi)轉發(fā)概率增加，簇間轉發(fā)效率提高，從系統(tǒng)整體上有效降低傳輸時延。但是，基于最高節(jié)點度的分簇算法，簇首變更頻繁，引發(fā)大量維護開銷，造成網(wǎng)絡資源浪費。

3 改進節(jié)點度分簇路由協(xié)議

改進節(jié)點度分簇路由協(xié)議主要針對原協(xié)議簇首變更頻繁的問題，在設計時引入門閾值T，既降低簇首變更頻率，同時能夠在拓撲結構變化較大時及時變更簇首，提高系統(tǒng)效率。改進節(jié)點度分簇路由協(xié)議主要包括分簇的建立和維護兩部分內(nèi)容。

3.1 分簇建立

改進節(jié)點度分簇路由協(xié)議在組網(wǎng)之初，采用最大節(jié)點度算法的思路，盡可能減少組網(wǎng)簇首的數(shù)量，具體算法如下。

通過廣播問詢以及統(tǒng)計應答信息，建立判決矩陣A：

其中判決矩陣A中，當i=j時，aij=1。N為節(jié)點總數(shù)量，所有節(jié)點從1到N對應不同序號進行標識；aij表示第i個節(jié)點與第j個節(jié)點的位置關系，當aij=0時，表示節(jié)點i和j不相鄰；當aij=1時，表示兩節(jié)點相鄰。

根據(jù)判決矩陣計算節(jié)點度：

公式中ai代表第i個節(jié)點。計算所有節(jié)點度后，得到節(jié)點度矩陣DN，并根據(jù)節(jié)點度矩陣選取其中節(jié)點度最大的節(jié)點，作為簇首。

第一個簇首節(jié)點記為H1，節(jié)點度為：

對簇首選舉度S（H1）進行賦值并保存選舉度在本節(jié)點：

簇首決定后，該節(jié)點ai根據(jù)判決矩陣A中第i行中的值判斷與簇首相連節(jié)點的位置關系。aij=1代表與簇首相連的鄰居節(jié)點，這些作為簇成員不參與其他簇首選舉，簇與簇成員組成簇；aij=0表示其他節(jié)點不與簇首ai一跳相連，參與其他簇首選舉。簇確定后，需要根據(jù)判決矩陣從所有節(jié)點集合N中刪除簇和簇成員節(jié)點，該簇節(jié)點集合定義為J，表示為：

剩余節(jié)點集合定義為N’，表示如下：

第二個簇首節(jié)點記為H2，需要在剩余節(jié)點集合中選取簇首，節(jié)點度為：

對簇首選舉度S（H2）進行賦值并保存選舉度在簇首節(jié)點H2中：

簇首選舉之后，同樣根據(jù)判決矩陣完成簇成員身份確定，完成第二個簇的建立，并從N’中刪除簇首和簇成員集合，繼續(xù)進行簇首選舉，直至所有節(jié)點身份確定，完成組網(wǎng)過程。

3.2 路由維護

3.2.1 變更判決

組網(wǎng)完成之初，采用最大節(jié)點度算法的分簇網(wǎng)絡保證簇首節(jié)點數(shù)量盡可能小。但是，由于移動自組網(wǎng)的移動性和開放性，節(jié)點位置可能不斷變化，普通節(jié)點可能隨時加入自組網(wǎng)，網(wǎng)絡拓撲動態(tài)變化。原路由協(xié)議在網(wǎng)絡拓撲變化后，始終根據(jù)節(jié)點度進行分簇，在節(jié)點移動速度快的情況下，可能引起簇首不斷變更，雖然能夠保證網(wǎng)絡效率，卻導致系統(tǒng)大量的路由維護。

采用改進節(jié)點度路由協(xié)議維護路由過程中，當簇首ai節(jié)點度變化時，計算當前節(jié)點度DN（ai），并與簇首保存選舉度S做差運算，引入比較門閾值T，降低簇首變更驟然性，增加變更條件余量。

若簇首節(jié)點度滿足如下條件：

則不需要變更簇首，即便簇內(nèi)存在節(jié)點度大于簇首的簇成員，系統(tǒng)依然保持簇結構，保證網(wǎng)絡穩(wěn)定性，反之，則進入簇變更程序。

公式中，門閾值T的取值，根據(jù)自組網(wǎng)業(yè)務量多少和節(jié)點設備功率、傳輸能力等進行預先設置。在系統(tǒng)業(yè)務量繁重或者節(jié)點設備功率大、功能全面等情況下，可以將T的取值增大，減少簇首變更，維持自組網(wǎng)拓撲結構，反之，則減少T的取值，及時變更簇首，調整到系統(tǒng)最佳狀態(tài)，提高系統(tǒng)效率。

3.2.2 狀態(tài)變更

在改進節(jié)點度的路由協(xié)議中，節(jié)點狀態(tài)（c_state）包括4種狀態(tài)：簇首狀態(tài)（CH）、成員節(jié)點狀態(tài)（MEMBER）、網(wǎng)關狀態(tài)（GW）、簇首競爭狀態(tài)（CH_READY）。幾種狀態(tài)變更示意圖如圖2所示。

圖2 狀態(tài)轉換示意圖

（1）簇首狀態(tài)

簇首與鄰居節(jié)點以一跳距離相連，組成簇，簇與簇之間通過簇首相連。在其他節(jié)點加入該簇或者本簇節(jié)點離開該簇，簇首節(jié)點度變更超過閾值，進行變更，重新計算簇內(nèi)節(jié)點節(jié)點度，若原簇首仍適合作為簇首狀態(tài)，則不作改變，若連續(xù)3個周期存在簇首競爭狀態(tài)，則將簇首競爭狀態(tài)節(jié)點作為簇首，原簇首降為成員節(jié)點狀態(tài)，并在本簇范圍內(nèi)廣播發(fā)送強制變更消息。

（2）成員節(jié)點狀態(tài)

成員節(jié)點狀態(tài)是簇內(nèi)可以隨時作為其他狀態(tài)的節(jié)點。

在當前拓撲更新周期內(nèi)，若新增處于CH狀態(tài)的雙向鄰居、且該CH所在簇的容量未滿時，加入該CH所在的簇；若本節(jié)點的鄰居中CH數(shù)量＞1，則成為網(wǎng)關節(jié)點，轉入GW狀態(tài)。

節(jié)點加入某簇的情況下，在當前拓撲更新周期內(nèi)，若新增處于CH_READY狀態(tài)的雙向鄰居，當本節(jié)點更適合作為CH時，進入CH_READY狀態(tài)。

節(jié)點加入某簇的情況下，若在當前拓撲更新周期內(nèi)，只收到處于雙向MEMBER狀態(tài)的節(jié)點發(fā)來的鄰居通告，比較本節(jié)點及所有鄰居的節(jié)點度，若本節(jié)點更適合作為CH，轉入CH_READY狀態(tài)。

節(jié)點尚未加入任何簇的情況下，若連續(xù)3個周期未收到處于CH_READY狀態(tài)的節(jié)點發(fā)送的鄰居通告，則自動轉入CH_READY狀態(tài)。

（3）簇首競爭狀態(tài)

在當前拓撲更新周期內(nèi)，若新增處于CH狀態(tài)的雙向鄰居、且該CH所在簇的容量未滿時，則加入該CH所在的簇，并轉入MEMBER狀態(tài)。

在當前拓撲更新周期內(nèi)，若新增處于CH_READY狀態(tài)的雙向鄰居，當對方更適合作為CH時，本節(jié)點轉入MEMBER狀態(tài)。

本節(jié)點若連續(xù)2個周期處于CH_READY狀態(tài)，則表示競爭簇首成功，進入CH狀態(tài)，并將此時的節(jié)點度記為選舉度S。

（4）網(wǎng)關狀態(tài)

在當前拓撲更新周期內(nèi)，若新增處于CH狀態(tài)的雙向鄰居、且該CH所在簇的容量未滿時，加入該CH所在的簇，作為該簇的網(wǎng)關。

當本節(jié)點鄰居中的CH數(shù)量降為1時，不再充當網(wǎng)關，轉入MEMBER狀態(tài)。

當本網(wǎng)關與相鄰的成員節(jié)點或網(wǎng)關節(jié)點所屬簇首不同時，相鄰的成員節(jié)點或網(wǎng)關節(jié)點則成為本網(wǎng)關的協(xié)作網(wǎng)關節(jié)點。

3.3 路由協(xié)議過程

改進節(jié)點度分簇路由協(xié)議主要包含兩部分內(nèi)容：簇內(nèi)路由過程和簇間路由過程。

（1）簇內(nèi)路由過程

節(jié)點收到上層的單播業(yè)務請求，目的節(jié)點位于簇內(nèi)時，直接查詢簇內(nèi)路由表，若存在到達目的節(jié)點的一跳路徑，則選取簇內(nèi)路由表中最小的路徑作為傳輸路徑；若不存在，選取路由表中最小的兩跳路徑作為傳輸路徑（必然存在簇首作為中轉節(jié)點的傳輸路徑），然后，將傳輸路徑寫入業(yè)務報文首部。

（2）簇間路由過程

節(jié)點收到上層的單播業(yè)務報文請求，目的節(jié)點位于簇外時，通過查詢網(wǎng)關列表、簇間路由表，若存在可用路由，則將傳輸路徑寫入業(yè)務報文首部，進行報文傳遞。若查詢后不存在可用路徑，生成路由請求RREQ消息。查詢路由請求表后，將路由請求消息傳遞給目的節(jié)點，目的節(jié)點生成應答消息RREP，生成“本地-目的節(jié)點”的路由加入簇間路由表，完成簇間路由。

4 仿真與結果分析

設計路由協(xié)議可以更好的構造一個高效率的自組網(wǎng)，分簇路由協(xié)議主要應用節(jié)點較多的場合，分簇算法將自組網(wǎng)分成多個簇，算法的好壞直接影響移動自組網(wǎng)性能。本研究采用OPNET軟件進行仿真驗證。本論文研究的改進節(jié)點度分簇路由協(xié)議，主要在不同節(jié)點移動速度的情況下，對該協(xié)議和原有路由協(xié)議進行比較。在仿真過程中，門閾值統(tǒng)一設為T=2，設定其他參數(shù)一致的前提下，比較二者簇首變更頻率的不同，傳輸時延的不同。仿真具體參數(shù)設置如仿真模擬實驗參數(shù)表1所示。

圖3 簇首變更率示意圖

圖4 不同節(jié)點移動速度下的傳輸時延

5 總結

本文基于最高節(jié)點度算法路由協(xié)議，提出改進節(jié)點度路由協(xié)議，對簇首的變更條件進行改進，并給出詳細算法，從理論和初步試驗證明了改進節(jié)點度分簇路由協(xié)議在簇首變更頻率和傳輸時延方面對自組網(wǎng)性能的提高。

[1]臧小東．Ad Hoc網(wǎng)絡路由協(xié)議的改進研究[學位論文]．南京郵電大學，2013．

[2]劉凱歌．基于分簇結構的Ad Hoc網(wǎng)絡路由協(xié)議的研究與仿真[學位論文]．武漢理工大學，2007．

[3]LIN CR，GERLAM．Adaptive clustering formobile wire -less networks [ J ]．IEEE Journal on Selected Areas in Communications，1997．

[4]鄭少仁，王海濤．Ad Hoc網(wǎng)絡技術[ M ]．北京：人民郵電出版社，2005．

[5]陳敏．OPNET 網(wǎng)絡仿真．北京：清華大學出版社，2004．

[6] Jiang M，Li J，Tay Y．Cluster based routing Protoeol（CBRP）funetional specification[Z]．IETF Intemet-Draft，Aug 1998．

[7]倪旻明．移動Ad Hoc網(wǎng)絡中分簇組網(wǎng)技術的研究[D]．[博士學位論文]．北京：北京交通大學，2012．

[8]Ali Aydin M,Halim Zaim A,Gokhan Ceylan K．A hybrid intrusion detection system design for computer network security[J]．Computers & Electrical Engineering，2009．

Libpcap對數(shù)據(jù)的捕獲是通過幾個主要函數(shù)來完成的。首先調用Pcap-lookupdev()函數(shù)找到查找可以捕獲數(shù)據(jù)包的設備接口，并返回該網(wǎng)絡設備名稱。接著調用Pcap-open()函數(shù)，利用上面查詢到的接口設備創(chuàng)建捕獲句柄，進行數(shù)據(jù)捕獲并將捕獲的數(shù)據(jù)轉換成以太類型，分析判斷包含的數(shù)據(jù)包類型。

Sebek和Libpcap都是在Linux系統(tǒng)內(nèi)核中完成的，可以在不同的層次把兩者結合起來進行多層次數(shù)據(jù)捕獲，保證了數(shù)據(jù)捕獲的全面性和可靠性。

3 結論

本文設計的數(shù)據(jù)捕獲系統(tǒng)是基于Linux系統(tǒng)內(nèi)核的基礎上對傳統(tǒng)Honeypot數(shù)據(jù)捕獲的一種改進，采用雙層捕獲機制，能名夠盡可能地對數(shù)據(jù)包的全面、可靠性捕獲，從而進行深入分析，獲取攻擊者的信息，以便更有效保護好主機系統(tǒng)。

參考文獻：

[1]朱一帥，吳禮發(fā)．基于Sebek的蜜罐識別機制研究[J]．信息技術，2009．

[2]陳超，妙全興．蜜罐識別與反識別技術研究[J]．計算機安全，2009．

[3]田俊峰，劉永立．一種新的蜜網(wǎng)模型——BRHNS[J]．計算機工程與應用，2007．

湖南省教育廳科研基金項目，項目編號：15C0166。