基于改進式隨機不完全著色算法的無線體域網干擾協調

孫彥贊 姜玉鳳 吳雅婷 馬一鳴 方 勇

1 引言

無線體域網（Wireless Body Area Network,WBAN）是一種以人體為中心的短距離無線通信網絡，作為無線傳感網絡的分支和物聯網的重要組成部分，WBAN成為個人健康信息實時遠程監控、采集與傳輸的重要技術手段之一。WBAN由一些人體表面或植入人體內的傳感器節點（Wireless Sensor Node, WSN）和中心處理節點 （Central Processing Node, CPN）組成，一般形成簡單的一跳星型組網結構。傳感器節點將采集到的生理數據傳輸給中心處理節點，中心處理節點既可以對WBAN進行管理，又可以充當與外部網絡之間的網關，將數據傳輸給遠程醫療中心進行研究和分析。

WBAN最新協議標準 IEEE802.15.6規定WBAN網絡節點需達到3 m的傳輸范圍，且能夠支持在633m 的空間范圍內最少10個WBAN網絡的部署。在如此高密度部署下的 WBAN網絡容易造成用戶間干擾問題。當用戶間距離較近時或單位空間內人的密度高于一定值時（如商場、學校、醫院等場景）會產生嚴重的WBAN網絡間干擾，造成信干噪比（Signal to Interference plus Noise Ratio, SINR）惡化，進而降低網絡吞吐量和增加網絡能耗，特別當干擾造成生命關鍵信息丟失時，病人的生命安全將會受到嚴重的威脅。因此，WBAN網絡間干擾抑制在增加 WBAN網絡信息傳輸可靠性和降低系統功耗方面具有至關重要的意義[1]。

WBAN間干擾通常發生于當多個WBAN相互鄰近而彼此間又沒有協同時[24]-。根據WBAN分布式特點，目前比較多的干擾協調算法可分為兩類：功率控制和資源管理。

傳輸功率控制是無線通信網絡中干擾抑制的一個重要手段。文獻[5～10]研究了功率控制的方法對WBAN間干擾進行抑制。其中文獻[5]基于非協作博弈論提出了分布式的用戶間干擾協調算法。每個體感網（Body Sensor Network, BSN）根據測量的鄰近BSN的SINR，采用分布式非協作無后悔學習算法實現傳感器信道和功率的自適應分配，但實現算法較復雜。文獻[6]研究了 WBAN中的非協作功率控制博弈理論，在最大化總系統吞吐量的同時最小化功率的消耗。文獻[7]提出基于增強學習（Reinforcement Learning, RL）算法使 WBAN對歷史經驗進行學習并實現 WBAN用戶間分布式的功率協調。文獻[8]基于人的社交預測信息，發展了基于博弈論的功率控制算法，減少 WBAN的能量消耗及用戶間干擾。文獻[9,10]基于簡單的信道預測，提出一種基于中繼（relay）傳輸功率控制協作通信機制，以降低傳感節點發射功率和信息傳輸中斷概率。雖然基于功率控制的方法有了一定數量的研究，但功率控制方法在很多場景下并不適用于低功耗和結構簡單的WBAN傳感器節點[11]。

資源分配算法是實現無線體域網用戶間干擾協調的另一重要方式。文獻[11～13]基于時分復用多址（Time Division Multiple Address, TDMA）的WBAN，從時隙資源分配的角度研究了WBAN間的干擾協調。文獻[11]研究了WBAN傳感器節點的干擾消除來最大化空間復用率，WBAN協調器通過一段時間的訓練形成干擾此協調器的傳感器節點列表，基于此使高干擾水平的傳感節點間正交傳輸以避免干擾，但算法需要 WBAN協調器花費一定時間形成干擾列表，不太適用于拓撲結構快速動態變化的WBAN。文獻[12]提出基于服務質量 （Quality of Service, QoS）保證的媒體接入控制（Media Access Control, MAC）層資源調度算法以避免WBAN網絡間干擾，但此算法需要協調器間在調度前相互協作通信業務類型，增加了協作復雜度。文獻[13]提出了一種分布式隨機不完全著色算法，實現時隙資源在中心處理節點（CPN）的干擾避免分配，并提高了頻譜資源的空間復用率。但由于算法對已獲得著色的節點限制了其參與下一輪著色，因此該算法并沒能充分提高頻譜資源的空間復用率。基于此，本文提出了改進式隨機不完全著色算法，可在不增加算法復雜度的前提下，進一步提升頻譜資源的空間復用率。

