面向BLE健康監(jiān)護網(wǎng)絡(luò)的負載均衡算法

李 銳，李曉卉，李小鈺，丁月民，朱時暉

(1.武漢科技大學(xué) 信息科學(xué)與工程學(xué)院，湖北 武漢 430081；2.華中科技大學(xué)同濟醫(yī)學(xué)院 同濟醫(yī)院，湖北 武漢 430030；3.天津理工大學(xué) 計算機科學(xué)與工程學(xué)院，天津 300384；4.建榮半導(dǎo)體(深圳)有限公司 工程部，廣東 深圳 518051)

0 引 言

BLE Mesh[1]技術(shù)的誕生解決了傳統(tǒng)藍牙傳輸距離過短的瓶頸[2]，因此這項技術(shù)應(yīng)用越來越廣泛[3-5]。然而，目前學(xué)術(shù)上對BLE Mesh網(wǎng)絡(luò)協(xié)議研究偏少，常用的幾種協(xié)議不能滿足市場上各種應(yīng)用的需求。在本文研究的面向BLE Mesh的健康監(jiān)護網(wǎng)絡(luò)中，一方面網(wǎng)絡(luò)中有部分節(jié)點時常處于移動狀態(tài)；另一方面現(xiàn)有BLE Mesh路由協(xié)議未考慮負載均衡導(dǎo)致部分節(jié)點能量消耗過快。因此，現(xiàn)有協(xié)議難以滿足以保證服務(wù)質(zhì)量為首要目標的數(shù)據(jù)傳輸需求，這就很容易導(dǎo)致監(jiān)護信息無法及時有效地送達，從而造成安全隱患。

目前常用的BLE Mesh算法中，CSR Mesh算法的優(yōu)點是簡單可靠，但其在路由過程中，具有資源占用大、節(jié)點消耗能量快等劣勢，并且當(dāng)節(jié)點經(jīng)常處于移動的狀態(tài)下，容易產(chǎn)生斷鏈，需要重新發(fā)現(xiàn)路由，導(dǎo)致數(shù)據(jù)無法穩(wěn)定傳輸[6]；而機會路由算法應(yīng)用在本網(wǎng)絡(luò)中由于移動節(jié)點的存在，導(dǎo)致最優(yōu)節(jié)點的選擇有著很大的不確定性，且最優(yōu)節(jié)點一旦確定，單一的路由路徑就被確定，易出現(xiàn)繞遠路情況，同樣無法保證能耗最優(yōu)[7]。部分學(xué)者采用AOMDV算法進行路由，由于備用路由的存在，其在一定程度上可以增加網(wǎng)絡(luò)的穩(wěn)定性和容錯能力，并相對平衡了各節(jié)點能量消耗。然而AODMV采用單一的跳數(shù)作為路由判據(jù)，并未考慮節(jié)點移動和剩余能量等因素，故選擇的路由往往也不一定是最佳路由[8]。而一些考慮剩余能量的協(xié)議，如文獻[9]將剩余能量運用到機會路由協(xié)議中，文獻[10]通過設(shè)置能量閾值來選擇代理父節(jié)點，從而選擇最佳路由。這些協(xié)議對節(jié)點的剩余能量劃分過于絕對，沒有動態(tài)地考慮節(jié)點能量，故無法保證達到負載均衡。

綜合來看，在現(xiàn)有的路由協(xié)議的設(shè)計中，所考慮的路由指標往往是固定不變的。而在實際應(yīng)用中，隨著節(jié)點位置和剩余能量等的動態(tài)變化，路徑的選擇同樣要隨著變化做動態(tài)調(diào)整。如何通過網(wǎng)絡(luò)的動態(tài)變化設(shè)計出動態(tài)的鏈路指標，再借助動態(tài)鏈路指標指導(dǎo)路由建立則是一種新的路由算法設(shè)計思路。鑒于以上設(shè)計思路，本文提出一種負載均衡多徑路由算法(load-balancing ad-hoc on-demand multipath distance vector routing，L-AOMDV)，其在AOMDV的基礎(chǔ)上，一方面考慮了監(jiān)護網(wǎng)絡(luò)中移動節(jié)點的移動特性，另一方面考慮了路由節(jié)點的動態(tài)剩余能量，最終通過引入負載均衡鏈路狀態(tài)指標(load-balancing link quality indicator，LLQI)指導(dǎo)路由建立。

