自組織網(wǎng)絡(luò)中的自適應(yīng)分簇路由算法

田斌鵬 黃盛 王昭

1.航空工業(yè)第一飛機(jī)設(shè)計(jì)研究院陜西西安710089 2．中國西南電子技術(shù)研究所四川成都610036

自組織網(wǎng)絡(luò)是由若干個移動節(jié)點(diǎn)通過分布式網(wǎng)絡(luò)協(xié)議自發(fā)組成的一個無中心多跳網(wǎng)絡(luò).自組織網(wǎng)絡(luò)能夠高效地處理網(wǎng)絡(luò)拓?fù)渥兓?、傳輸鏈路故障等問題,具有很強(qiáng)的靈活性和抗毀性.無線自組織網(wǎng)絡(luò)環(huán)境下,節(jié)點(diǎn)間的無線鏈路及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨節(jié)點(diǎn)的位置移動、信道的變化等因素呈現(xiàn)出動態(tài)變化的特性,需通過有效的路由算法保障網(wǎng)絡(luò)節(jié)點(diǎn)之間的連通性[1?5].

無線自組織網(wǎng)絡(luò)具有兩種不同的層次結(jié)構(gòu):平面路由結(jié)構(gòu)和分層路由結(jié)構(gòu)[6?8].在平面路由結(jié)構(gòu)中,所有節(jié)點(diǎn)的地位平等,每個節(jié)點(diǎn)都需要知道到達(dá)其他所有節(jié)點(diǎn)的路由,需要維護(hù)大量的動態(tài)路由控制信息;網(wǎng)絡(luò)規(guī)模越大,路由維護(hù)的開銷就越大,所以平面路由結(jié)構(gòu)的網(wǎng)絡(luò)可擴(kuò)展性較差.分級路由結(jié)構(gòu)需要相應(yīng)的分簇算法和簇維護(hù)機(jī)制,簇頭負(fù)責(zé)本簇內(nèi)成員節(jié)點(diǎn)之間的通信,以及本簇成員節(jié)點(diǎn)和其他簇成員節(jié)點(diǎn)間的通信[9?11].姜春曉等研究了路由算法對提升未來天基指揮控制網(wǎng)絡(luò)效率的重要性[12].分簇路由技術(shù)是提高自組織網(wǎng)絡(luò)效率的有效手段,它可以有效地降低網(wǎng)絡(luò)復(fù)雜度,減小路由開銷[13?15].

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

圖1 多跳自組織網(wǎng)絡(luò)拓?fù)涫疽鈭DFig.1 Network Topology of multi-hop self-organization networks

本文研究由U個節(jié)點(diǎn)構(gòu)建的多跳自組織網(wǎng)絡(luò),節(jié)點(diǎn)集合定義為U={1,2,···,U}.所有節(jié)點(diǎn)可通過自組織網(wǎng)絡(luò)協(xié)議周期地與一跳鄰居節(jié)點(diǎn)交互控制包信息,如圖1所示.在多跳自組織網(wǎng)絡(luò)中,每個網(wǎng)絡(luò)節(jié)點(diǎn)配置了環(huán)境感知、自學(xué)習(xí)和自決策3 大功能模塊,如圖2所示.各個網(wǎng)絡(luò)節(jié)點(diǎn)周期地利用無線傳輸模塊與鄰居節(jié)點(diǎn)交互路由控制信息,由環(huán)境感知功能模塊統(tǒng)計(jì)鄰居節(jié)點(diǎn)的分簇控制信息,再由自學(xué)習(xí)功能模塊將所有鄰居節(jié)點(diǎn)的分簇控制信息提煉成局部網(wǎng)絡(luò)的分簇狀態(tài)變化信息,最終由自決策功能模塊依據(jù)本節(jié)點(diǎn)當(dāng)前的分簇角色,以及相應(yīng)的分簇狀態(tài)轉(zhuǎn)移條件,自適應(yīng)地調(diào)整本節(jié)點(diǎn)的分簇狀態(tài),使得全部網(wǎng)絡(luò)節(jié)點(diǎn)能夠依據(jù)鄰居列表信息,自適應(yīng)地處理網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化和網(wǎng)絡(luò)分簇狀態(tài)變化,實(shí)時地優(yōu)化簇頭選擇與分簇結(jié)果.