圖1 基于CPN的WBAN網絡間資源調度

本文內容安排如下：第2節闡述了WBAN網絡間干擾避免的資源調度；第3節給出隨機不完全著色算法在 WBAN網絡資源分配中的應用；第 4節提出改進式隨機不完全著色算法；第5節為相關實驗仿真及結果分析；第6節總結全文。

2 WBAN網絡間資源調度

2.1 基于CPN的WBAN網絡間資源調度

在一個單獨的WBAN網絡中，CPN負責管理傳感器節點的接入、離開及其他功能控制，且其一般嵌入在可充電的手機或PDA設備上工作，因此本文傾向研究基于CPN的WBAN網絡間資源調度，以簡化傳感器節點的功能，降低其能耗。基于CPN的 WBAN網絡間資源調度可分兩步完成：首先CPN與其鄰近相互干擾的CPN協商時頻資源的分配，然后 CPN再把獲得的時頻分配給其傳感器節點，如圖1所示。

2.2 著色理論的WBAN網絡間資源分配

圖著色理論被廣泛應用于無線傳感網絡和認知無線電網絡的干擾避免資源分配[14-16]。WBAN網絡場景可建模為一個圖G=（V, E），圖G的頂點集V（G）表示WBAN網絡CPN節點，邊集E（G）表示其連接的兩個頂點（即CPN節點）占用相同無線資源時會相互干擾，圖G的顏色集C表示為該網絡分配的不同時隙，其中|C | = k ，則WBAN間干擾避免的時隙資源調度問題可轉化為對圖的著色問題。通過圖著色算法使相互干擾的頂點間分配不同的顏色，即相鄰干擾用戶間時頻資源正交分配，從而實現鄰近用戶間的干擾抑制。

然而，WBAN用戶在移動時，其拓撲結構將快速變化，用戶間干擾也就會頻繁變化，因此基于圖著色算法的 WBAN間時頻資源分配需要具有高速的收斂性。又由于WBAN協議需支持63m3的空間范圍內至少10個WBAN網絡，60個傳感器節點的部署，因此基于圖著色算法的 WBAN間時頻資源分配需要實現高的信道空間復用率，以滿足在時頻資源有限的情況下實現 WBAN網絡的高密度部署[13]。

對于一個圖，當使用最少數目的顏色對圖完全著色時，稱之為最優空間復用著色。然而圖的最優空間復用完全著色是個NP-hard問題，當前最優空間復用著色最快算法的時間復雜度仍需要O（2nnO（1））。然而當著色顏色數增加至1+Δ（G）時，則完全著色圖G的時間復雜度可降低至 O （l ogn），其中 Δ（ G ）= m ax{dG（v） |v ∈ V （G）}為圖G的最 大 度數，dG（v）為頂點v的度數，但此時著色算法時間復雜度的降低是以空間復用率的降低為代價的[13]。當圖著色用于WBAN的資源分配時，文獻[13]研究發現，當某些 WBAN用戶沒有業務需求時，可采用隨機不完全著色算法（Random Incomplete Coloring,RIC）實現WBAN網絡間的干擾避免資源調度（不完全著色即對沒有業務需求的 WBAN頂點不分配顏色），既可以降低著色算法時間復雜度，又可提高顏色（時隙資源）空間復用率。

3 隨機不完全著色算法

隨機不完全著色（Random Incomplete Coloring,RIC）由隨機值著色和不完全著色兩個部分組成。其中，隨機值著色目的是降低著色算法時間復雜度，提高算法收斂速度，而不完全著色是基于某些WBAN在一定時段內沒有數據傳輸的特點，可對這些節點不著色，降低圖著色所需的色數，提高著色空間復用率[13]。RIC算法流程如表1所示。

