黃慶東，閆喬喬，孫 晴

?

一種改進的Ad Hoc無線網(wǎng)絡(luò)連通支配集生成方法

黃慶東，閆喬喬，孫 晴

(西安郵電大學(xué)通信與信息工程學(xué)院, 信息與通信技術(shù)國家級實驗教學(xué)中心 西安 710121)

該文研究了Ad hoc無線網(wǎng)中連通支配集(CDS)的生成方法，并對CDS算法做了兩個方面的改進: 1) 通過引入拓撲相關(guān)信息的特征矢量中心性值進行節(jié)點編號，避免節(jié)點縮減時的隨機性，使節(jié)點縮減與實際網(wǎng)絡(luò)拓撲緊密聯(lián)系；2) CDS算法忽略了最大編號節(jié)點的可縮減性，為此改進了該算法并提出新規(guī)則實現(xiàn)最大編號節(jié)點的縮減判定。該方法解決了CDS算法在生成連通支配集時存在的完全NP難問題，而且可得到條件最優(yōu)連通支配集。仿真結(jié)果驗證了改進算法的優(yōu)良特性。

Ad hoc無線網(wǎng); 支配集; 路由; 拓撲; 無向圖

無線自組織(Ad hoc)網(wǎng)絡(luò)中移動節(jié)點的主要特征是帶寬低、移動性、能量有限。將適應(yīng)于固定網(wǎng)絡(luò)的傳統(tǒng)路由協(xié)議應(yīng)用到Ad hoc網(wǎng)絡(luò)中，會存在路由表生命周期短、耗費大等問題，不適應(yīng)于無線動態(tài)網(wǎng)絡(luò)。在Ad hoc網(wǎng)絡(luò)中，節(jié)點的移動性及節(jié)點能量有限，促使在Ad hoc網(wǎng)絡(luò)中建立路由是一項既具挑戰(zhàn)性又十分重要的工作。

文獻[1-3]借助網(wǎng)絡(luò)拓撲改善網(wǎng)絡(luò)性能，在Ad hoc網(wǎng)絡(luò)中把搜索路徑簡化到連通支配集進行路由[3-8]。支配集中的節(jié)點稱為網(wǎng)關(guān)節(jié)點/主機(gateway host)，這意味著僅僅網(wǎng)關(guān)節(jié)點需要保持路由信息[3]。只要網(wǎng)絡(luò)拓撲改變沒有影響到連通支配集，就不需要重新計算路由表。文獻[3]提出一種簡單、有效的分布式計算CDS的算法，但此方法得到的連通支配集并不是最優(yōu)的。文獻[4]針對支配集節(jié)點能量消耗均衡的問題，提出了輪流成為支配集節(jié)點的改善方法。文獻[5]將連通支配集方法擴展到單向鏈路網(wǎng)絡(luò)中。文獻[6]說明了生成最小連通支配集的完全NP難事實，為了避免信息冗余的影響，對支配集進行擴展。文獻[7-8]分別對于網(wǎng)絡(luò)能耗和信息冗余方面進行改善，以提高Ad hoc網(wǎng)絡(luò)的性能和改善能耗。文獻[9]對于城市交通網(wǎng)絡(luò)提出基于連通支配集的骨干網(wǎng)絡(luò)，用以避免局部數(shù)據(jù)阻塞和數(shù)據(jù)延遲大問題。文獻[10]基于區(qū)域的網(wǎng)絡(luò)構(gòu)建和維護穩(wěn)健的連通支配集。上述這些算法大多局限于路由節(jié)點的產(chǎn)生和構(gòu)建，對于網(wǎng)絡(luò)本身拓撲信息卻很少涉及，屬于“拓撲未知”類方法，故而得到的支配集并不是最優(yōu)的，所以網(wǎng)絡(luò)性能也沒有達到最優(yōu)。最小連通支配集的完全NP難問題依然懸而未決。本文提出的改進算法是一種全分布式無中心“拓撲可知”方法，通過網(wǎng)內(nèi)分布式計算合理利用拓撲相關(guān)信息，提升網(wǎng)絡(luò)性能。

本文結(jié)合圖譜理論中的特征矢量中心性對文獻[3]所述的CDS方法進行改進，通過網(wǎng)內(nèi)分布式計算獲得網(wǎng)絡(luò)拓撲的相關(guān)信息，對最小連通支配集的完全NP難問題進行了妥善解決，結(jié)合網(wǎng)絡(luò)拓撲信息得到最優(yōu)連通支配集，并給出相關(guān)定理及證明。同時，對網(wǎng)絡(luò)拓撲改變時的更新/重算方法進行了改進。

1 圖論相關(guān)概念及分布計算

