鄭明才，趙小超，趙晉琴

1.湖南第一師范學(xué)院信息科學(xué)與工程學(xué)院，長沙4102052.湖南第一師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，長沙410205

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0363-09

?

泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)混合拓?fù)浣Y(jié)構(gòu)研究*

鄭明才1+，趙小超2，趙晉琴1

1.湖南第一師范學(xué)院信息科學(xué)與工程學(xué)院，長沙410205
2.湖南第一師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，長沙410205

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0363-09

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The Natural Science Foundation of Hunan Province of China under Grant No. 2015JJ2037 (湖南省自然科學(xué)基金); the Program of Key Laboratory of Hunan Province Based on Information Technology of Basic Education under Grant No. 2015TP1017 (基礎(chǔ)教育信息化技術(shù)湖南省重點(diǎn)實(shí)驗(yàn)室項(xiàng)目).

Received 2015-05,Accepted 2015-07.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-07-13, http://www.cnki.net/kcms/detail/11.5602.TP.20150713.1036.001.html

摘要：針對泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)的特點(diǎn)，提出了一種基于位置和定向擴(kuò)散機(jī)制的泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)混合邏輯拓?fù)浣Y(jié)構(gòu)HLT-L&DD（hybrid logical topology based on location and directed diffusion mechanism），并給出了形成HLT-L&DD的控制方法。在HLT-L&DD中，各路邊節(jié)點(diǎn)根據(jù)任務(wù)需求自定為簇首，以其位置信息作為其所在分簇的簇標(biāo)識ID，并以定向擴(kuò)散機(jī)制分布式啟動分簇過程，逐跳吸納跳數(shù)距離近的車輛節(jié)點(diǎn)加入本簇，不同的路邊節(jié)點(diǎn)獨(dú)立形成若干個分簇；各相鄰分簇之間通過邊沿節(jié)點(diǎn)的定向擴(kuò)散機(jī)制實(shí)現(xiàn)彼此相聯(lián)，最終將各獨(dú)立分簇互聯(lián)成一個完整的混合邏輯拓?fù)浣Y(jié)構(gòu)HLT-L&DD。HLT-L&DD是平面邏輯拓?fù)浣Y(jié)構(gòu)與層次型邏輯拓?fù)浣Y(jié)構(gòu)的混合拓?fù)浣Y(jié)構(gòu)，既便于車輛傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的泛在自組成網(wǎng)、分區(qū)自治，也便于路邊節(jié)點(diǎn)與其他諸如Internet等傳統(tǒng)網(wǎng)絡(luò)的泛在互聯(lián)。理論分析和仿真結(jié)果表明，HLT-L&DD有利于減小泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)邏輯拓?fù)浣Y(jié)構(gòu)建立與動態(tài)維護(hù)的時間開銷,以及提高網(wǎng)絡(luò)的實(shí)時連通性，從而優(yōu)化泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)的綜合性能。

關(guān)鍵詞：車輛傳感器網(wǎng)絡(luò)；泛在互聯(lián)；混合邏輯拓?fù)浣Y(jié)構(gòu)；定向擴(kuò)散；性能優(yōu)化

1　引言

隨著社會的發(fā)展，人們對社會信息化服務(wù)的需求越來越高。傳統(tǒng)互聯(lián)網(wǎng)絡(luò)通過異構(gòu)通信網(wǎng)絡(luò)的互聯(lián)一定程度上實(shí)現(xiàn)了抽象信息空間的共享，但抽象信息的獲取手段和效率還相當(dāng)落后和低下，自動化程度不高，信息感知覆蓋范圍還不廣，泛在物理空間到抽象信息空間的轉(zhuǎn)換渠道尚不順暢。為滿足不斷提高的社會信息化服務(wù)需求，傳感器網(wǎng)絡(luò)[1]、物聯(lián)網(wǎng)[2]、泛在網(wǎng)絡(luò)[3]等新興網(wǎng)絡(luò)概念不斷被提出，并被提升到國家信息化戰(zhàn)略高度，被普遍當(dāng)作為實(shí)現(xiàn)“智慧地球”、“感知中國”、“數(shù)字城市”等國家信息化戰(zhàn)略舉措的關(guān)鍵技術(shù)。車輛傳感器網(wǎng)絡(luò)（vehicular sensor networks，VSN）[4]是一類依托交通運(yùn)輸設(shè)施且包容傳感網(wǎng)、物聯(lián)網(wǎng)、泛在網(wǎng)技術(shù)的綜合網(wǎng)絡(luò)，車輛移動環(huán)境下的覆蓋區(qū)域十分寬廣，具有強(qiáng)大的泛在信息感知、處理、傳輸、應(yīng)用等能力，可以配置為滿足社會高水平泛在信息化服務(wù)需求的公用信息服務(wù)平臺，促進(jìn)“智慧地球”、“感知中國”、“數(shù)字城市”等信息化戰(zhàn)略的實(shí)現(xiàn)，不僅在智能交通領(lǐng)域有巨大的用途，還可為社會公共安全服務(wù)、環(huán)境監(jiān)控等其他各行各業(yè)具體應(yīng)用提供廉價的信息獲取途徑和信息公共服務(wù)支撐環(huán)境，提供面向行業(yè)應(yīng)用子集的共性支撐平臺。但由于交通車輛的高速運(yùn)動特性，以及網(wǎng)絡(luò)規(guī)模巨大，節(jié)點(diǎn)分布狀況極其復(fù)雜，物理拓?fù)浣Y(jié)構(gòu)動態(tài)變化，突發(fā)負(fù)載頻繁等特性，泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)中的高效信息傳送問題成為制約其大規(guī)模實(shí)際應(yīng)用的瓶頸，而網(wǎng)絡(luò)邏輯拓?fù)浣Y(jié)構(gòu)是信息高效傳送的關(guān)鍵，故有必要對制約信息高效傳送的泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)邏輯拓?fù)浣Y(jié)構(gòu)進(jìn)行深入研究。