圖2 網(wǎng)絡(luò)節(jié)點(diǎn)的功能結(jié)構(gòu)Fig.2 Function structure of network nodes

1.2 問題描述

多跳自組織網(wǎng)絡(luò)在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化的情況下,如何分布式地選擇分簇簇頭、實(shí)時地優(yōu)化節(jié)點(diǎn)分簇狀態(tài)及分簇鏈接關(guān)系,自適應(yīng)地完成簇頭選擇、簇頭替換、簇頭切換、分簇裂變、分簇合并等流程,從而達(dá)到均衡分簇規(guī)模并保障網(wǎng)絡(luò)連通性的目標(biāo).

2 自適應(yīng)分簇路由算法

自適應(yīng)分簇路由算法利用分簇控制信息交互觸發(fā)網(wǎng)絡(luò)節(jié)點(diǎn),依據(jù)分簇狀態(tài)轉(zhuǎn)移條件和轉(zhuǎn)移流程實(shí)時地更新本節(jié)點(diǎn),分簇狀態(tài)及分簇鏈接關(guān)系.

2.1 分簇控制信息

分簇控制信息如表1所示,包含該節(jié)點(diǎn)的簇頭權(quán)值、分簇狀態(tài)及目的節(jié)點(diǎn)ID、連通簇頭集合和鄰居列表.其中,簇頭權(quán)值表示該鄰居節(jié)點(diǎn)適合擔(dān)任簇頭節(jié)點(diǎn)的程度,簇頭權(quán)值越高的節(jié)點(diǎn)越適合在自組織網(wǎng)絡(luò)中擔(dān)任簇頭節(jié)點(diǎn);分簇狀態(tài)包含申請入簇、簇成員、簇頭、簇頭替換、簇頭切換、分簇裂變和分簇合并共7 種狀態(tài),分簇狀態(tài)及目的節(jié)點(diǎn)ID 表明了該鄰居節(jié)點(diǎn)的分簇角色與該鄰居節(jié)點(diǎn)正在執(zhí)行的分簇操作,以及配合其完成分簇操作的目的節(jié)點(diǎn);連通簇頭集合包含該鄰居節(jié)點(diǎn)能夠連通的所有簇頭節(jié)點(diǎn),可用于判斷分簇結(jié)構(gòu)在自組織網(wǎng)絡(luò)中的連通性;鄰居列表包含該鄰居節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn),表明了該鄰居節(jié)點(diǎn)在自組織網(wǎng)絡(luò)中的局部拓?fù)浣Y(jié)構(gòu).

表1 分簇控制信息示例Table 1 Cluster control information

2.2 節(jié)點(diǎn)分簇狀態(tài)轉(zhuǎn)移條件

在多跳自組織網(wǎng)絡(luò)中,任意節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)的分簇控制信息后,由自學(xué)習(xí)功能模塊提取鄰居列表信息、分簇狀態(tài)信息、連通簇頭信息和簇頭權(quán)值信息,并依據(jù)節(jié)點(diǎn)分簇狀態(tài)轉(zhuǎn)移條件,分析本節(jié)點(diǎn)兩跳范圍內(nèi)的局部網(wǎng)絡(luò)的分簇狀態(tài)變化信息.

1)簇頭替換條件:本節(jié)點(diǎn)的鄰居節(jié)點(diǎn)及本節(jié)點(diǎn)組成的集合,是某個鄰居簇頭及其鄰居節(jié)點(diǎn)組成的集合的真超集.

2)成功入簇條件:本節(jié)點(diǎn)指定的簇頭的分簇狀態(tài)為簇頭,并且該簇頭的鄰居列表信息包含本節(jié)點(diǎn)ID.