1.1 特征矢量中心性[1]

1.2 特性[1]

因此，

1.3 分布式網(wǎng)內(nèi)計算[1]

所以，可以網(wǎng)內(nèi)執(zhí)行冪迭代(power iteration, PI)：

這里同樣需要利用與前面相似的技術(shù)，進行一個合適的增長/衰減比例的補償。

2 連通支配集的生成算法

支配集的生成過程只需要與鄰居節(jié)點進行本地信息交換和固定數(shù)量迭代循環(huán)就可以通過分布式方式實現(xiàn)。由于要在此支配集上建立路由，將路徑搜索功能在此支配集上實現(xiàn)，因此生成的支配集應(yīng)該是連通的，并盡可能小，生成的支配集應(yīng)包括任何最短路徑的所有中間節(jié)點。

CDS算法包括標(biāo)記過程、縮減規(guī)則一、縮減規(guī)則二，以及由于網(wǎng)絡(luò)拓撲改變而采取的更新/重算方法。

2.1 標(biāo)記連通支配集

標(biāo)記過程[3]：

定理 3 任何兩個節(jié)點間最短路徑的中間節(jié)點，不存在非網(wǎng)關(guān)節(jié)點。

由于確定連通圖的一個最小連通支配集是完全NP難(NP-complete)問題，標(biāo)記過程獲得的連通支配集通常不是最小的，因此要對連通支配集進行縮減。

2.2 縮減過程[3]

2.3 更新/重算連通支配集[3]

在Ad hoc網(wǎng)絡(luò)中，每一個節(jié)點可以不受距離和速度限制而移動。同時，為了降低能耗，移動節(jié)點可以在任何時刻關(guān)機一段時間后再開機。因此Ad hoc網(wǎng)絡(luò)的拓撲改變可歸結(jié)為3種情況：移動節(jié)點開機，移動節(jié)點關(guān)機，移動節(jié)點運動。

3 改進的連通支配集生成算法

由于確定連通圖的一個最小連通支配集是完全NP難問題，獲得的連通支配集一般不是最小的，為了使連通支配集盡可能小，通過兩個縮減進行改善，然而這樣同樣不能保證得到的支配集是最小的。本文在生成連通支配集時，借助“拓撲可知”理論，引入拓撲相關(guān)信息，進而為解決此完全NP難問題打開途徑。通過引入拓撲相關(guān)信息后，對網(wǎng)絡(luò)中不同位置的節(jié)點按照對網(wǎng)絡(luò)“影響”大小進行排序并id編號，這樣避免了CDS算法中節(jié)點id編號的隨意性和無網(wǎng)絡(luò)拓撲相關(guān)意義的缺點。由于CDS算法中id編號僅是為了避免將“同時違規(guī)”的所有頂點同時刪除而設(shè)置，使問題呈現(xiàn)完全NP難，通過為id編號賦予網(wǎng)絡(luò)拓撲相關(guān)特性后，問題便有了條件最優(yōu)解。

與CDS算法相似，這里改進算法也包括標(biāo)記過程、縮減規(guī)則1、縮減規(guī)則2和新建規(guī)則3，以及由于網(wǎng)絡(luò)拓撲改變而采取的更新/重算方法。

3.1 標(biāo)記連通支配集

3.2 改進的縮減過程

實際上規(guī)則1和規(guī)則2對于最大id編號的網(wǎng)關(guān)節(jié)點會產(chǎn)生漏判情況，即如果最大id編號的網(wǎng)關(guān)節(jié)點是冗余的，那么通過規(guī)則1、規(guī)則2是無法刪減掉的。這里提出規(guī)則3來解決此問題。

定理 4 經(jīng)標(biāo)記過程后通過改進縮減過程(規(guī)則1、規(guī)則2和規(guī)則3)得到的縮減圖是一個條件最優(yōu)連通支配集，它是在規(guī)則1、規(guī)則2和規(guī)則3條件下生成的一個最小連通支配集。

由定理4可知，改進的連通支配集生成算法得到的連通支配集節(jié)點數(shù)量不會多于CDS支配集生成方法得到的連通支配集的節(jié)點數(shù)量，此方法是條件最優(yōu)的。

3.3 改進的更新/重算連通支配集

3.4 基于連通支配集的路由

對于最小連通支配集上的路由方法，與文獻[3]方法相同，這里不再贅述。

4 仿真分析

圖1 CDS連通支配集生成圖

圖2 改進連通支配集生成圖

圖3 支配集中平均網(wǎng)關(guān)節(jié)點數(shù)對比(r=0.4)

圖4 支配集中平均網(wǎng)關(guān)節(jié)點數(shù)對比( r =0.6)