2　相關(guān)工作

傳感器網(wǎng)絡(luò)中的高效信息傳送與網(wǎng)絡(luò)邏輯拓?fù)浣Y(jié)構(gòu)密切相關(guān)，綜合已有研究成果[5]，傳感器網(wǎng)絡(luò)邏輯拓?fù)浣Y(jié)構(gòu)大體可以分為平面型邏輯拓?fù)浣Y(jié)構(gòu)[6]和層次型邏輯拓?fù)浣Y(jié)構(gòu)[7]兩大類。平面型邏輯拓?fù)浣Y(jié)構(gòu)控制算法簡單，但邏輯拓?fù)浣Y(jié)構(gòu)建立時間長，可擴(kuò)展性差，不適合用于大規(guī)模網(wǎng)絡(luò)和物理拓?fù)浣Y(jié)構(gòu)頻繁變化的網(wǎng)絡(luò)。層次型邏輯拓?fù)浣Y(jié)構(gòu)通過網(wǎng)絡(luò)節(jié)點(diǎn)的分層或分簇降低了邏輯拓?fù)浣Y(jié)構(gòu)管理難度，具有優(yōu)良的可擴(kuò)展性，但控制算法一般相對較復(fù)雜，控制開銷大[8]。與傳統(tǒng)無線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSN）[9]相比，泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)具有一系列與之不同的特點(diǎn)[10-11]，傳統(tǒng)無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其控制技術(shù)無法直接應(yīng)用于泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)，需適當(dāng)進(jìn)行針對性調(diào)整。

與傳感器網(wǎng)絡(luò)中信息傳送的方向性特點(diǎn)[12]相適應(yīng)，文獻(xiàn)[6]描述了一種適于傳感器網(wǎng)絡(luò)任務(wù)分發(fā)和數(shù)據(jù)收集的，基于跳數(shù)和定向擴(kuò)散（directed diffusion, DD）機(jī)制的網(wǎng)絡(luò)邏輯拓?fù)浣Y(jié)構(gòu)，即最小跳數(shù)路由（minimum hop routing, MHR）依賴的定向擴(kuò)散梯度場（directed diffusion gradient field for MHR, DDGFMHR）。為確保網(wǎng)絡(luò)邏輯拓?fù)浣Y(jié)構(gòu)與網(wǎng)絡(luò)物理拓?fù)浣Y(jié)構(gòu)的動態(tài)一致性，文獻(xiàn)[13]提出了一種邏輯拓?fù)浣Y(jié)構(gòu)的動態(tài)調(diào)整策略，當(dāng)網(wǎng)絡(luò)物理拓?fù)浣Y(jié)構(gòu)緩慢變化時能以較低代價實(shí)現(xiàn)網(wǎng)絡(luò)邏輯拓?fù)浣Y(jié)構(gòu)與物理拓?fù)浣Y(jié)構(gòu)的高度一致性，但當(dāng)節(jié)點(diǎn)高速移動或網(wǎng)絡(luò)物理拓?fù)浣Y(jié)構(gòu)快速變化時效果不是很理想，故不能直接應(yīng)用于泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)。針對車輛傳感器網(wǎng)絡(luò)的特點(diǎn)，文獻(xiàn)[14]提出了一種以路邊節(jié)點(diǎn)為局部核心的可滑動定向擴(kuò)散梯度場（directed diffusion gradient field with sliding roadside-node gradient，DDGFSRG）作為車輛傳感器網(wǎng)絡(luò)邏輯拓?fù)浣Y(jié)構(gòu)，通過定向擴(kuò)散梯度場的可滑動性或可折疊性以實(shí)現(xiàn)定向擴(kuò)散梯度場的分布式建立和維護(hù)。DDGF-SRG雖然通過路邊節(jié)點(diǎn)啟動各局部定向擴(kuò)散梯度場的分布式建立，但沒有規(guī)定車輛節(jié)點(diǎn)始終以就近的路邊節(jié)點(diǎn)為局部核心，當(dāng)路邊節(jié)點(diǎn)的估計(jì)梯度值與實(shí)際梯度值存在差異時，隨著局部定向擴(kuò)散梯度場延伸到相鄰局部定向擴(kuò)散梯度場，節(jié)點(diǎn)尤其是車輛節(jié)點(diǎn)的數(shù)據(jù)匯聚梯度值可能會被反復(fù)刷新，梯度場建立過程收斂慢，穩(wěn)定性不好，建立的定向擴(kuò)散梯度場模型DDGF-SRG最終趨于與傳統(tǒng)定向擴(kuò)散梯度場DDGFMHR類似，且DDGF-SRG針對單一Sink節(jié)點(diǎn)設(shè)計(jì)，不利于車輛傳感器網(wǎng)絡(luò)的泛在互聯(lián)和信息在任意方向上的靈活傳送。

本文提出了一種基于位置和定向擴(kuò)散機(jī)制的泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)混合邏輯拓?fù)浣Y(jié)構(gòu)（hybrid logical topology based on location and directed diffusion mechanism，HLT-L&DD），以路邊節(jié)點(diǎn)為各局部分簇簇首，既符合車輛傳感器網(wǎng)絡(luò)的特點(diǎn)，也提高了邏輯拓?fù)浣Y(jié)構(gòu)建立的分布式程度，省去了簇首選擇所需的控制開銷；以定向擴(kuò)散機(jī)制對車輛節(jié)點(diǎn)進(jìn)行分簇和實(shí)現(xiàn)簇間互聯(lián)，既減小了邏輯拓?fù)浣Y(jié)構(gòu)建立的控制開銷，也保證了網(wǎng)絡(luò)節(jié)點(diǎn)的泛在順暢互聯(lián)。HLT-L&DD充分利用平面型邏輯拓?fù)浣Y(jié)構(gòu)和層次型邏輯拓?fù)浣Y(jié)構(gòu)的優(yōu)點(diǎn)，既便于車輛傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的泛在自組成網(wǎng)，也便于車輛傳感器網(wǎng)絡(luò)通過路邊節(jié)點(diǎn)與其他網(wǎng)絡(luò)的泛在互聯(lián)，有利于網(wǎng)絡(luò)實(shí)時性、連通性、可靠性、健壯性以及綜合性能的提高。