3)簇頭切換條件:本節(jié)點(diǎn)的所有鄰居簇頭之間是連通的,并且所有鄰居簇頭以及它們的鄰居節(jié)點(diǎn)的并集是本節(jié)點(diǎn)及本節(jié)點(diǎn)的鄰居節(jié)點(diǎn)組成的集合的超集.

4)分簇裂變條件:本節(jié)點(diǎn)為簇頭且收到了新的入簇申請,并且當(dāng)前簇成員的數(shù)目加上新入簇成員的數(shù)目,將達(dá)到預(yù)設(shè)的最大簇成員容量限制.

5)分簇合并條件:當(dāng)前控制周期內(nèi)存在鄰節(jié)點(diǎn)的連通簇頭集合中的最小節(jié)點(diǎn)ID,不等于本節(jié)點(diǎn)的連通簇頭集合中的最小節(jié)點(diǎn)ID.

6)鄰簇合并狀態(tài):當(dāng)前控制周期內(nèi)存在鄰簇的簇頭的分簇狀態(tài)為分簇合并,則鄰簇合并狀態(tài)的判斷結(jié)果為存在鄰簇處于合并狀態(tài).

2.3 節(jié)點(diǎn)分簇狀態(tài)轉(zhuǎn)移流程

在多跳自組織網(wǎng)絡(luò)中,網(wǎng)絡(luò)節(jié)點(diǎn)依據(jù)本節(jié)點(diǎn)分簇角色與分簇狀態(tài)轉(zhuǎn)移條件,自適應(yīng)地執(zhí)行分簇路由流程,完成申請入簇、提升簇頭、簇頭替換、簇頭切換、分簇裂變、分簇合并等分簇狀態(tài)更新行為,優(yōu)化全網(wǎng)分簇路由結(jié)構(gòu),如圖3所示.

2.3.1 待入簇節(jié)點(diǎn)

待入簇節(jié)點(diǎn)的分簇狀態(tài)轉(zhuǎn)移流程如下:

1)待入簇節(jié)點(diǎn)判斷簇頭替換條件;若簇頭替換條件滿足,則本節(jié)點(diǎn)的分簇角色提升為簇頭節(jié)點(diǎn);否則,待入簇節(jié)點(diǎn)繼續(xù)判斷候選簇頭集合是否非空.

圖3 節(jié)點(diǎn)分簇狀態(tài)轉(zhuǎn)移流程Fig.3 Transition process of node cluster states

2)若本節(jié)點(diǎn)的候選簇頭集合為空,則本節(jié)點(diǎn)的分簇角色提升為簇頭節(jié)點(diǎn);否則,待入簇節(jié)點(diǎn)繼續(xù)選擇合適的簇頭.

3)待入簇節(jié)點(diǎn)從候選簇頭集合中選擇簇頭權(quán)值最大的簇頭作為本節(jié)點(diǎn)指定的簇頭,并通過本節(jié)點(diǎn)的分簇控制信息申請加入該分簇.

2.3.2 申請入簇節(jié)點(diǎn)

申請入簇節(jié)點(diǎn)的分簇狀態(tài)轉(zhuǎn)移流程如下:

1)申請入簇節(jié)點(diǎn)判斷成功入簇條件;若成功入簇條件滿足,本節(jié)點(diǎn)的分簇角色設(shè)置為簇成員節(jié)點(diǎn);否則,申請入簇節(jié)點(diǎn)更新候選簇頭集合.

若本節(jié)點(diǎn)的候選簇頭集合為空,則本節(jié)點(diǎn)的分簇角色提升為簇頭節(jié)點(diǎn).

否則,本節(jié)點(diǎn)從候選簇頭集合中選擇簇頭權(quán)值最大的簇頭作為本節(jié)點(diǎn)指定的簇頭,并通過本節(jié)點(diǎn)的分簇控制信息申請加入該分簇.

