馮學(xué)兵

（上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093）

0 引言

HART網(wǎng)絡(luò)是一種應(yīng)用于現(xiàn)場儀表與控制設(shè)備之間協(xié)議，為了支持無線的應(yīng)用HART7.0首次提出了Wireless HART標(biāo)準(zhǔn)。作為一種集中式控制網(wǎng)絡(luò)，網(wǎng)絡(luò)管理器利用設(shè)備和應(yīng)用程序提供的總體網(wǎng)絡(luò)路由信息，并結(jié)合通信需求實(shí)現(xiàn)對全網(wǎng)的調(diào)度和資源分配[1]。傳統(tǒng)的無線網(wǎng)絡(luò)由于其AP（Access Point）的覆蓋范圍限制往往需要多個(gè)網(wǎng)關(guān)協(xié)同工作以增加無線網(wǎng)絡(luò)的覆蓋區(qū)域。但Wireless HART好的解決了這一問題，一個(gè)Wireless HART的節(jié)點(diǎn)既可以充當(dāng)現(xiàn)場設(shè)備，也可以作為中間路由[2]。同時(shí)Wireless HART采用無線網(wǎng)絡(luò)跳頻技術(shù)來提高網(wǎng)絡(luò)的健壯性與吞吐量。

文章首先介紹Wireless HART網(wǎng)絡(luò)，提出網(wǎng)絡(luò)的數(shù)學(xué)模型，在此模型的基礎(chǔ)上研究如何對一個(gè)多信道的無線網(wǎng)絡(luò)的網(wǎng)絡(luò)負(fù)載進(jìn)行評(píng)估，并對負(fù)載不均衡的部分進(jìn)行算法調(diào)整以達(dá)到網(wǎng)絡(luò)負(fù)載均衡的狀態(tài)。

1 無線HART網(wǎng)絡(luò)

典型的Wireless HART網(wǎng)絡(luò)包括實(shí)現(xiàn)感知或執(zhí)行功能的現(xiàn)場設(shè)備、作為路由器提供服務(wù)的現(xiàn)場路由設(shè)備、將有線HART網(wǎng)絡(luò)鏈接到無線HART網(wǎng)絡(luò)的現(xiàn)場適配器、被用戶隨身攜帶的手持設(shè)備、鏈接現(xiàn)場設(shè)備到網(wǎng)關(guān)的接入點(diǎn)、作為上位機(jī)與無線網(wǎng)絡(luò)之間橋梁的網(wǎng)關(guān)、管理整個(gè)無線HART網(wǎng)絡(luò)的網(wǎng)絡(luò)管理器。

1.1 關(guān)于負(fù)載均衡的研究

無線網(wǎng)絡(luò)的度量一種用來描述無線網(wǎng)絡(luò)路由中一段鏈路性能、質(zhì)量合格與否的標(biāo)準(zhǔn)。故而一個(gè)合適的度量值可以準(zhǔn)確的反應(yīng)網(wǎng)絡(luò)的相關(guān)特性。無線網(wǎng)狀網(wǎng)鏈路衡量可以在路由的選擇中使用，作為選擇路由的衡量標(biāo)準(zhǔn)。

在無線mesh網(wǎng)絡(luò)的負(fù)載均衡的研究中，論文[4]提出了基于RSL或RSSI選取的最短路徑算法，論文[3]研究無線mesh網(wǎng)絡(luò)的負(fù)載均衡metric以及負(fù)載均衡metric的設(shè)計(jì)，提出了一種基于加權(quán)累積傳輸時(shí)間的路由度量，通過節(jié)點(diǎn)的業(yè)務(wù)集中度與信號(hào)與擁塞等級(jí)來衡量負(fù)載。論文[11-14]提出了網(wǎng)絡(luò)路徑規(guī)劃與提高網(wǎng)絡(luò)生命周期的研究。這部分論文主要是針對研究無線網(wǎng)絡(luò)組網(wǎng)協(xié)議的研究，對 Wireless HART網(wǎng)絡(luò)負(fù)載均衡metric與負(fù)載均衡算法的研究較為少見。

1.2 網(wǎng)絡(luò)模型建立