3　混合邏輯拓?fù)浣Y(jié)構(gòu)HLT-L&DD

車輛傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)分為車輛節(jié)點(diǎn)和路邊節(jié)點(diǎn)。車輛節(jié)點(diǎn)由各類交通運(yùn)輸車輛攜帶，具有高速可移動特性，能實(shí)現(xiàn)車輛傳感器網(wǎng)絡(luò)的泛在覆蓋、泛在感知以及泛在應(yīng)用的功能；路邊節(jié)點(diǎn)置于路邊基礎(chǔ)設(shè)施中，位置相對固定，一般具有豐富的聯(lián)網(wǎng)能力，可方便地與諸如Internet等其他網(wǎng)絡(luò)互聯(lián)互通，能勝任泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)數(shù)據(jù)的靈活收集和轉(zhuǎn)發(fā)。為保證泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)中數(shù)據(jù)傳送的健壯性、高效率和靈活性，HLT-L&DD采用如圖1所示的邏輯拓?fù)浣Y(jié)構(gòu)形式。

Fig.1　 Sketch map of HLT-L&DD圖1　 HLT-L&DD的結(jié)構(gòu)示意圖

HLT-L&DD是一種混合邏輯拓?fù)浣Y(jié)構(gòu)，車輛節(jié)點(diǎn)圍繞路邊節(jié)點(diǎn)就近分簇，形成局部分簇的邏輯拓?fù)浣Y(jié)構(gòu)，而各分簇內(nèi)部互聯(lián)以及簇間互聯(lián)是按定向擴(kuò)散機(jī)制形成的平面型邏輯拓?fù)浣Y(jié)構(gòu)。

3.1 HLT-L&DD的建立

在HLT-L&DD建立過程中，各路邊節(jié)點(diǎn)獨(dú)立啟動分簇進(jìn)程，以定向擴(kuò)散機(jī)制將距其跳數(shù)距離近的車輛節(jié)點(diǎn)逐跳收進(jìn)本簇?？紤]到路邊節(jié)點(diǎn)的位置易于獲得，且一般互不相同，HLT-L&DD中用路邊節(jié)點(diǎn)的位置信息作為其所在分簇的簇標(biāo)識ID；簇內(nèi)節(jié)點(diǎn)的互聯(lián)關(guān)系可由節(jié)點(diǎn)距所屬簇簇首的跳數(shù)距離標(biāo)識，簇間節(jié)點(diǎn)的互聯(lián)關(guān)系可由鄰簇簇標(biāo)識ID和距鄰簇簇首的跳數(shù)距離標(biāo)識。因此，在HLT-L&DD中，各節(jié)點(diǎn)存儲的標(biāo)識泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)邏輯拓?fù)浣Y(jié)構(gòu)的信息結(jié)構(gòu)為{簇標(biāo)識ID，簇內(nèi)跳數(shù)距離，（鄰簇1簇標(biāo)識ID，鄰簇1跳數(shù)距離），（鄰簇2簇標(biāo)識ID，鄰簇2跳數(shù)距離），…，}。為描述方便，給節(jié)點(diǎn)分配一個二維的標(biāo)識號(i,j)，節(jié)點(diǎn)(i,j)的拓?fù)浣Y(jié)構(gòu)信息用{HR(i,j),HD(i,j),(HNR1(i,j),HND1(i,j)),(HNR2(i,j),HND2(i,j)),…}表示。HLT-L&DD建立前，任意節(jié)點(diǎn)(i,j)的拓?fù)浣Y(jié)構(gòu)信息按下列原則初始化：如果(i,j)為路邊節(jié)點(diǎn)，HR(i,j)取其位置信息，HD(i,j ) =0，其他為空；如果(i,j)為車輛節(jié)點(diǎn)，HR(i,j )為空，HD(i,j ) =∞，其他為空。HLTL&DD的建立過程就是節(jié)點(diǎn)在路邊節(jié)點(diǎn)啟動的查詢分組的定向擴(kuò)散過程中獲取或更新拓?fù)浣Y(jié)構(gòu)信息值的過程。

3.1.1簇的建立

各路邊節(jié)點(diǎn)獨(dú)立地按定向擴(kuò)散機(jī)制發(fā)送查詢分組以啟動局部簇的建立，在查詢分組的逐跳發(fā)送或轉(zhuǎn)發(fā)過程中，車輛節(jié)點(diǎn)也逐跳地獲取或更新相應(yīng)的拓?fù)浣Y(jié)構(gòu)信息值從而加入相應(yīng)局部簇。在簇的建立過程中，查詢分組的發(fā)送或轉(zhuǎn)發(fā)以及節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)信息值的獲取或更新應(yīng)遵循以下規(guī)則。

（1）如果查詢分組發(fā)送節(jié)點(diǎn)(i,j)為路邊節(jié)點(diǎn)或車輛節(jié)點(diǎn)，接收節(jié)點(diǎn)(i′,j′)為車輛節(jié)點(diǎn)，且滿足式（1）中的條件，則節(jié)點(diǎn)(i′,j′)接收并轉(zhuǎn)發(fā)查詢分組，且按式（1）和式（2）自適應(yīng)更新其相應(yīng)的拓?fù)浣Y(jié)構(gòu)信息值加入該簇。