RIC算法相比傳統完全著色算法可進一步提高顏色空間復用率[13]，但由于RIC算法中限制了已著色節點在下一輪著色中的顏色競爭，因此制約了顏色空間復用率的進一步提高。基于此，本文提出一種改進的隨機不完全著色算法（Improved Random Incomplete Coloring, IRIC），消除對已著色節點在下一輪著色中的顏色競爭限制，以進一步提高顏色空間復用率。但此時某些節點在競爭第2種以上的顏色時，可能出現其對鄰近未著色節點或分配顏色數量較少節點的可用顏色進一步占用而造成的節點著色饑餓問題。為此，所提IRIC算法中引入了公平著色影響因子ε，以在提高顏色空間復用率的前提下，保證節點間顏色分配公平性和消除節點著色饑餓問題。

表1 RIC算法流程

4 改進式隨機不完全著色算法

為消除 WBAN間網絡干擾的同時，進一步提高WBAN網絡時頻資源空間復用率和系統吞吐量，同時兼顧WBAN網絡CPN資源分配的公平性，本文所提改進式隨機不完全著色算法（Improved Random Incomplete Coloring, IRIC）流程如表2所示。

表2 IRIC算法流程

4.1 顏色空間復用率分析

空間復用率可以用每種顏色著色的頂點數pcV（Vertices-per-color）來表示，即

IRIC算法消除了RIC算法中只有未著色的節點才能參與下一輪顏色競爭的限制，可使已著色節點進一步參與到下一輪的顏色競爭，從而進一步提高顏色空間復用率。IRIC相對于 RIC算法空間復用率提高的一個例子如圖2所示。

4.2 公平性分析

為避免某些節點在競爭第2種以上的顏色時，對鄰近未著色節點或分配顏色較少節點的可用顏色進一步占用而造成的節點著色饑餓問題，IRIC算法中引入了公平著色影響因子ε, ε取整數，且ε≥0，如表2所示。當ε=0時，節點間著色可實現最大公平性，ε增大，則節點間公平性降低。如當ε=0,?u≥ ?v且cv= cu時，只有|Lu（ r）|≤|Lv（ r）|時，節點u才可獲得顏色 cu，而當|Lu（ r）|＞|Lv（ r）|時，意味著節點u獲得的顏色數已經大于節點v所獲顏色數，則不再分配 cu給節點u。通過ε的取值，可控制鄰近節點間最終所分配的顏色數量差值，即可控制WBAN網絡CPN節點分配時頻資源的公平性。

5 仿真實驗

本節對IRIC算法分別從算法時間復雜度、時頻資源空間復用率、網絡吞吐量和網絡能耗方面進行了性能仿真。基于CPN的WBAN網絡間干擾避免資源調度采用時分多址接入（Time Division Multiple Access, TDMA），信道從頻域分為兩條不同的信道：WBAN間信道和WBAN內信道。每條信道從時間上分為不同的時隙。CPN分別利用WBAN間信道和 WBAN內信道進行資源競爭和WBAN內傳感器節點的人體生理數據收集。傳感器節點僅利用WBAN內信道進行人體生理數據傳輸。CPN首先利用WBAN間信道通過著色算法競爭可用時隙資源，然后利用 WBAN內信道向其傳感器節點發送信標以分配其所獲的時隙資源。最后，傳感器節點在所獲得的 WBAN內信道的數據時隙向其CPN發送人體生理數據[13]。

5.1 WBAN網絡場景及仿真參數

n個CPN節點隨機均勻分布在 1 0×10 m2的正方形區域內，n取值 12, 25, 50, 100以分別模擬WBAN低、中、高、非常高部署密度的網絡場景。CPN間干擾距離設為2 m。信道增益 hij=CPN與傳感器的發射功率 p = 1 00 mW，信道帶寬B= 1 2 kHz，白噪聲功率譜密度 n0為-120 dBm/Hz，公平因子ε為0。著色算法時間復雜度和空間復用率分別用一次 while循環內著色輪數 Rpc（Round per circle）和每種顏色平均著色頂點數 Vpc（Vertices per color）來衡量。

5.2 仿真結果及分析

圖2 RIC與IRIC顏色空間復用率分析