用V表示W(wǎng)ireless HART網(wǎng)絡(luò)中所有的網(wǎng)絡(luò)節(jié)點(diǎn),N表示網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)，以一個(gè)無線網(wǎng)絡(luò)管理器GW（Getaway）作為該局域網(wǎng)的根節(jié)點(diǎn)，同時(shí)設(shè)置每個(gè)GW的有效覆蓋范圍。

如圖1，Wireless HART網(wǎng)絡(luò)拓?fù)淇梢杂?G ( V, E)表示，其中V表示網(wǎng)絡(luò)中一系列的節(jié)點(diǎn)，E表示節(jié)點(diǎn)之間的連接情況。一條從 V1至 Vn的路由我們將其表示為 P (V1, Vn)[8]其中 P (V1,Vn) = ( V1, V2, V3……Vn)。

圖1 Wireless HART網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.1 Wireless HART topology structure

用一個(gè)nn×的對稱矩陣nnC×表示網(wǎng)絡(luò)節(jié)點(diǎn)之間的鏈接情況。

2 負(fù)載均衡算法

在通訊過程中Wireless HART的每個(gè)數(shù)據(jù)包大小與上位機(jī)所發(fā)命令號(hào)有關(guān)，相同的命令對應(yīng)的響應(yīng)數(shù)據(jù)包大小相等，令D表示某個(gè)命令所對應(yīng)的響應(yīng)數(shù)據(jù)包的大小，兩個(gè)節(jié)點(diǎn)mV，kV之間互為鄰居，則矩陣元素,mkc= 1。令iΩ表示所有在信道i上通訊的節(jié)點(diǎn)，則節(jié)點(diǎn)在 k時(shí)段內(nèi)信道 i上的負(fù)載可以表表示在 k時(shí)段內(nèi)節(jié)點(diǎn) n使用信道i下的負(fù)載。同時(shí)，對于網(wǎng)絡(luò)管理器的總負(fù)載可以表示為：

其中B為Wireless HART網(wǎng)絡(luò)的信道數(shù)。

圖2 Wireless HART通訊時(shí)隙Fig.2 Wireless HART communication time slot

研究網(wǎng)絡(luò)負(fù)載均衡時(shí)，從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑選取有多種方案，Wireless HART采用TDMA的傳輸方式來精確調(diào)度網(wǎng)絡(luò)中的通信[1]，通信的時(shí)間調(diào)度被分為多個(gè)時(shí)隙，m每個(gè)時(shí)隙完成數(shù)據(jù)的一次收發(fā)，時(shí)隙的通信過程如圖 2所示。在 Wireless HART網(wǎng)絡(luò)通信中，時(shí)隙規(guī)定了節(jié)點(diǎn)通信的過程，而多個(gè)時(shí)隙的組合構(gòu)成了網(wǎng)絡(luò)的超幀。由圖2可以看出，Wireless HART網(wǎng)絡(luò)通訊的過程是基于多次握手的通信傳輸，根據(jù)論文[7]網(wǎng)絡(luò)的傳輸成功率可以由前向遞交率 pf與反向遞交率 pr來計(jì)算，一次成功的傳輸概率為 p =1 - ( 1 - pf) (1 - pr)，因此在傳輸路由傳輸?shù)倪^程中路由跳數(shù)越多，網(wǎng)絡(luò)傳輸延時(shí)越大，數(shù)據(jù)丟包率越高。但單純的采用傳統(tǒng)的以“跳數(shù)”為判斷最佳路由的路由協(xié)議就有可能造成某個(gè)區(qū)域的節(jié)點(diǎn)負(fù)載失衡的現(xiàn)象。故而本文使用BFS算法作為搭建網(wǎng)絡(luò)框架的主要因素，并對組網(wǎng)后的網(wǎng)絡(luò)架構(gòu)進(jìn)行算法改進(jìn)，以達(dá)到負(fù)載均衡的狀態(tài)，同時(shí)也可以使用其他的算法替代BFS再使用本文提出的負(fù)載均衡因素與負(fù)載調(diào)整算法進(jìn)行改進(jìn)。

首先使用BFS對Wireless HART網(wǎng)絡(luò)的圖路由結(jié)構(gòu)進(jìn)行處理，BFS算法的遍歷樹具有其中任意節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑最短（跳數(shù)最少）的特點(diǎn)[9]，本文以網(wǎng)關(guān)接入點(diǎn)為根節(jié)點(diǎn)（即節(jié)點(diǎn) A），采用 BFS算法對網(wǎng)絡(luò)進(jìn)行遍歷，可以得到分層的網(wǎng)絡(luò)樹狀拓?fù)浣Y(jié)構(gòu)。