其中，d(i,j)(i′,j′)為節(jié)點(diǎn)(i′,j′)距節(jié)點(diǎn)(i,j)的幾何距離；R(i,j)為節(jié)點(diǎn)(i,j)的有效通訊半徑。

（2）如果查詢分組發(fā)送節(jié)點(diǎn)(i,j)為路邊節(jié)點(diǎn)或車輛節(jié)點(diǎn)，接收節(jié)點(diǎn)(i′,j′)為路邊節(jié)點(diǎn)，則路邊節(jié)點(diǎn)(i′,j′)不轉(zhuǎn)發(fā)查詢分組，也不加入該簇，只更新其簇間鏈接信息值（見3.1.3小節(jié)）。

3.1.2簇內(nèi)邏輯鏈路建立

HLT-L&DD中，每個局部簇包含一個路邊節(jié)點(diǎn)和若干個就近的車輛節(jié)點(diǎn)，簇內(nèi)任意節(jié)點(diǎn)間邏輯鏈路的存在與否由節(jié)點(diǎn)的簇標(biāo)識值HR和簇內(nèi)跳數(shù)距離值HD決定，節(jié)點(diǎn)(i,j)和節(jié)點(diǎn)(i′,j′)如果滿足式（3）中列出的條件，則其間存在簇內(nèi)邏輯鏈路。

3.1.3簇間邏輯鏈路建立

為便于泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的自組成網(wǎng)，增強(qiáng)數(shù)據(jù)傳送的實(shí)時性、健壯性和可靠性，網(wǎng)絡(luò)中各獨(dú)立分簇通過簇間邏輯鏈路實(shí)現(xiàn)簇間互聯(lián)。簇間邏輯鏈路的建立同樣在路邊節(jié)點(diǎn)以定向擴(kuò)散機(jī)制發(fā)送查詢分組以建立分簇的過程中實(shí)現(xiàn)，當(dāng)源自路邊節(jié)點(diǎn)的查詢分組定向擴(kuò)散至簇邊界且跨越簇邊界進(jìn)入某個鄰簇時，不同分簇內(nèi)的邊沿節(jié)點(diǎn)間建立起簇間邏輯鏈路，簇間邏輯鏈路的存在依靠節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)信息中保存的鄰簇標(biāo)識值HNR和鄰簇跳數(shù)距離值HND標(biāo)記。若節(jié)點(diǎn)(i,j)和(i′,j′)分別為查詢分組發(fā)送節(jié)點(diǎn)和查詢分組接收節(jié)點(diǎn)時，節(jié)點(diǎn)(i′,j′)遵循式（4）和式（5）的規(guī)則更新其鄰簇信息值，且不轉(zhuǎn)發(fā)查詢分組，不干擾鄰簇簇內(nèi)的邏輯鏈路狀態(tài)。

HLT-L&DD中，簇內(nèi)邊沿節(jié)點(diǎn)與鄰簇邊沿節(jié)點(diǎn)可能存在簇間邏輯鏈路，簇間邏輯鏈路的存在與否由節(jié)點(diǎn)的簇標(biāo)識值HR和簇跳數(shù)距離值HD以及鄰簇標(biāo)識值HNR和鄰簇跳數(shù)距離值HND決定，節(jié)點(diǎn)(i,j)和節(jié)點(diǎn)(i′,j′)如果滿足式（6）中列出的條件，則其間存在簇間邏輯鏈路。

3.2 HLT-L&DD動態(tài)更新

隨著車輛節(jié)點(diǎn)的移動，HLT-L&DD中的分簇可能被破壞，原有的簇內(nèi)邏輯鏈路或簇間邏輯鏈路可能因網(wǎng)絡(luò)物理拓?fù)浣Y(jié)構(gòu)的變化而斷裂。因?yàn)榉涸诨ヂ?lián)車輛傳感器網(wǎng)絡(luò)的物理拓?fù)浣Y(jié)構(gòu)頻繁變化，頻繁重建分簇和簇間互聯(lián)關(guān)系是不現(xiàn)實(shí)的，所以HLTL&DD采用了優(yōu)先實(shí)時動態(tài)更新的策略，僅在迫不得已時才由路邊節(jié)點(diǎn)啟動重建局部分簇。HLT-L&DD建立后，網(wǎng)絡(luò)中的數(shù)據(jù)匯聚便依據(jù)HLT-L&DD邏輯拓?fù)浣Y(jié)構(gòu)進(jìn)行，數(shù)據(jù)分組中攜帶節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)信息值以指導(dǎo)數(shù)據(jù)匯聚的路由，節(jié)點(diǎn)實(shí)時監(jiān)聽其鄰居節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)信息值并統(tǒng)計(jì)其鄰居節(jié)點(diǎn)的分布狀況，根據(jù)鄰居節(jié)點(diǎn)分布狀況進(jìn)行拓?fù)浣Y(jié)構(gòu)信息值的動態(tài)更新。HLT-L&DD的動態(tài)更新遵循下列規(guī)則。

（1）當(dāng)車輛節(jié)點(diǎn)(i′,j′)在其一跳范圍內(nèi)的鄰居節(jié)點(diǎn)(i,j)中沒有發(fā)現(xiàn)同簇鄰居節(jié)點(diǎn)時，車輛節(jié)點(diǎn)(i′,j′)按式（7）更新其簇標(biāo)識值HR(i′,j′)，按式（8）更新其簇跳數(shù)距離值HD(i′,j′)。

（2）當(dāng)車輛節(jié)點(diǎn)(i′,j′)在其一跳范圍內(nèi)監(jiān)測到同簇鄰居節(jié)點(diǎn)(i,j)，但不存在簇內(nèi)鏈路時，車輛節(jié)點(diǎn)(i′,j′)按式（9）更新其簇跳數(shù)距離值HD(i′,j′)。