5 結(jié)束語

本文通過研究Ad hoc無線網(wǎng)絡(luò)的路由機制，對可以用來建立路由的連通支配集生成算法進行改進。改進主要有兩個方面：1) 通過借助“拓撲可知”理論，通過網(wǎng)內(nèi)節(jié)點的分布式計算獲得含有拓撲相關(guān)相信的特征矢量中心性值，并利用特征矢量中心性值進行節(jié)點id編號，避免了節(jié)點縮減時的隨機性，使節(jié)點縮減與實際網(wǎng)絡(luò)拓撲緊密聯(lián)系；2) CDS算法對最大id節(jié)點是否可縮減并沒有進行判定，改進算法提出規(guī)則3來完成最大id節(jié)點的縮減判定。通過改進，本文通過“拓撲可知”相關(guān)的圖譜理論，將CDS算法中完全NP難問題轉(zhuǎn)變?yōu)榫哂袟l件最優(yōu)解的問題，改進算法可得到條件最小支配集，無需中心節(jié)點，可以完全分布式實現(xiàn)。

[1] BERTRAND A, MOONEN M. Seeing the bigger picture: How nodes can learn their place within a complex ad hoc network topology[J]. IEEE Signal Processing Magazine, 2013, 30(3): 71-82.

[2] BERTRAND A, MOONEN M. Distributed computation of the fiedler vector with application to topology inference in ad hoc networks[J]. Signal Processing, 2013, 93(5): 1106-1117.

[3] WU J, LI H L. A dominating-set-based routing scheme in ad hoc wireless networks[J]. Telecommunication Systems, 2001, 18(1-3): 13-36.

[4] WU Jie, LI H L. On calculating connected dominating set for efficient routing in Ad hoc wireless networks[J].Journal of Communications and Networks, 2002, 4(1): 59-70.

[5] WU J. Extended dominating-set-based routing in ad hoc wireless networks with unidirectional links[J].IEEE Transactions on Parallel and Distributed Systems, 2002, 13(9): 866-881.

[6] WU J, CARDEI M, FEI D, et al.Extended dominating set and its applications in ad hoc networks using cooperative communication[J].IEEE Transactions on Parallel and Distributed Systems, 2006, 17(8):851-864.

[7] WANG X Y, LI J. Improving the network lifetime of MANETs through cooperative MAC protocol design[J].IEEE Transactions on Parallel and Distributed Systems, 2015, 26(4): 1010-1020.

[8] LEU J, CHEN J, LI K. Hybrid search scheme for social networks supported by dynamic weighted distributed label clustering[J].IEEE Transactions on Computers, 2015, 64(9): 2586-2594.

[9] TOGOU M A, HAFID A, KHOUKHI L. SCRP: Stable CDS-based routing protocol for urban vehicular ad hoc networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2016, 17(5): 1298-1307.

[10] GUO S, XING N, FU N, et al. Area-based connected dominating set construction and maintenance algorithm in ubiquitous stub environment[J]. China Communications, 2015, 12(9): 141-149.

[11] LI Z Q, RICHARD Y F, HUANG M Y. A distributed consensus-based cooperative spectrum-sensing scheme in cognitive radios[J]. IEEE Transactions on Vehicular Technology, 2010, 59(1): 383-392.

編 輯 葉 芳

An Improved Formation Method of Connected-Dominating Set in Ad Hoc Wireless Networks

HUANG Qing-dong, YAN Qiao-qiao, and SUN Qing

(School of Communication and Information Engineering, Informations and Communications Technology of National Experimental Teaching Center, Xi’an University of Posts and Telecommunications Xi’an 710121)

The formation method of connected-dominating set (CDS) in ad hoc wireless network is studied and improved. There are two improvements in this paper, the first one is numbering the nodes by introducing the eigenvector center value of the network topology information, which avoids the randomness during node reduction and makes the node reduction be related to the actual network topology closely. The second one is that CDS algorithm ignores the removal of the largest numbered nodes, the improved one proposes a new rule to achieve the reduction of the maximum number nodes. Thus, the improved method solves the NP-complete problem of the CDS algorithm in formation method of connected-dominating set and achieves the conditional optimal connected-dominating set. The simulation results show the excellent characteristics of the improved method

Ad hoc wireless networks; dominating sets; routing; topology; undirected graph

TN911.23

A

10.3969/j.issn.1001-0548.2017.06.004

2016-05-17；

2017-04-11

國家重大專項(2017ZX03001012-005)

黃慶東(1976-)，男，副教授，博士，主要從事分布式信號處理，陣列信號處理、低復(fù)雜度算法等方面的研究.