1 網(wǎng)絡(luò)結(jié)構(gòu)和相關(guān)模型構(gòu)建

本節(jié)主要介紹網(wǎng)絡(luò)的結(jié)構(gòu)和動態(tài)剩余能量計算模型與節(jié)點移動狀態(tài)概率計算模型的詳細設(shè)計。

1.1 網(wǎng)絡(luò)結(jié)構(gòu)

傳統(tǒng)的BLE Mesh網(wǎng)絡(luò)中，各節(jié)點都具有路由功能，但未對節(jié)點的功能進行劃分，導(dǎo)致節(jié)點在健康監(jiān)護的實際應(yīng)用時，功耗過大。為了進一步優(yōu)化BLE Mesh健康監(jiān)護網(wǎng)絡(luò)節(jié)點功耗[11,12]，本文采用一種新的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，該結(jié)構(gòu)將BLE Mesh節(jié)點分為3類：固定終端節(jié)點、固定路由節(jié)點和可移動節(jié)點。

其中固定終端節(jié)點采用低功耗廣播(low power advertisement，ADV LOW)廣播自身設(shè)備信息，其僅定期采集傳感器信息,然后將信息發(fā)送至其它固定路由節(jié)點，或獲取固定路由節(jié)點的控制信息；固定路由節(jié)點具備固定終端節(jié)點的功能，同時其可利用廣播中繼(advertisement relay，ADV RELAY)接收和中繼其它節(jié)點的信息，起路由功能；而可移動節(jié)點具備固定路由節(jié)點的全部功能，屬于全功能節(jié)點，其具有一定的運算能力并可根據(jù)藍牙信標獲取自身位置[13]，另外其采用標準低功耗藍牙的關(guān)貿(mào)總協(xié)定(general agreement on tariffs and trade，GATT)與手機通信。

整個網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖1所示。

圖1 網(wǎng)絡(luò)拓撲結(jié)構(gòu)

1.2 動態(tài)剩余能量計算模型

如果簡單地以當(dāng)前節(jié)點的剩余能量作為影響路由判據(jù)的相關(guān)因子，則可能不能設(shè)計出最佳判據(jù)，因為這種策略忽略了能量消耗的速度，例如某個路由節(jié)點當(dāng)前剩余能量較多，然而其能量消耗速度過快，在選擇路徑時也應(yīng)降低此節(jié)點的選擇權(quán)重。為了動態(tài)獲得節(jié)點的剩余能量，可通過構(gòu)建模型滾動預(yù)測未來時間段節(jié)點的剩余能量，再通過未來節(jié)點剩余能量的多少來設(shè)計路由判據(jù)影響因子。由于預(yù)測僅參考過去剩余能量這一個指標，預(yù)測模型必須簡單、精度相對較高，且計算難度不能過大，因此本文采用灰色一階一元預(yù)測模型GM(1,1) 來預(yù)測節(jié)點的剩余能量[14]，灰色預(yù)測模型具有樣本數(shù)量要求低、算法相對簡便、短期預(yù)測精度高等優(yōu)點，因此比較適合在本系統(tǒng)中預(yù)測未來各節(jié)點的剩余能量[15]，預(yù)測步驟如下：

每隔固定時間t，記錄固定路由節(jié)點的剩余能量，持續(xù)記錄的總時間為T=nt，記錄完畢，將數(shù)據(jù)傳輸給全功能節(jié)點進行處理，即得到滾動的固定路由節(jié)點的剩余能量時間序列為

x=(x(1),x(2),…,x(n))

(1)

式中：x(n) 表示在n時刻固定路由節(jié)點的剩余能量值。

對剩余能量序列按照式(2)進行累加

(2)

得到累加的剩余能量序列

X=(X(1),X(2),…,X(n))

(3)

對X建立灰色模型的一次微分方程，其方程如式(4)所示

(4)

(5)

式中：Yn和B的計算分別如下

(6)

(7)

(8)

1.3 節(jié)點移動狀態(tài)概率計算模型