（3）當(dāng)節(jié)點(diǎn)(i′,j′)監(jiān)測到在其一跳范圍內(nèi)有鄰簇鄰居節(jié)點(diǎn)時，節(jié)點(diǎn)(i′,j′)按式（10）更新其鄰簇簇標(biāo)識值HNR(i′,j′)，按式（11）更新其鄰簇簇跳數(shù)距離值HND(i′,j′)。

（4）其他情況下，節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)信息值暫不更新，等待網(wǎng)絡(luò)物理拓?fù)浣Y(jié)構(gòu)進(jìn)一步變化到一定狀態(tài)后根據(jù)新的鄰居節(jié)點(diǎn)統(tǒng)計(jì)信息進(jìn)行調(diào)整。

（5）當(dāng)路邊節(jié)點(diǎn)長期（時間閾值與網(wǎng)絡(luò)承載的具體業(yè)務(wù)類型有關(guān)，可由相應(yīng)業(yè)務(wù)管理實(shí)體通過消息傳送的方式設(shè)定）監(jiān)測不到一跳范圍內(nèi)有同簇鄰居節(jié)點(diǎn)時，該路邊節(jié)點(diǎn)啟動局部分簇重建過程，以定向擴(kuò)散機(jī)制重建其局部分簇。

3.3性能分析

針對泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)物理拓?fù)浣Y(jié)構(gòu)的特點(diǎn)，HLT-L&DD基于位置和定向擴(kuò)散機(jī)制構(gòu)建一種平面邏輯拓?fù)浣Y(jié)構(gòu)和分簇邏輯拓?fù)浣Y(jié)構(gòu)的混合邏輯拓?fù)浣Y(jié)構(gòu)，以期同時具備平面邏輯拓?fù)浣Y(jié)構(gòu)和分簇邏輯拓?fù)浣Y(jié)構(gòu)的優(yōu)點(diǎn)，并保證邏輯拓?fù)浣Y(jié)構(gòu)與物理拓?fù)浣Y(jié)構(gòu)的高度動態(tài)一致性，優(yōu)化網(wǎng)絡(luò)綜合性能。具體來說，HLT-L&DD在以下幾個方面改進(jìn)網(wǎng)絡(luò)邏輯拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)性能。

（1）HLT-L&DD中的分簇由路邊節(jié)點(diǎn)獨(dú)立發(fā)起構(gòu)建，車輛節(jié)點(diǎn)就近加入，并在定向擴(kuò)散機(jī)制下建立簇內(nèi)邏輯鏈路。路邊節(jié)點(diǎn)位置固定，能量充足，聯(lián)網(wǎng)能力豐富，以路邊節(jié)點(diǎn)為各局部分簇簇首獨(dú)立建立局部分簇，感知數(shù)據(jù)易于匯聚到路邊節(jié)點(diǎn)，便于路邊節(jié)點(diǎn)通過諸如Internet等其他網(wǎng)絡(luò)轉(zhuǎn)發(fā)數(shù)據(jù)，減輕車輛自組網(wǎng)的壓力，可優(yōu)化泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)的綜合性能。

（2）HLT-L&DD中的分簇間通過定向擴(kuò)散機(jī)制建立簇間邏輯鏈路，實(shí)現(xiàn)大規(guī)模車輛傳感器網(wǎng)絡(luò)自身的泛在互聯(lián)和順暢互聯(lián)，有效保證泛在感知數(shù)據(jù)傳送的健壯性和可靠性。

（3）HLT-L&DD通過路邊節(jié)點(diǎn)分布式建立分簇，實(shí)現(xiàn)對巨大規(guī)模車輛傳感器網(wǎng)絡(luò)的分區(qū)自治，便于邏輯拓?fù)浣Y(jié)構(gòu)的實(shí)時動態(tài)維護(hù)和擴(kuò)展，從而提高網(wǎng)絡(luò)的實(shí)時連通性和邏輯拓?fù)浣Y(jié)構(gòu)的穩(wěn)定周期。

（4）HLT-L&DD中的分簇以路邊節(jié)點(diǎn)為簇首，控制開銷低，且可充分利用路邊節(jié)點(diǎn)的豐富聯(lián)網(wǎng)能力，實(shí)時選用性能優(yōu)良的網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)分組轉(zhuǎn)發(fā)，從而提高數(shù)據(jù)傳送的效率和靈活性、健壯性。

（5）HLT-L&DD中，簇首位于局部分簇的中間位置，各簇成員距離簇首的跳數(shù)距離近，數(shù)據(jù)匯聚的實(shí)時性好，代價低。

4　仿真分析

仿真場景為169~324個節(jié)點(diǎn)按近似均勻分布模型隨機(jī)分布在500 m×500 m的平面矩形區(qū)域中，其中路邊節(jié)點(diǎn)個數(shù)為4~16個，網(wǎng)絡(luò)節(jié)點(diǎn)密度ξ為0.000 7~ 0.001 3個/m2，節(jié)點(diǎn)通信半徑R約為70 m。仿真目的為比較傳統(tǒng)最小跳數(shù)路由的定向擴(kuò)散梯度場DDGFMHR、可滑動定向擴(kuò)散梯度場DDGF-SRG與本文提出的基于位置和定向擴(kuò)散機(jī)制的混合邏輯拓?fù)浣Y(jié)構(gòu)HLT-L&DD的性能，通過比較建立邏輯拓?fù)浣Y(jié)構(gòu)時的定向擴(kuò)散跳數(shù)（可用來衡量邏輯拓?fù)浣Y(jié)構(gòu)建立時間）來評價邏輯拓?fù)浣Y(jié)構(gòu)建立和動態(tài)維護(hù)的實(shí)時性，通過比較實(shí)時斷鏈節(jié)點(diǎn)數(shù)來評價不同邏輯拓?fù)浣Y(jié)構(gòu)的實(shí)時連通性，并說明HLT-L&DD的優(yōu)越之處。主要仿真結(jié)果數(shù)據(jù)列于表1~表2，圖2~圖6為仿真結(jié)果圖。