2.3.3 簇成員節(jié)點(diǎn)

簇成員節(jié)點(diǎn)的分簇狀態(tài)轉(zhuǎn)移流程如下:

1)若簇成員節(jié)點(diǎn)收到了本簇簇頭的切換消息,則本節(jié)點(diǎn)以待入簇節(jié)點(diǎn)的身份執(zhí)行分簇狀態(tài)轉(zhuǎn)移.

2)否則:

上述分析表明，四大自貿(mào)試驗(yàn)區(qū)在“一帶一路”建設(shè)中的定位有所不同，因此，各個自貿(mào)試驗(yàn)區(qū)應(yīng)根據(jù)自身優(yōu)勢及戰(zhàn)略定位，差異化參與和推動“一帶一路”建設(shè)。

a)若簇成員收到了本簇裂變消息,則本節(jié)點(diǎn)依據(jù)裂變消息與鄰居列表信息執(zhí)行如下操作:

①若本節(jié)點(diǎn)為本簇簇頭指定的新簇頭,則本節(jié)點(diǎn)將分簇角色提升為簇頭節(jié)點(diǎn).

②否則,若新簇頭為本節(jié)點(diǎn)的鄰居節(jié)點(diǎn),則本節(jié)點(diǎn)將分簇控制信息的目的節(jié)點(diǎn)ID 更換為新簇頭ID.

③否則,本節(jié)點(diǎn)保持分簇控制信息的目的節(jié)點(diǎn)ID 為原簇頭ID.

b)否則,本節(jié)點(diǎn)判斷分簇合并條件與鄰簇合并狀態(tài):

①若分簇合并條件滿足并且無鄰簇處于合并狀態(tài),則本節(jié)點(diǎn)觸發(fā)分簇合并流程,本節(jié)點(diǎn)的分簇角色提升為簇頭節(jié)點(diǎn),分簇合并流程將無連通鏈路的兩個分簇的邊緣節(jié)點(diǎn)提升為簇頭節(jié)點(diǎn),為這兩個分簇構(gòu)建連通鏈路,實(shí)現(xiàn)分簇間的數(shù)據(jù)中繼傳輸.

②否則,本節(jié)點(diǎn)的分簇角色保持為簇成員節(jié)點(diǎn).

2.3.4 簇頭節(jié)點(diǎn)

簇頭節(jié)點(diǎn)的分簇狀態(tài)轉(zhuǎn)移流程如下:

1)簇頭節(jié)點(diǎn)判斷簇頭切換條件;若簇頭切換條件滿足,則本節(jié)點(diǎn)觸發(fā)簇頭切換流程,簇頭切換流程指導(dǎo)本簇的簇成員加入其他鄰居簇頭節(jié)點(diǎn)來優(yōu)化分簇結(jié)構(gòu);否則,本節(jié)點(diǎn)繼續(xù)判斷分簇裂變條件.

2)若分簇裂變條件滿足,則本節(jié)點(diǎn)觸發(fā)分簇裂變流程,分簇裂變流程指導(dǎo)本簇的簇成員構(gòu)建新分簇來均衡網(wǎng)絡(luò)分簇規(guī)模,本節(jié)點(diǎn)從本簇的簇成員中選擇鄰居節(jié)點(diǎn)數(shù)最多的節(jié)點(diǎn)作為新簇頭,通知新簇頭及本簇的簇成員進(jìn)行分簇裂變;否則,本節(jié)點(diǎn)繼續(xù)判斷分簇合并條件.

3)若分簇合并條件滿足,則本節(jié)點(diǎn)將分簇控制信息的目的節(jié)點(diǎn)ID 設(shè)置為連通簇頭集合的最小ID,與本節(jié)點(diǎn)的連通簇頭集合的最小ID 不一致的鄰居節(jié)點(diǎn)的ID,并將本節(jié)點(diǎn)連通簇頭集合更新為本節(jié)點(diǎn)的連通簇頭集合,與目的節(jié)點(diǎn)ID 的連通簇頭集合的并集,通過交互分簇控制信息完成分簇合并;否則,本節(jié)點(diǎn)保持為簇頭節(jié)點(diǎn).