由于被監(jiān)護者為可移動節(jié)點，根據(jù)被監(jiān)護者的特征，即其不是隨機的在網(wǎng)絡(luò)的各個區(qū)域移動，而是其有很大概率會在某些固定區(qū)域之間移動，故可構(gòu)建一種簡單的模型計算出移動節(jié)點處于各個區(qū)域的概率，得到概率之后，在設(shè)計路由判據(jù)時將區(qū)域概率因素考慮進來，則設(shè)計的鏈路更偏向于選擇移動節(jié)點出現(xiàn)頻率高的區(qū)域中的路由節(jié)點。下面是構(gòu)建該模型的方法：

在布置固定路由節(jié)點之后，根據(jù)節(jié)點平面分布，先記錄下固定路由節(jié)點的位置信息，然后根據(jù)布點情況將整個區(qū)域平均劃分為多個，如圖2所示分布，可將整個網(wǎng)絡(luò)劃分為9個區(qū)域，設(shè)區(qū)域序列Z=(Z1,Z2,…,Z9)， 則Z1至Z9表示這9個區(qū)域。為了獲取可移動節(jié)點的位置情況，需要在應(yīng)用區(qū)域四周布置數(shù)個藍牙信標，通過信標即可隨時記錄可移動節(jié)點的位置情況。

圖2 節(jié)點劃分區(qū)域

由于移動節(jié)點可通過藍牙信標得到當(dāng)前的位置，故每隔固定時間t，記錄移動節(jié)點的區(qū)域位置，持續(xù)滾動記錄的總時間為T=nt，記錄完畢，可得到T時間段內(nèi)移動節(jié)點處于各區(qū)域的序列為

(9)

式中：序列D即表示移動節(jié)點在T時間內(nèi)依次處于各區(qū)域的情況。由式(10)可統(tǒng)計出T時間內(nèi)移動節(jié)點處于各個區(qū)域的概率Ni為

(10)

2 L-AOMDV路由算法

L-AOMDV算法考慮了節(jié)點的動態(tài)剩余能量和移動特性，即在構(gòu)建鏈路時優(yōu)先考慮動態(tài)剩余能量大的路由節(jié)點和移動節(jié)點出現(xiàn)頻率高的區(qū)域內(nèi)的固定路由節(jié)點，上一節(jié)介紹了如何通過兩個模型計算得到節(jié)點的動態(tài)剩余能量和移動節(jié)點的區(qū)域概率，本節(jié)詳細介紹利用這兩個指標設(shè)計出新的路由判據(jù)——負載均衡鏈路狀態(tài)指標，并介紹整個算法流程。

2.1 負載均衡鏈路狀態(tài)指標

首先需要考慮鏈路的質(zhì)量因素。對于確定的網(wǎng)絡(luò)設(shè)備，一般有著固定范圍的鏈路質(zhì)量值LQI，且一般由MAC層計算得到。設(shè)LQImax和LQImin為LQI的上下限，對于相鄰兩個節(jié)點間鏈路質(zhì)量的權(quán)值標準化由式(11)表示

(11)

式中：YLQIab為節(jié)點a到節(jié)點b的歸一化鏈路質(zhì)量指標。

其次考慮路由節(jié)點的動態(tài)剩余能量對網(wǎng)絡(luò)的影響，未來時間段剩余能量高的固定路由節(jié)點影響整個鏈路質(zhì)量的權(quán)重會高于剩余能量低的節(jié)點。設(shè)Emax為初始的節(jié)點最大能量，定義Ej為固定路由節(jié)點能量指標系數(shù)，則

(12)

接下來考慮網(wǎng)絡(luò)中的移動節(jié)點對網(wǎng)絡(luò)的影響，由于移動節(jié)點處在各區(qū)域的概率不同，故各Zi區(qū)域內(nèi)的固定路由節(jié)點影響整個鏈路質(zhì)量的權(quán)重不同。定義Ti為處于Zi區(qū)域的固定路由節(jié)點狀態(tài)指標系數(shù)，則

(13)

式中:Ni為上一節(jié)得到的固定路由節(jié)點區(qū)域概率，λ為調(diào)節(jié)因子，調(diào)節(jié)狀態(tài)指標系數(shù)的大小，其值越大則狀態(tài)指標系數(shù)數(shù)值越小，狀態(tài)指標系數(shù)值越小則移動狀態(tài)對整個鏈路指標的影響度也就越小。