Table 1　 Number of broken-chain nodes before and after adjusting logical topology表1　邏輯拓?fù)浣Y(jié)構(gòu)調(diào)整前后的斷鏈節(jié)點(diǎn)數(shù)

Table 2　 Hop number of directed diffusion in setting up logical topology表2　邏輯拓?fù)浣Y(jié)構(gòu)建立需要的定向擴(kuò)散跳數(shù)

圖2所示為HLT-L&DD中的分簇及簇內(nèi)邏輯鏈路情況，圖3所示為HLT-L&DD中的分簇及簇內(nèi)、簇間邏輯鏈路情況。從圖2和圖3中可見，HLT-L&DD由各路邊節(jié)點(diǎn)分布式建立，車輛節(jié)點(diǎn)以路邊節(jié)點(diǎn)為核心就近加入其分簇，相鄰分簇的邊沿節(jié)點(diǎn)間建立簇間邏輯鏈路。與DDGF-MHR相比，用分簇實(shí)現(xiàn)巨大規(guī)模車輛傳感器網(wǎng)絡(luò)的分區(qū)自治，網(wǎng)絡(luò)可擴(kuò)展性好，邏輯拓?fù)浣Y(jié)構(gòu)建立和動態(tài)維護(hù)的實(shí)時性好；與DDGF-SRG相比，任何路邊節(jié)點(diǎn)都可作為Sink節(jié)點(diǎn)，網(wǎng)絡(luò)數(shù)據(jù)可根據(jù)需要沿任意方向傳送，適應(yīng)巨大規(guī)模車輛傳感器網(wǎng)絡(luò)的泛在互聯(lián)和感知數(shù)據(jù)的靈活匯聚，邏輯拓?fù)浣Y(jié)構(gòu)的自適應(yīng)能力強(qiáng)。

圖4所示為當(dāng)車輛節(jié)點(diǎn)以不同速度隨機(jī)移動，各類邏輯拓?fù)浣Y(jié)構(gòu)不進(jìn)行動態(tài)調(diào)整時，DDGF-MHR、DDGF-SRG和HLT-L&DD中的斷鏈節(jié)點(diǎn)數(shù)情況。由圖4可見，當(dāng)車輛節(jié)點(diǎn)移動速度增加時，邏輯拓?fù)浣Y(jié)構(gòu)不調(diào)整時的斷鏈節(jié)點(diǎn)數(shù)均增加，但HLT-L&DD中的斷鏈節(jié)點(diǎn)數(shù)明顯是最小的。這是因?yàn)镠LT-L&DD是分簇的邏輯拓?fù)浣Y(jié)構(gòu)，且作為簇首的路邊節(jié)點(diǎn)一般位于分簇的中心，車輛節(jié)點(diǎn)移動對邏輯拓?fù)浣Y(jié)構(gòu)的影響被限制在局部區(qū)域內(nèi)。

圖5所示為當(dāng)車輛節(jié)點(diǎn)以不同速度隨機(jī)移動，各類邏輯拓?fù)浣Y(jié)構(gòu)進(jìn)行動態(tài)調(diào)整時，DDGF-MHR、DDGF-SRG和HLT-L&DD中的斷鏈節(jié)點(diǎn)數(shù)情況。由圖5可見，當(dāng)車輛節(jié)點(diǎn)移動速度增加時，邏輯拓?fù)浣Y(jié)構(gòu)動態(tài)調(diào)整時的斷鏈節(jié)點(diǎn)數(shù)均增加，但各自少于邏輯拓?fù)浣Y(jié)構(gòu)不進(jìn)行動態(tài)調(diào)整時的斷鏈節(jié)點(diǎn)數(shù)，且HLT-L&DD中的斷鏈節(jié)點(diǎn)數(shù)明顯是最少的?？梢?，邏輯拓?fù)浣Y(jié)構(gòu)進(jìn)行動態(tài)調(diào)整后，DDGF-SRG的實(shí)時連通性明顯優(yōu)于DDGF-MHR，而HLT-L&DD的實(shí)時連通性又優(yōu)于DDGF-SRG。這也是因?yàn)镠LT-L&DD是分簇的邏輯拓?fù)浣Y(jié)構(gòu)，且作為簇首的路邊節(jié)點(diǎn)一般位于分簇的中心，車輛節(jié)點(diǎn)移動對邏輯拓?fù)浣Y(jié)構(gòu)的影響被限制在局部區(qū)域，便于動態(tài)維護(hù)。

Fig.2　 Cluster and inner links in HLT-L&DD圖2　 HLT-L&DD中的分簇及簇內(nèi)邏輯鏈路

Fig.3　 Cluster and inner and inter links in HLT-L&DD圖3　 HLT-L&DD中的分簇及簇內(nèi)、簇間邏輯鏈路

Fig.4　 Number of broken-chain nodes before adjustinglogical topology圖4　邏輯拓?fù)浣Y(jié)構(gòu)不調(diào)整時的斷鏈節(jié)點(diǎn)數(shù)

Fig.5　 Number of broken-chain nodes after adjustinglogical topology圖5　邏輯拓?fù)浣Y(jié)構(gòu)進(jìn)行動態(tài)調(diào)整時的斷鏈節(jié)點(diǎn)數(shù)

Fig.6　 Hop number of directed diffusion in setting uplogical topology圖6　邏輯拓?fù)浣Y(jié)構(gòu)建立時的定向擴(kuò)散跳數(shù)