當(dāng)基礎(chǔ)算法產(chǎn)生了一個(gè)粗糙的負(fù)載均衡網(wǎng)絡(luò)拓?fù)鋾r(shí)，可以利用一個(gè)負(fù)載均衡的衡量因素對現(xiàn)有的網(wǎng)絡(luò)負(fù)載均衡進(jìn)行評(píng)估，并在此基礎(chǔ)上使用調(diào)節(jié)算法進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)的調(diào)整。在完全負(fù)載均衡的狀態(tài)下節(jié)點(diǎn)n的載Ln（k）可由公式2得出：

圖3 利用BFS算法分層后的結(jié)構(gòu)Fig.3 Topology after layered by BFS algorithm

λ根據(jù)算法 1得出，如果節(jié)點(diǎn)本身的負(fù)載Ln(k) ＞ Ln(k)則該節(jié)點(diǎn)視為過載，過載量為Δn=Ln(k ) - Ln(k)，此時(shí)其在BFS分層結(jié)構(gòu)中其同級(jí)節(jié)點(diǎn)必然有Ln(k) ＜ Ln(k)的節(jié)點(diǎn)存在。將節(jié)點(diǎn)n的負(fù)載均衡因素θn表示為公式3。

當(dāng)BFS分層樹的每個(gè)支樹趨于負(fù)載均衡時(shí)，負(fù)載均衡因素向1逼近。對于負(fù)載不均衡的節(jié)點(diǎn)采用算法2進(jìn)行調(diào)節(jié)。

迭代使用調(diào)節(jié)算法將負(fù)載最重的分支上的節(jié)點(diǎn)移動(dòng)到較輕的鄰近分支，首先找到根節(jié)點(diǎn)下負(fù)載最重的子節(jié)點(diǎn)，通過計(jì)算該節(jié)點(diǎn)與完全負(fù)載均衡情況下的節(jié)點(diǎn)負(fù)載之間的差值δ再尋找子節(jié)點(diǎn)中負(fù)載與δ相近的節(jié)點(diǎn)并將其與其他負(fù)載較輕的分支進(jìn)行連接，若沒有負(fù)載值與δ相近的節(jié)點(diǎn)，則每次移動(dòng)該分支中負(fù)載最輕的節(jié)點(diǎn)，并刷新負(fù)載均衡因子nθ。負(fù)載均衡因子在迭代的過程中應(yīng)呈上升的過程（向1逼近），以此作為迭代的判斷標(biāo)準(zhǔn)對Wireless HART網(wǎng)絡(luò)架構(gòu)進(jìn)行迭代調(diào)節(jié)。

3 實(shí)驗(yàn)與結(jié)果分析

使用matlab環(huán)境對本文提出的負(fù)載均衡算法進(jìn)行評(píng)估，以提出的θn作為評(píng)估的指標(biāo)。實(shí)驗(yàn)?zāi)M一定數(shù)量的節(jié)點(diǎn)并以1號(hào)節(jié)點(diǎn)作為網(wǎng)絡(luò)管理器，首先對BFS算法構(gòu)成的網(wǎng)絡(luò)進(jìn)行評(píng)估，并在新的實(shí)驗(yàn)中使用基于本文提出的新算法進(jìn)行實(shí)驗(yàn)，分別選取最優(yōu)表現(xiàn)與最差表現(xiàn)進(jìn)行觀察對比。

圖4和圖5評(píng)估了兩種算法在以負(fù)載平衡因素θn作為評(píng)估標(biāo)準(zhǔn)下的表現(xiàn)，分別選取最優(yōu)情況與最壞情況下的對比。圖4表明，即使在最壞的情況下，新算法對于網(wǎng)絡(luò)的負(fù)載均衡效果也遠(yuǎn)優(yōu)于基于 BFS選取的最短路徑算法。同時(shí)，本文提出的負(fù)載均衡因素與調(diào)節(jié)算法同樣可以用在其他無線網(wǎng)絡(luò)路由算法上以達(dá)到對算法優(yōu)化的目的。