結(jié)合式(12)和式(13)可得到節(jié)點a與節(jié)點b之間的負載均衡鏈路狀態(tài)指標系數(shù)Rab

Rab=TiaTibEaEb

(14)

式中：Tia為節(jié)點a對應(yīng)的狀態(tài)指標系數(shù)值，例如節(jié)點a處于Z2區(qū)域，則Tia=T2，同理Tib為節(jié)點b對應(yīng)的狀態(tài)指標系數(shù)值，Ea和Eb分別為節(jié)點a和節(jié)點b的能量指標系數(shù)值。

再根據(jù)式(15)可得到兩個節(jié)點之間的負載均衡鏈路狀態(tài)指標LLQIab

LLQIab=RabYLQIab

(15)

LLQIab數(shù)值越高表明兩節(jié)點間鏈路質(zhì)量和能量均衡性能越好。

最后計算整條鏈路的負載均衡鏈路狀態(tài)指標，對于從源節(jié)點到目的節(jié)點的完整鏈路，其負載均衡鏈路狀態(tài)指標計算如式(16)表示

(16)

LLQIpath即為整個路徑的負載均衡鏈路狀態(tài)指標，數(shù)值越大表示整條鏈路的通信性能和負載均衡度越好。

2.2 算法流程圖

L-AOMDV算法的流程如圖3所示。

圖3 L-AOMDV算法流程

整個路由算法分為路由發(fā)現(xiàn)、路由維護和路由更新3個部分。

整個算法在路由發(fā)現(xiàn)階段查找出所有可能的節(jié)點不相交多路徑；由于在路由請求和應(yīng)答報文中包含負載均衡鏈路狀態(tài)指標，因此可以計算得到各條路徑的負載均衡鏈路狀態(tài)指標；在選擇路徑時選擇指標最大的作為主路徑，并預(yù)留兩條備用路徑。在普通模式下采用主路由進行通信，若監(jiān)護人健康出現(xiàn)異常，則系統(tǒng)進入緊急模式，此時系統(tǒng)同時采用主路徑和備用路徑傳輸數(shù)據(jù)，以保證網(wǎng)絡(luò)的穩(wěn)定性和可靠性。

當(dāng)路徑建立后，系統(tǒng)進入路由維護狀態(tài)，在此期間，目的節(jié)點定期向源節(jié)點發(fā)送維護消息，維護信息中包含節(jié)點的剩余能量信息和移動節(jié)點的位置信息，在這一過程中系統(tǒng)會時刻檢測維護消息中的LLQI值。

若檢測的LLQI值出現(xiàn)異常，系統(tǒng)進入路由更新狀態(tài)：當(dāng)?shù)谝淮螜z測到LLQI值降低到預(yù)警值的時候，開始進行備用路由更新，源節(jié)點發(fā)送更新信息沿每一條備用路徑到達目的節(jié)點，并且重新計算鏈路的LLQI值，當(dāng)源節(jié)點第二次檢測到鏈路狀態(tài)降低到預(yù)警值的時候，開始切換備用路徑，在備用路徑選擇鏈路狀態(tài)最好的路由進行通信，并且將原路徑從路由表中刪除，當(dāng)所有備用路徑都失效時，重新進行路由發(fā)現(xiàn)。

3 仿真與結(jié)果

為評估L-AOMDV在BLE Mesh健康監(jiān)測網(wǎng)絡(luò)中的有效性，本文在MATLAB上開發(fā)了L-AOMDV算法，并和CSR Mesh路由算法與AOMDV算法進行仿真對比。

3.1 仿真參數(shù)設(shè)置