圖6所示為建立不同邏輯拓?fù)浣Y(jié)構(gòu)時需要的定向擴(kuò)散跳數(shù)情況，反映了邏輯拓?fù)浣Y(jié)構(gòu)建立和動態(tài)維護(hù)的實(shí)時性。由圖6可見，DDGF-MHR因是平面邏輯拓?fù)浣Y(jié)構(gòu)，其邏輯拓?fù)浣Y(jié)構(gòu)建立時查詢分組定向擴(kuò)散的跳數(shù)多，邏輯拓?fù)浣Y(jié)構(gòu)建立時間長，不適合大規(guī)模網(wǎng)絡(luò)。DDGF-SRG和HLT-L&DD因?qū)W(wǎng)絡(luò)實(shí)施了分簇，邏輯拓?fù)浣Y(jié)構(gòu)建立時間均比DDGF-MHR短。而且，因?yàn)镠LT-L&DD中分簇的簇首位于分簇的中心，而DDGF-SRG為達(dá)到向某個Sink節(jié)點(diǎn)匯聚數(shù)據(jù)時的路由優(yōu)化，路邊節(jié)點(diǎn)位于分簇的邊沿，所以對相同物理拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)，HLT-L&DD建立時需要的定向擴(kuò)散跳數(shù)更少，邏輯拓?fù)浣Y(jié)構(gòu)建立或動態(tài)維護(hù)需要的時間更短，實(shí)時性更好。

5　結(jié)束語

泛在互聯(lián)車輛傳感器網(wǎng)絡(luò)規(guī)模極其巨大，物理拓?fù)浣Y(jié)構(gòu)復(fù)雜且高度動態(tài)變化，網(wǎng)絡(luò)中數(shù)據(jù)的高效傳送十分重要，需要與動態(tài)物理拓?fù)浣Y(jié)構(gòu)自適應(yīng)的高效邏輯拓?fù)浣Y(jié)構(gòu)來支撐?；谖恢煤投ㄏ驍U(kuò)散機(jī)制的混合邏輯拓?fù)浣Y(jié)構(gòu)HLT-L&DD具有兩個顯著的優(yōu)點(diǎn)：一是由路邊節(jié)點(diǎn)分布式并行發(fā)起建立，提高了邏輯拓?fù)浣Y(jié)構(gòu)建立和動態(tài)更新的分布式程度，可以極大減小邏輯拓?fù)浣Y(jié)構(gòu)建立的時間開銷和控制開銷，增強(qiáng)邏輯拓?fù)浣Y(jié)構(gòu)動態(tài)更新的實(shí)時性。二是網(wǎng)絡(luò)節(jié)點(diǎn)具有簇標(biāo)識值和簇跳數(shù)距離兩個邏輯拓?fù)浣Y(jié)構(gòu)信息值，且路邊節(jié)點(diǎn)的簇標(biāo)識值固定，各車輛節(jié)點(diǎn)以就近的路邊節(jié)點(diǎn)為核心建立局部的數(shù)據(jù)匯聚分簇，可將巨大規(guī)模車輛傳感器網(wǎng)絡(luò)覆蓋區(qū)域按路邊節(jié)點(diǎn)“分區(qū)自治”，有利于局部區(qū)域的數(shù)據(jù)匯聚和邏輯拓?fù)浣Y(jié)構(gòu)的動態(tài)維護(hù)；且HLT-L&DD中各分簇通過簇邊沿節(jié)點(diǎn)互聯(lián)，簇內(nèi)數(shù)據(jù)既便于匯聚到路邊節(jié)點(diǎn)后由路邊節(jié)點(diǎn)經(jīng)其他泛在互聯(lián)網(wǎng)絡(luò)傳給用戶，也可經(jīng)簇間鏈路在自組織車輛傳感器網(wǎng)絡(luò)內(nèi)部匯聚到Sink節(jié)點(diǎn)，數(shù)據(jù)匯聚具有很高的健壯性和靈活性，可根據(jù)泛在互聯(lián)網(wǎng)絡(luò)實(shí)時狀況進(jìn)行網(wǎng)絡(luò)性能優(yōu)化。

References:

[1] Parvin S, Hussain F K, Park J S, et al. A survivability model in wireless sensor networks[J]. Computers & Mathematics with Applications, 2012, 64(12): 3666-3682.

[2] Atzori L, Iera A, Morabito G, et al. The social Internet of things (SIoT)—When social networks meet the Internet of things: concept, architecture and network characterization[J]. Computer Networks, 2012, 56(11): 3594-3608.

[3] International Telecommunication Union. Ubiquitous network societies: their impact on the telecommunication industry [EB/OL]. (2010-08-25)[2015-03-26]. http://www.itu.int/osg/ spu/ni/ubiquitous/Papers/UNSImpactPaper.pdf.

[4] Chen L-W, Peng Y-H, Tseng Y-C. An infrastructures framework for preventing rear-end collisions by vehicular sensor networks[J]. IEEE communications Letters, 2011, 15(3): 358-360.

[5] Zhang Xue, Lu Sanglu, Chen Guihai, et al. Topology control for wireless sensor networks[J]. Journal of Software, 2007, 18(4): 943-954.

[6] Han K-H, Ko Y-B, Kim J-H. A novel gradient approach for efficient data dissemination in wireless sensor networks[C]// Proceedings of the 2004 IEEE 60th Vehicular Technology Conference. Piscataway, USA: IEEE, 2004: 2979-2983.

[7] Li Yue, Sun Lijuan, Wang Ruchuan, et al. Improvement of LEACH algorithm in wireless sensor network[J]. Journal of Computer Research and Development, 2011, 48(S): 131-134.