3 仿真結(jié)果與數(shù)值分析

3.1 仿真設(shè)置

利用OPNET 仿真軟件,驗(yàn)證自適應(yīng)分簇路由算法在路由收斂時間和網(wǎng)絡(luò)開銷上的性能.在OPNET仿真軟件中構(gòu)建了32 個節(jié)點(diǎn)的柵格拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)場景,并且設(shè)置32 個節(jié)點(diǎn)在1 s 時刻同時開機(jī),各個節(jié)點(diǎn)在完成入網(wǎng)操作后,通過執(zhí)行自適應(yīng)分簇路由算法來構(gòu)建本節(jié)點(diǎn)的路由表.

3.2 仿真結(jié)果

圖4 全網(wǎng)節(jié)點(diǎn)路由收斂時間Fig.4 Route convergence time for whole network nodes

圖5 全網(wǎng)節(jié)點(diǎn)平均路由信息開銷Fig.5 Average cost of route information for whole network nodes

如圖4和圖5所示,所有網(wǎng)絡(luò)節(jié)點(diǎn)在開機(jī)后,各個網(wǎng)絡(luò)節(jié)點(diǎn)通過交互分簇控制信息迅速地發(fā)現(xiàn)其他網(wǎng)絡(luò)節(jié)點(diǎn),在約30 s 時刻全網(wǎng)節(jié)點(diǎn)可達(dá)的平均目的節(jié)點(diǎn)個數(shù)已經(jīng)達(dá)到30 個.此時,由于網(wǎng)絡(luò)拓?fù)渲行氯刖W(wǎng)的成員迅速增多,導(dǎo)致分簇狀態(tài)中簇頭成員比例較高,因此,平均路由開銷最高.隨著在網(wǎng)成員數(shù)逐漸穩(wěn)定,網(wǎng)絡(luò)成員自適應(yīng)地依據(jù)實(shí)時網(wǎng)絡(luò)拓?fù)錉顟B(tài)完成分簇狀態(tài)轉(zhuǎn)移.在50 s 時刻全網(wǎng)節(jié)點(diǎn)即可獲得所有其余31 個目的節(jié)點(diǎn)的路由信息,網(wǎng)絡(luò)分簇結(jié)構(gòu)能夠收斂至穩(wěn)定的狀態(tài),全網(wǎng)平均路由開銷也逐漸下降至較優(yōu)值.當(dāng)全網(wǎng)路由信息收斂時,32 個節(jié)點(diǎn)的分簇狀態(tài)及分簇鏈接關(guān)系如圖6所示.

圖6 分簇拓?fù)浞抡娼Y(jié)果Fig.6 Simulation results of clustered topology

4 結(jié)論

在多跳自組織網(wǎng)絡(luò)中,提出了一種自組織網(wǎng)絡(luò)的自適應(yīng)分簇路由算法,通過優(yōu)化分簇控制信息、節(jié)點(diǎn)分簇狀態(tài)轉(zhuǎn)移條件和節(jié)點(diǎn)分簇狀態(tài)轉(zhuǎn)移流程,使得網(wǎng)絡(luò)節(jié)點(diǎn)的路由信息能夠?qū)崟r地匹配網(wǎng)絡(luò)拓?fù)渑c鏈路狀態(tài)的變化,優(yōu)化簇頭選擇和分簇鏈接關(guān)系,從而達(dá)到均衡分簇規(guī)模并保障網(wǎng)絡(luò)連通性的目標(biāo).通過OPNET 仿真驗(yàn)證,本文提出的自適應(yīng)分簇路由算法具有快速收斂的優(yōu)點(diǎn),全網(wǎng)平均路由開銷可快速收斂至較優(yōu)值.