面向BLE健康監護網絡的負載均衡算法

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

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

0 引 言

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

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

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

1 網絡結構和相關模型構建

本節主要介紹網絡的結構和動態剩余能量計算模型與節點移動狀態概率計算模型的詳細設計。

1.1 網絡結構

傳統的BLE Mesh網絡中，各節點都具有路由功能，但未對節點的功能進行劃分，導致節點在健康監護的實際應用時，功耗過大。為了進一步優化BLE Mesh健康監護網絡節點功耗[11,12]，本文采用一種新的網絡拓撲結構，該結構將BLE Mesh節點分為3類：固定終端節點、固定路由節點和可移動節點。

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

整個網絡拓撲結構如圖1所示。

圖1 網絡拓撲結構

1.2 動態剩余能量計算模型

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

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

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

(1)

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

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

(2)

得到累加的剩余能量序列

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

(3)

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

(4)

(5)

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

(6)

(7)

(8)

1.3 節點移動狀態概率計算模型

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

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

圖2 節點劃分區域

由于移動節點可通過藍牙信標得到當前的位置，故每隔固定時間t，記錄移動節點的區域位置，持續滾動記錄的總時間為T=nt，記錄完畢，可得到T時間段內移動節點處于各區域的序列為

(9)

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

(10)

2 L-AOMDV路由算法

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

2.1 負載均衡鏈路狀態指標

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

(11)

式中：YLQIab為節點a到節點b的歸一化鏈路質量指標。

其次考慮路由節點的動態剩余能量對網絡的影響，未來時間段剩余能量高的固定路由節點影響整個鏈路質量的權重會高于剩余能量低的節點。設Emax為初始的節點最大能量，定義Ej為固定路由節點能量指標系數，則

(12)

接下來考慮網絡中的移動節點對網絡的影響，由于移動節點處在各區域的概率不同，故各Zi區域內的固定路由節點影響整個鏈路質量的權重不同。定義Ti為處于Zi區域的固定路由節點狀態指標系數，則

(13)

式中:Ni為上一節得到的固定路由節點區域概率，λ為調節因子，調節狀態指標系數的大小，其值越大則狀態指標系數數值越小，狀態指標系數值越小則移動狀態對整個鏈路指標的影響度也就越小。

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

Rab=TiaTibEaEb

(14)

式中：Tia為節點a對應的狀態指標系數值，例如節點a處于Z2區域，則Tia=T2，同理Tib為節點b對應的狀態指標系數值，Ea和Eb分別為節點a和節點b的能量指標系數值。

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

LLQIab=RabYLQIab

(15)

LLQIab數值越高表明兩節點間鏈路質量和能量均衡性能越好。

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

(16)

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

2.2 算法流程圖

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

圖3 L-AOMDV算法流程

整個路由算法分為路由發現、路由維護和路由更新3個部分。

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

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

若檢測的LLQI值出現異常，系統進入路由更新狀態：當第一次檢測到LLQI值降低到預警值的時候，開始進行備用路由更新，源節點發送更新信息沿每一條備用路徑到達目的節點，并且重新計算鏈路的LLQI值，當源節點第二次檢測到鏈路狀態降低到預警值的時候，開始切換備用路徑，在備用路徑選擇鏈路狀態最好的路由進行通信，并且將原路徑從路由表中刪除，當所有備用路徑都失效時，重新進行路由發現。

3 仿真與結果

為評估L-AOMDV在BLE Mesh健康監測網絡中的有效性，本文在MATLAB上開發了L-AOMDV算法，并和CSR Mesh路由算法與AOMDV算法進行仿真對比。

3.1 仿真參數設置

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

表1 仿真場景參數

3.2 仿真性能指標

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

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

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

3.3 仿真結果分析

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

圖4 分組投遞率仿真結果

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

圖5 平均節點死亡個數對比

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

圖6 平均路由跳數仿真結果

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

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

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

4 結束語

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