[8] Huang Heqing, Shen Jie, Yao Daoyuan, et al. An energydriven adaptive cluster head rotation algorithm for wireless sensor networks[J]. Journal of Electronics & Information Technology, 2009, 31(5): 1040-1044.

[9] Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.

[10] Harri J, Filali F, Bonnet C. Mobility models for vehicular ad hoc networks: a survey and taxonomy[J]. IEEE Communications Surveys and Tutorials, 2009, 11(4): 19-41.

[11] Zhu Yanmin, Li MingLu, Ni Mingxuan. Research on vehicular sensor networks[J]. ZTE Communications, 2009, 15(5): 28-32.

[12] Zhang Wensheng, Cao Guohong, La Porta T. Data dissemination with ring-based index for wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2007, 6(7): 832-847.

[13] Zheng Mingcai, Zhang Dafang, Zhao Xiaochao. Dynamic adjusting policies on minimum hop gradient field in MHR wireless sensor networks[J]. Computer Engineering and Applications, 2011, 47(8): 83-86.

[14] Zheng Mingcai, Zhao Xiaochao, Zhao Jinqin, et al. Research on connectivity for vehicular sensor networks based on directed diffusion[J]. Application Research of Computers, 2012, 29 (1): 266-269.

附中文參考文獻(xiàn)：

[5]張學(xué),陸桑璐,陳貴海,等.無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂芠J].軟件學(xué)報, 2007, 18(4): 943-954.

[7]李悅,孫力娟,王汝傳.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)LEACH算法[J].計(jì)算機(jī)研究與發(fā)展, 2011, 48(S): 131-134.

[8]黃河清,沈杰,姚道遠(yuǎn),等.無線傳感網(wǎng)自適應(yīng)能量驅(qū)動簇頭輪換算法研究[J].電子與信息學(xué)報, 2009, 31(5): 1040-1044.

[11]朱燕民,李明祿,倪明選.車輛傳感器網(wǎng)絡(luò)研究[J].中興通訊技術(shù), 2009, 15(5): 28-32.

[13]鄭明才,張大方,趙小超. MHR無線傳感器網(wǎng)絡(luò)梯度場動態(tài)調(diào)整策略[J].計(jì)算機(jī)工程與應(yīng)用, 2011, 47(8): 83-86.

[14]鄭明才,趙小超,趙晉琴,等.基于定向擴(kuò)散的車輛傳感器網(wǎng)絡(luò)連通性研究[J].計(jì)算機(jī)應(yīng)用研究, 2012, 29(1): 266-269.

ZHENG Mingcai was born in 1969. He received the Ph.D. degree in computer science and technology from Hunan University in 2010. Now he is a professor at Hunan First Normal University. His research interests include wireless sensor networks and digital signal processing, etc.鄭明才（1969—），男，湖南津市人，2010年于湖南大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)獲得博士學(xué)位，現(xiàn)為湖南第一師范學(xué)院教授，主要研究領(lǐng)域?yàn)闊o線傳感器網(wǎng)絡(luò)，數(shù)字信號處理等。

ZHAO Xiaochao was born in 1971. She is an associate professor at Hunan First Normal University. Her research interests include applied mathematics and computer simulation, etc.趙小超（1971—），女，河南許昌人，湖南第一師范學(xué)院副教授，主要研究領(lǐng)域?yàn)閼?yīng)用數(shù)學(xué)，計(jì)算機(jī)仿真等。

ZHAO Jinqin was born in 1964. He is a professor at Hunan First Normal University. His research interests include computer network and digital signal processing, etc.趙晉琴（1964—），男，湖南邵陽人，湖南第一師范學(xué)院教授，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)，數(shù)字信號處理等。

Research on Hybrid Topology in Ubiquitous Interconnected Vehicular Sensor Networks?

ZHENG Mingcai1+, ZHAO Xiaochao2, ZHAO Jinqin1
1. College of Information Science and Engineering, Hunan First Normal University, Changsha 410205, China
2. College of Mathematics and Computational Science, Hunan First Normal University, Changsha 410205, China
+ Corresponding author: E-mail: dysfzmc@163.com

ZHENG Mingcai, ZHAO Xiaochao, ZHAO Jinqin. Research on hybrid topology in ubiquitous interconnected vehicular sensor networks. Journal of Frontiers of Computer Science and Technology, 2016, 10(3): 363-371.

Abstract:Aiming at the characteristics of ubiquitous interconnected vehicular sensor networks, this paper proposes a hybrid logical topology based on location and directed diffusion mechanism (HLT-L&DD), and gives the controlling method of HLT-L&DD. In the HLT-L&DD, the roadside-node is set as the local cluster head according to the requirement of tasks, and the location information of roadside-node is taken as the local cluster ID. The process of clustering is distributedly started with roadside-nodes according to the directed diffusion mechanism, and the vehicle-node joins into the corresponding local cluster hop by hop in the directed diffusion process of querying-packet, this leads to that several independent clusters are formed around the roadside-nodes respectively. Then, all independent clusters are interconnected into an entirety of logical topology by edge nodes in neighboring clusters, namely the HLTL&DD. The HLT-L&DD is a hybrid logical topology of the plane logical topology and the hierarchical logical topology, this is not only easy to self organize into an Ad hoc network and district autonomy, but also easy to ubiquitous
book=364,ebook=68interconnect with other traditional networks such as Internet through the roadside-node. Theoretical analysis and simulation results validate that the HLT-L&DD topology reduces the time consumption of setting up and dynamically maintaining the logical topology, and improves the real-time connectivity of the logical topology, so the comprehensive performance of the ubiquitous interconnected vehicular sensor network is improved.

Key words:vehicular sensor networks; ubiquitous interconnection; hybrid logical topology; directed diffusion; performance improvement

doi:10.3778/j.issn.1673-9418.1506031

文獻(xiàn)標(biāo)志碼：A

中圖分類號：TP393