仿真的社區(qū)健康監(jiān)護BLE Mesh網(wǎng)絡(luò)的區(qū)域為30*30 m2的區(qū)域。考慮到現(xiàn)實中場景布點數(shù)量的不同，本次仿真分別采用10個至40個節(jié)點對其進行模擬，其中包含較少量的移動節(jié)點，整個節(jié)點區(qū)域共劃分為9個，固定節(jié)點隨機分散在這9個區(qū)域之中，移動節(jié)點按照一定軌跡在3個-7個區(qū)域內(nèi)移動，獲取位置間隔時間t設(shè)為20 min，記錄總時間設(shè)為9t。在相同條件下，經(jīng)仿真測得，調(diào)節(jié)因子λ數(shù)值在1.3-1.7之間具有較好的實驗效果，若調(diào)節(jié)因子λ過低則路由開銷過大且分組投遞率并沒有明顯提升；若調(diào)節(jié)因子λ過高，則移動狀態(tài)概率計算對提升網(wǎng)絡(luò)性能沒有起到積極的效果，本次仿真中調(diào)節(jié)因子λ取1.5。確定調(diào)節(jié)因子λ之后，繼續(xù)在相同條件下求得調(diào)節(jié)因子σ的最優(yōu)值，經(jīng)仿真測得調(diào)節(jié)因子σ數(shù)值在2.5-3.4之間時，路由開銷總體增加不多，卻可有效延長網(wǎng)絡(luò)的生命周期，在本次仿真中調(diào)節(jié)因子σ取3.1。在不考慮緊急模式的情況下，具體的仿真參數(shù)見表1。

表1 仿真場景參數(shù)

3.2 仿真性能指標

為了更好地評估各種算法在健康監(jiān)護網(wǎng)絡(luò)中的性能差異，本文以分組投遞率作為算法性能評估的基礎(chǔ)指標。分組投遞率可用于表征數(shù)據(jù)包投遞成功的概率，若此數(shù)值過低，則表明算法性能較低，不適合采用。

在保證有較高的分組投遞率的前提下，再選擇平均節(jié)點死亡個數(shù)作為負載均衡性能的評估指標，若算法的負載均衡性能越好，則平均節(jié)點死亡個數(shù)的值越低。

另外，為了綜合地了解算法的其它性能，例如數(shù)據(jù)包投遞過程中所用時間與網(wǎng)絡(luò)的復(fù)雜度等，本文選擇平均路由跳數(shù)作為算法性能評估的輔助指標，借助此指標可以更全面地了解算法的性能。

3.3 仿真結(jié)果分析

3種算法的分組投遞率仿真結(jié)果如圖4所示。隨著節(jié)點數(shù)量的增加，3種路由算法的分組投遞率均隨之上升。由圖可知，L-AOMDV有更高的分組投遞率，其原因在于一方面L-AOMDV能通過LLQI值，優(yōu)先向移動節(jié)點出現(xiàn)頻率高的區(qū)域內(nèi)的固定路由節(jié)點建鏈，以此保證在移動節(jié)點移動過程中的通信順暢；另一方面L-AOMDV考慮了節(jié)點的未來剩余能量，這一定程度避免了部分節(jié)點過早死亡對網(wǎng)絡(luò)的影響。而AOMDV僅根據(jù)網(wǎng)絡(luò)初始狀態(tài)下的路由發(fā)現(xiàn)跳數(shù)建立路由表，無法保證在移動節(jié)點移動過程中的鏈路穩(wěn)定性。CSR Mesh由于每次僅能建立一條鏈路，在移動節(jié)點移動的情況下無法保障該鏈路的有效性。

圖4 分組投遞率仿真結(jié)果

當(dāng)節(jié)點設(shè)置為40個節(jié)點，所有的節(jié)點初始能量設(shè)置為2 J時，3種路由算法的平均節(jié)點死亡個數(shù)情況如圖5所示。由圖可知，隨著時間的增加，L-AOMDV算法中的節(jié)點死亡速率遠低于另外兩種路由算法，且在路由開始運行的50 min內(nèi)，L-AOMDV算法中無節(jié)點死亡。這表示在各節(jié)點均有相同的能量下，L-AOMDV算法能夠延遲第一個節(jié)點的死亡時間；在相同時間段內(nèi)，采用L-AOMDV算法的網(wǎng)絡(luò)中死亡的節(jié)點數(shù)目最少。在現(xiàn)實中，則表示不會出現(xiàn)某個健康監(jiān)護節(jié)點過早死亡從而導(dǎo)致某項數(shù)據(jù)遺失的情況，也意味著不需要頻繁地給某些節(jié)點補充能量。出現(xiàn)以上結(jié)果是因為L-AOMDV盡可能優(yōu)先選擇能量相對較高的節(jié)點進行通信，也盡可能優(yōu)先選擇移動節(jié)點出現(xiàn)頻率高的區(qū)域內(nèi)的固定路由節(jié)點進行通信，這相當(dāng)于負載均衡地分擔(dān)給了整個網(wǎng)絡(luò)，另外由于節(jié)點死亡速率變慢，也相當(dāng)于延長了整個網(wǎng)絡(luò)的生命周期。