圖3 仿真了IRIC算法與RIC算法的時間算法復雜度pcR 隨可用顏色數和WBAN用戶部署密度不同而變化的曲線。其中可用顏色數由1增加至15。由仿真結果可知，RIC算法隨著可用顏色數的增加，其執行一次著色循環的著色輪數基本沒有變化，這是由于RIC算法在對頂點著色過程中，頂點獲得一種顏色即退出著色循環，頂點沒有可用顏色時也立即退出著色循環，顏色數大小對著色循環次數影響很小。隨著 WBAN網絡部署密度n的增加，CPN間干擾機會增大，因此RIC算法pcR 會有所增加。而在本文所提IRIC算法中，當頂點獲得顏色后，頂點為進一步提高顏色復用率，并不會立即退出著色循環，而是直到其可用顏色集為空集時才退出著色循環，因此，隨著可用顏色數的增加，其pcR 呈遞增趨勢。隨著WBAN網絡部署密度n的增加，CPN間干擾機會增大，這樣一方面會造成IRIC算法每次著色循環內著色輪數pcR 有所增加，另一方面又會使每個頂點的可用顏色集的顏色數降低，從而造成每個頂點著色輪數pcR 的減少，最終第 2種影響因素超過了第 1種影響因素，從而造成隨著 WBAN網絡部署密度n的增加，pcR 呈減少趨勢。

IRIC算法與 RIC算法空間復用率對比仿真如圖4所示。在一定的WBAN網絡部署密度下，對RIC算法，CPN節點分配一種顏色后會立即退出著色循環，隨著顏色數的增加，每種顏色可著色的頂點數減少，甚至會出現某些顏色沒有頂點可著色的情況，因此其顏色復用率隨可用顏色數的增加呈遞減趨勢。隨著 WBAN部署密度的增加，節點對顏色的需求量會上升，因此其顏色復用率會有所上升。對本文所提IRIC算法，由于CPN節點在獲得一種顏色后并不會退出著色循環，直到其可用顏色集為空時，CPN節點才會退出著色循環。因此，對每種顏色來說，其著色地位是相同的，因此每種顏色空間復用率是一定值，顏色數的增加不會降低顏色的空間復用率。而隨著WBAN網絡部署密度的增加，每種顏色可著色的頂點數會上升，意味著每種顏色空間復用率的提升，因此所有顏色空間復用率的期望值也就上升。

圖5是IRIC算法與RIC算法的用戶平均功率隨 WBAN網絡部署密度和可用顏色數不同而變化的仿真對比曲線。平均功率為

其中 nk為顏色（時隙）k時工作的CPN數量，K為可用顏色數量，P為CPN或傳感節點發射功率。 由圖5可知，對RIC算法，隨著可用顏色數量的增加，每種顏色的平均著色點數降低，意味著每時隙工作的節點數 nk減少，因此在WBAN部署密度n一定時，用戶的平均功率隨著可用顏色數的增加而降低。而對IRIC算法，隨著可用顏色的增加，其每種顏色的平均著色點數基本不變，意味著每時隙工作的節點數 nk基本不變，因此在WBAN部署密度n一定時，用戶的平均功率隨著可用顏色數的增加基本保持不變。當用戶密度n增加時，由圖5仿真可知，nk增加的幅度遠小于n增加的幅度，因此，對RIC和IRIC算法，隨著WBAN部署密度的增加，用戶平均功率減少。

圖3 IRIC算法與RIC算法時間復雜度 pcR 仿真對比

圖4 IRIC算法與RIC算法顏色 空間復用率 pcV 仿真對比

圖5 IRIC算法與RIC算法 用戶平均功率仿真對比

IRIC算法和 RIC算法系統總吞吐量的仿真對比如圖6所示。在WBAN部署密度一定時，隨著可用顏色的增加，RIC算法空間復用率降低，因此，其系統吞吐量呈下降趨勢；而IRIC算法可保持空間復用率在較高的穩定值，因此系統吞吐量保持恒定。當WBAN部署密度變大時，RIC和IRIC空間復用率上升，因此系統吞吐量都呈上升趨勢。

圖6 IRIC算法與RIC算法系統總吞吐量仿真對比

6 結束語