4 結(jié)語

無線傳感網(wǎng)絡(luò)在工業(yè)上還有很大的應(yīng)用提升空間，作為第一個(gè)用于工業(yè)控制的無線網(wǎng)絡(luò)協(xié)議，Wireless HART網(wǎng)絡(luò)在實(shí)時(shí)性與可靠性方面有著嚴(yán)格的要求。在此本文提出一種基于BFS與負(fù)載均衡因素nθ的負(fù)載均衡優(yōu)化方法，在平衡了各個(gè)節(jié)點(diǎn)的負(fù)載的情況下提升了整個(gè)網(wǎng)絡(luò)的生命周期。有利于提高Wireless HART網(wǎng)絡(luò)的競爭力與應(yīng)用效果。

圖4 最優(yōu)表現(xiàn)Fig.4 Optimal performance

圖5 最差表現(xiàn)Fig.5 Worst performance

[1] (美)陳德基, (美)尼克松( Nixon, M), (美)(Mok, A)著, 王泉等譯. Wireless HART: 面向工業(yè)自動(dòng)化的實(shí)時(shí)網(wǎng)狀網(wǎng)絡(luò)[M]. 北京: 機(jī)械工業(yè)出版社, 2012.11.

[2] Jungmin So, Nitin H, Vaidya. Load-Balancing Routing in Multichannel Hybrid Wireless Networks With Single Network Interface. IEEE transactions on vehicular technology,vol.56, NO.1, January 2007.

[3] Sooyeol Yang, Jilong Li, Jangkyu Yun, Icksoo Lee and Kijun Han. A Routing Metric for Load Balance in Wireless Mesh Networks. 2008 IEEE DOI 10.1109/MMIT.2008.204.

[4] DANG Kui, SHEN Jizhong, DONG Lida. Shortest-path routing algorithm based on selec-ted RSL in WirelessHART.Computer Engineer-ing and Applications, 2012, 48(6): 69-72.

[5] Song Jianping, Han Song, Mok Aloysius K. Wireless HART:Applying Wireless Technology in Real-Time Industrial Process Control[C]//Proceedings of the on Real-Time and Embedded Tech-nology and Embedded Technology and Applications Symposium, St Louis, MO, April 22-24, 2008: 377-386.

[6] HART Communication Foundation. HCF_SPEC-085 Network Management Specification (Revision 1.1)[S]. 2008-05-30.

[7] HART Communication Foundation. Wireless Device Specification[S]. HCF_SPEC-290, Revision 1.1, USA, 2008.

[8] HE Pingshi, XU Ziping, YANG Xia. Research on algorithms of routing metric in multi-channel IEEE 802.11 WMN.

[9] Yaling Yang, Jun Wang. Design Guidelines for Routing Metric in Multihop Wireless Network. in IEEE INFOCOM, 2008.

[10] Zhao Jindong, Liang Zhenjun, Zhao Yaopei. ELHFR: a graph routing in industry wireless mesh network[C]//Proceedings of the Interna-tional Conference on Information and Automation(ICIA’2009), Zhuhai, China, June 22-25, 2009: 106-110.

[11] 馮偉, 別紅霞. 具有擁塞感知的Mesh負(fù)載均衡路由策略[J].軟件, 2013, 34(1): 56-59.

[12] 趙欣榮, 肖迎元, 王曉曄, 等. 無線傳感器網(wǎng)絡(luò)多路徑聚集的改進(jìn)[J]. 軟件, 2014, 35(7): 7-12.

[13] 周唯, 劉冬, 劉會(huì)師. 基于無線傳感器網(wǎng)絡(luò)拓?fù)涞难芯颗c設(shè)計(jì)[J]. 軟件, 2013, 34(12): 22-25.

[14] 呂占偉, 陶崢. 重傳下的無線傳感器網(wǎng)絡(luò)的生命周期分析[J]. 軟件, 2015, 36(1): 116-121.

[15] H. Dai and R. Han, “A node-centric load balancing algorithm for wireless sensor net-works,” in IEEE GLOBECOM Wireless Com-munication, 2003.

[16] A.Raniwala, K. Gopalan, and T. Chiueh, “Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks” ACM Mobile Comput. Commun.Rev. (MC2R), vol.8, no.2, pp.50-65, Apr.2004.