圖5 平均節(jié)點死亡個數(shù)對比

路由跳數(shù)仿真結(jié)果如圖6所示，隨著節(jié)點數(shù)量的增加，3種路由算法的平均路由跳數(shù)均隨之上升。L-AOMDV所耗路由跳數(shù)高于AOMDV與CSR Mesh，這是因為AOMDV 與CSR Mesh會優(yōu)先選擇路由跳數(shù)最短的路徑進行路由，而L-AOMDV會考慮移動節(jié)點的位置和節(jié)點的未來剩余能量。L-AOMDV較之AOMDV與CSR Mesh而言，路由跳數(shù)增加，網(wǎng)絡(luò)的開銷和復(fù)雜度會相應(yīng)有所增加。對于復(fù)雜度，由于健康信息的數(shù)據(jù)量相對較少且設(shè)定的發(fā)送間隔周期較長，從仿真結(jié)果來看，分組投遞率的顯著提高表明復(fù)雜度的提高對本應(yīng)用影響不大。對于網(wǎng)絡(luò)整體開銷的增加，由于健康監(jiān)護系統(tǒng)對數(shù)據(jù)傳輸穩(wěn)定性和有效性要求較高，因此以一定的開銷換取更長的網(wǎng)絡(luò)生命周期是可以接受的。

圖6 平均路由跳數(shù)仿真結(jié)果

圖7為一段時間內(nèi)源節(jié)點與目的節(jié)點通信過程中生成的3條路徑的LLQI值展示情況。在通信伊始，由于路徑1的LLQI值最高，故選取路徑1作為主路由通信。隨著網(wǎng)絡(luò)復(fù)雜度的增加以及部分節(jié)點能量的減少，各路徑的LLQI值均有所下降。在運行過程中，當(dāng)路徑1的LLQI值低于設(shè)定的閥值，而路徑2的LLQI值相對較高時，則表明路徑2的通信性能更佳，此時開始切換備用路徑，選擇路徑2作為主路由通信。通過以上備用路由的切換過程也進一步表明了L-AOMDV算法所采用策略的有效性。

圖7 L-AOMDV算法中多路徑LLQI值

綜上所述，在存在移動節(jié)點的BLE Mesh健康監(jiān)護網(wǎng)絡(luò)中，L-AOMDV算法在性能上較AOMDV與CSR Mesh算法存在一定優(yōu)勢，其一方面保證了數(shù)據(jù)投遞的成功率，另一方面又延長了網(wǎng)絡(luò)的生命周期，有效增強了網(wǎng)絡(luò)性能。雖然L-AOMDV算法在路由開銷方面會略高，但是在對穩(wěn)定性和有效性要求更高的健康監(jiān)護網(wǎng)絡(luò)下，L-AOMDV算法更能夠滿足健康監(jiān)護網(wǎng)絡(luò)的需求。

4 結(jié)束語

針對健康監(jiān)護系統(tǒng)中存在可移動節(jié)點和傳統(tǒng)算法未考慮負載均衡因素造成BLE Mesh網(wǎng)絡(luò)數(shù)據(jù)傳輸不穩(wěn)定的問題，本文提出了一種負載均衡多徑路由算法——L-AOMDV，在算法中綜合考慮了節(jié)點的移動特性和未來剩余能量并引入更加有效的負載均衡鏈路狀態(tài)指標——LLQI來指導(dǎo)建立鏈路，同時在路由維護中通過及時更新LLQI的值來選取最佳備用鏈路；另外系統(tǒng)還優(yōu)化了BLE Mesh網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和設(shè)立了緊急模式來進一步提升網(wǎng)絡(luò)的可靠性。仿真結(jié)果表明，L-AOMDV算法比傳統(tǒng)的CSR Mesh算法和AOMDV算法有更高的投遞率和更長的網(wǎng)絡(luò)生命周期，因此在家庭社區(qū)健康監(jiān)護系統(tǒng)中，其更能夠保證數(shù)據(jù)傳輸?shù)姆€(wěn)定性和有效性。