本文提出了一種改進式隨機不完全著色算法（IRIC），實現了WBAN網絡間干擾避免的時隙資源分配。該算法在兼顧用戶公平的前提下，提高了資源分配空間復用率，優化了系統吞吐量。仿真結果表明，所提IRIC算法相比RIC算法時間復雜度略有惡化，但該算法有效地改善了資源空間復用率和系統吞吐量。未來會進一步研究公平因子ε對網絡總吞吐量和WBAN網絡間公平性的影響。

[1] Movassaghi S, Abolhasan M, Lipman J, et al..Wireless body area networks: A survey[J]. IEEE Journal on Communications Surveys & Tutorials, 2014, 16（3）: 1658-1686.

[2] Yang Wen-bin and Sayrafian-Pour K. Interference mitigation for body area networks[C]. IEEE Conference on 22nd International Symposium on Personal Indoor and Mobile Radio Communications （PIMRC）, Toronto, 2011: 2193-2197.

[3] De Silva B, Natarajan A, and Motani M. Inter-user interference in body sensor networks: preliminary investigation and an infrastructure based solution[C]. IEEE Conference on Sixth International Workshop on Wearable and Implantable Body Sensor Networks, Berkeley, 2009:35-40.

[4] Dong J and Smith D. Cooperative body-areacommunications: enhancing coexistence without coordination between networks[C]. IEEE Conference on 23rd International Symposium on Personal Indoor and Mobile Radio Communication （PIMRC）, Sydney, 2012: 2269-2274.

[5] Fang Geng-fa, Dutkiewicz E, Yu Ke-gen, et al.. Distributed internetwork interference coordination for wireless body area networks[C]. IEEE Conference on Global Telecommunications Conference （GLOBECOM 2010）, Miami, 2010: 1-5.

[6] Kazemi R, Vesilo R, Dutkiewicz E, et al.. Inter-network interference mitigation in wireless body area networks using power control games[C]. IEEE Conference on International Symposium on Communications and Information Technologies（ISCIT）, Tokyo, 2010: 81-86.

[7] Kazemi R, Vesilo R, Dutkiewicz E, et al.. Reinforcement learning in power control games for internet work interference mitigation in wireless body area networks[C]. IEEE Conference on International Symposium on Communications and Information Technologies （ISCIT）, Australia, 2012:256-262.

[8] Zhang Zhao-yang, Wang Hong-gang, Wang Chong-gang, et al.. Interference mitigation for cyber-physical wireless body area network system using social networks[J]. IEEE Transactions on Emerging Topics in Computing, 2013, 1（1）:121-132.

[9] Dong Jie and Smith D. Joint relay selection and transmit power control for wireless body area networks coexistence[C].IEEE International Conference on Communications （ICC）,Australia, 2014: 5676-5681.

[10] Dong Jie and Smith D. Opportunistic relaying in wireless body area networks: Coexistence performance[C]. IEEE International Conference on Communications （ICC）,Hungary, 2013: 5613-5618.

[11] Movassaghi S, Abolhasan M, and Smith D. Smart spectrum allocation for interference mitigation in Wireless Body Area Networks[C]. IEEE International Conference on Communications （ICC）, Australia, 2014: 5688-5693.

[12] Jamthe A, Mishra A, and Agrawal D P. Scheduling schemes for interference suppression in healthcare sensor networks[C].IEEE International Conference on Communications （ICC）,Australia, 2014: 391-396.

[13] Cheng Shih-heng and Huang Ching-yao. Coloring-based inter-WBAN scheduling for mobile wireless body area networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24（2）: 250-259.

[14] Gandham S, Dawande M, and Prakash R. Link Scheduling in wireless sensor networks: distributed edge-coloring revisited[C]. IEEE Conference on 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, USA, 2005, 4: 2492-2501.

[15] Fonseca Jr B J B. An augmented graph-based coloring scheme to derive upper bounds for the performance of distributed schedulers in CSMA-based mobile Ad Hoc networks[C]. IEEE Conference on Wireless Communication and Mobile Computing, Wuhan, 2006: 761-766.

[16] Sun Yan-zan, Hu Hong-lin, Liu Fu-qiang, et al.. Dynamic spectrum access based on MAC-layer spectrum sensing and prior channel pre-allocation strategy[J]. IEICE Transactions on Communications, 2010, E93-B（3）: 609-619.