孫彥贊 姜玉鳳 吳雅婷 馬一鳴 方 勇
無線體域網(wǎng)(Wireless Body Area Network,WBAN)是一種以人體為中心的短距離無線通信網(wǎng)絡(luò),作為無線傳感網(wǎng)絡(luò)的分支和物聯(lián)網(wǎng)的重要組成部分,WBAN成為個人健康信息實時遠程監(jiān)控、采集與傳輸?shù)闹匾夹g(shù)手段之一。WBAN由一些人體表面或植入人體內(nèi)的傳感器節(jié)點(Wireless Sensor Node, WSN)和中心處理節(jié)點 (Central Processing Node, CPN)組成,一般形成簡單的一跳星型組網(wǎng)結(jié)構(gòu)。傳感器節(jié)點將采集到的生理數(shù)據(jù)傳輸給中心處理節(jié)點,中心處理節(jié)點既可以對WBAN進行管理,又可以充當(dāng)與外部網(wǎng)絡(luò)之間的網(wǎng)關(guān),將數(shù)據(jù)傳輸給遠程醫(yī)療中心進行研究和分析。
WBAN最新協(xié)議標(biāo)準(zhǔn) IEEE802.15.6規(guī)定WBAN網(wǎng)絡(luò)節(jié)點需達到3 m的傳輸范圍,且能夠支持在633m 的空間范圍內(nèi)最少10個WBAN網(wǎng)絡(luò)的部署。在如此高密度部署下的 WBAN網(wǎng)絡(luò)容易造成用戶間干擾問題。當(dāng)用戶間距離較近時或單位空間內(nèi)人的密度高于一定值時(如商場、學(xué)校、醫(yī)院等場景)會產(chǎn)生嚴(yán)重的WBAN網(wǎng)絡(luò)間干擾,造成信干噪比(Signal to Interference plus Noise Ratio, SINR)惡化,進而降低網(wǎng)絡(luò)吞吐量和增加網(wǎng)絡(luò)能耗,特別當(dāng)干擾造成生命關(guān)鍵信息丟失時,病人的生命安全將會受到嚴(yán)重的威脅。因此,WBAN網(wǎng)絡(luò)間干擾抑制在增加 WBAN網(wǎng)絡(luò)信息傳輸可靠性和降低系統(tǒng)功耗方面具有至關(guān)重要的意義[1]。
WBAN間干擾通常發(fā)生于當(dāng)多個WBAN相互鄰近而彼此間又沒有協(xié)同時[24]-。根據(jù)WBAN分布式特點,目前比較多的干擾協(xié)調(diào)算法可分為兩類:功率控制和資源管理。
傳輸功率控制是無線通信網(wǎng)絡(luò)中干擾抑制的一個重要手段。文獻[5~10]研究了功率控制的方法對WBAN間干擾進行抑制。其中文獻[5]基于非協(xié)作博弈論提出了分布式的用戶間干擾協(xié)調(diào)算法。每個體感網(wǎng)(Body Sensor Network, BSN)根據(jù)測量的鄰近BSN的SINR,采用分布式非協(xié)作無后悔學(xué)習(xí)算法實現(xiàn)傳感器信道和功率的自適應(yīng)分配,但實現(xiàn)算法較復(fù)雜。文獻[6]研究了 WBAN中的非協(xié)作功率控制博弈理論,在最大化總系統(tǒng)吞吐量的同時最小化功率的消耗。文獻[7]提出基于增強學(xué)習(xí)(Reinforcement Learning, RL)算法使 WBAN對歷史經(jīng)驗進行學(xué)習(xí)并實現(xiàn) WBAN用戶間分布式的功率協(xié)調(diào)。文獻[8]基于人的社交預(yù)測信息,發(fā)展了基于博弈論的功率控制算法,減少 WBAN的能量消耗及用戶間干擾。文獻[9,10]基于簡單的信道預(yù)測,提出一種基于中繼(relay)傳輸功率控制協(xié)作通信機制,以降低傳感節(jié)點發(fā)射功率和信息傳輸中斷概率。雖然基于功率控制的方法有了一定數(shù)量的研究,但功率控制方法在很多場景下并不適用于低功耗和結(jié)構(gòu)簡單的WBAN傳感器節(jié)點[11]。
資源分配算法是實現(xiàn)無線體域網(wǎng)用戶間干擾協(xié)調(diào)的另一重要方式。文獻[11~13]基于時分復(fù)用多址(Time Division Multiple Address, TDMA)的WBAN,從時隙資源分配的角度研究了WBAN間的干擾協(xié)調(diào)。文獻[11]研究了WBAN傳感器節(jié)點的干擾消除來最大化空間復(fù)用率,WBAN協(xié)調(diào)器通過一段時間的訓(xùn)練形成干擾此協(xié)調(diào)器的傳感器節(jié)點列表,基于此使高干擾水平的傳感節(jié)點間正交傳輸以避免干擾,但算法需要 WBAN協(xié)調(diào)器花費一定時間形成干擾列表,不太適用于拓?fù)浣Y(jié)構(gòu)快速動態(tài)變化的WBAN。文獻[12]提出基于服務(wù)質(zhì)量 (Quality of Service, QoS)保證的媒體接入控制(Media Access Control, MAC)層資源調(diào)度算法以避免WBAN網(wǎng)絡(luò)間干擾,但此算法需要協(xié)調(diào)器間在調(diào)度前相互協(xié)作通信業(yè)務(wù)類型,增加了協(xié)作復(fù)雜度。文獻[13]提出了一種分布式隨機不完全著色算法,實現(xiàn)時隙資源在中心處理節(jié)點(CPN)的干擾避免分配,并提高了頻譜資源的空間復(fù)用率。但由于算法對已獲得著色的節(jié)點限制了其參與下一輪著色,因此該算法并沒能充分提高頻譜資源的空間復(fù)用率。基于此,本文提出了改進式隨機不完全著色算法,可在不增加算法復(fù)雜度的前提下,進一步提升頻譜資源的空間復(fù)用率。
圖1 基于CPN的WBAN網(wǎng)絡(luò)間資源調(diào)度
本文內(nèi)容安排如下:第2節(jié)闡述了WBAN網(wǎng)絡(luò)間干擾避免的資源調(diào)度;第3節(jié)給出隨機不完全著色算法在 WBAN網(wǎng)絡(luò)資源分配中的應(yīng)用;第 4節(jié)提出改進式隨機不完全著色算法;第5節(jié)為相關(guān)實驗仿真及結(jié)果分析;第6節(jié)總結(jié)全文。
在一個單獨的WBAN網(wǎng)絡(luò)中,CPN負(fù)責(zé)管理傳感器節(jié)點的接入、離開及其他功能控制,且其一般嵌入在可充電的手機或PDA設(shè)備上工作,因此本文傾向研究基于CPN的WBAN網(wǎng)絡(luò)間資源調(diào)度,以簡化傳感器節(jié)點的功能,降低其能耗。基于CPN的 WBAN網(wǎng)絡(luò)間資源調(diào)度可分兩步完成:首先CPN與其鄰近相互干擾的CPN協(xié)商時頻資源的分配,然后 CPN再把獲得的時頻分配給其傳感器節(jié)點,如圖1所示。
圖著色理論被廣泛應(yīng)用于無線傳感網(wǎng)絡(luò)和認(rèn)知無線電網(wǎng)絡(luò)的干擾避免資源分配[14-16]。WBAN網(wǎng)絡(luò)場景可建模為一個圖G=(V, E),圖G的頂點集V(G)表示W(wǎng)BAN網(wǎng)絡(luò)CPN節(jié)點,邊集E(G)表示其連接的兩個頂點(即CPN節(jié)點)占用相同無線資源時會相互干擾,圖G的顏色集C表示為該網(wǎng)絡(luò)分配的不同時隙,其中|C | = k ,則WBAN間干擾避免的時隙資源調(diào)度問題可轉(zhuǎn)化為對圖的著色問題。通過圖著色算法使相互干擾的頂點間分配不同的顏色,即相鄰干擾用戶間時頻資源正交分配,從而實現(xiàn)鄰近用戶間的干擾抑制。
然而,WBAN用戶在移動時,其拓?fù)浣Y(jié)構(gòu)將快速變化,用戶間干擾也就會頻繁變化,因此基于圖著色算法的 WBAN間時頻資源分配需要具有高速的收斂性。又由于WBAN協(xié)議需支持63m3的空間范圍內(nèi)至少10個WBAN網(wǎng)絡(luò),60個傳感器節(jié)點的部署,因此基于圖著色算法的 WBAN間時頻資源分配需要實現(xiàn)高的信道空間復(fù)用率,以滿足在時頻資源有限的情況下實現(xiàn) WBAN網(wǎng)絡(luò)的高密度部署[13]。
對于一個圖,當(dāng)使用最少數(shù)目的顏色對圖完全著色時,稱之為最優(yōu)空間復(fù)用著色。然而圖的最優(yōu)空間復(fù)用完全著色是個NP-hard問題,當(dāng)前最優(yōu)空間復(fù)用著色最快算法的時間復(fù)雜度仍需要O(2nnO(1))。然而當(dāng)著色顏色數(shù)增加至1+Δ(G)時,則完全著色圖G的時間復(fù)雜度可降低至 O (l ogn),其中 Δ( G )= m ax{dG(v) |v ∈ V (G)}為圖G的最 大 度數(shù),dG(v)為頂點v的度數(shù),但此時著色算法時間復(fù)雜度的降低是以空間復(fù)用率的降低為代價的[13]。當(dāng)圖著色用于WBAN的資源分配時,文獻[13]研究發(fā)現(xiàn),當(dāng)某些 WBAN用戶沒有業(yè)務(wù)需求時,可采用隨機不完全著色算法(Random Incomplete Coloring,RIC)實現(xiàn)WBAN網(wǎng)絡(luò)間的干擾避免資源調(diào)度(不完全著色即對沒有業(yè)務(wù)需求的 WBAN頂點不分配顏色),既可以降低著色算法時間復(fù)雜度,又可提高顏色(時隙資源)空間復(fù)用率。
隨機不完全著色(Random Incomplete Coloring,RIC)由隨機值著色和不完全著色兩個部分組成。其中,隨機值著色目的是降低著色算法時間復(fù)雜度,提高算法收斂速度,而不完全著色是基于某些WBAN在一定時段內(nèi)沒有數(shù)據(jù)傳輸?shù)奶攸c,可對這些節(jié)點不著色,降低圖著色所需的色數(shù),提高著色空間復(fù)用率[13]。RIC算法流程如表1所示。
RIC算法相比傳統(tǒng)完全著色算法可進一步提高顏色空間復(fù)用率[13],但由于RIC算法中限制了已著色節(jié)點在下一輪著色中的顏色競爭,因此制約了顏色空間復(fù)用率的進一步提高?;诖?,本文提出一種改進的隨機不完全著色算法(Improved Random Incomplete Coloring, IRIC),消除對已著色節(jié)點在下一輪著色中的顏色競爭限制,以進一步提高顏色空間復(fù)用率。但此時某些節(jié)點在競爭第2種以上的顏色時,可能出現(xiàn)其對鄰近未著色節(jié)點或分配顏色數(shù)量較少節(jié)點的可用顏色進一步占用而造成的節(jié)點著色饑餓問題。為此,所提IRIC算法中引入了公平著色影響因子ε,以在提高顏色空間復(fù)用率的前提下,保證節(jié)點間顏色分配公平性和消除節(jié)點著色饑餓問題。
表1 RIC算法流程
為消除 WBAN間網(wǎng)絡(luò)干擾的同時,進一步提高WBAN網(wǎng)絡(luò)時頻資源空間復(fù)用率和系統(tǒng)吞吐量,同時兼顧WBAN網(wǎng)絡(luò)CPN資源分配的公平性,本文所提改進式隨機不完全著色算法(Improved Random Incomplete Coloring, IRIC)流程如表2所示。
表2 IRIC算法流程
空間復(fù)用率可以用每種顏色著色的頂點數(shù)pcV(Vertices-per-color)來表示,即
IRIC算法消除了RIC算法中只有未著色的節(jié)點才能參與下一輪顏色競爭的限制,可使已著色節(jié)點進一步參與到下一輪的顏色競爭,從而進一步提高顏色空間復(fù)用率。IRIC相對于 RIC算法空間復(fù)用率提高的一個例子如圖2所示。
為避免某些節(jié)點在競爭第2種以上的顏色時,對鄰近未著色節(jié)點或分配顏色較少節(jié)點的可用顏色進一步占用而造成的節(jié)點著色饑餓問題,IRIC算法中引入了公平著色影響因子ε, ε取整數(shù),且ε≥0,如表2所示。當(dāng)ε=0時,節(jié)點間著色可實現(xiàn)最大公平性,ε增大,則節(jié)點間公平性降低。如當(dāng)ε=0,?u≥ ?v且cv= cu時,只有|Lu( r)|≤|Lv( r)|時,節(jié)點u才可獲得顏色 cu,而當(dāng)|Lu( r)|>|Lv( r)|時,意味著節(jié)點u獲得的顏色數(shù)已經(jīng)大于節(jié)點v所獲顏色數(shù),則不再分配 cu給節(jié)點u。通過ε的取值,可控制鄰近節(jié)點間最終所分配的顏色數(shù)量差值,即可控制WBAN網(wǎng)絡(luò)CPN節(jié)點分配時頻資源的公平性。
本節(jié)對IRIC算法分別從算法時間復(fù)雜度、時頻資源空間復(fù)用率、網(wǎng)絡(luò)吞吐量和網(wǎng)絡(luò)能耗方面進行了性能仿真?;贑PN的WBAN網(wǎng)絡(luò)間干擾避免資源調(diào)度采用時分多址接入(Time Division Multiple Access, TDMA),信道從頻域分為兩條不同的信道:WBAN間信道和WBAN內(nèi)信道。每條信道從時間上分為不同的時隙。CPN分別利用WBAN間信道和 WBAN內(nèi)信道進行資源競爭和WBAN內(nèi)傳感器節(jié)點的人體生理數(shù)據(jù)收集。傳感器節(jié)點僅利用WBAN內(nèi)信道進行人體生理數(shù)據(jù)傳輸。CPN首先利用WBAN間信道通過著色算法競爭可用時隙資源,然后利用 WBAN內(nèi)信道向其傳感器節(jié)點發(fā)送信標(biāo)以分配其所獲的時隙資源。最后,傳感器節(jié)點在所獲得的 WBAN內(nèi)信道的數(shù)據(jù)時隙向其CPN發(fā)送人體生理數(shù)據(jù)[13]。
n個CPN節(jié)點隨機均勻分布在 1 0×10 m2的正方形區(qū)域內(nèi),n取值 12, 25, 50, 100以分別模擬WBAN低、中、高、非常高部署密度的網(wǎng)絡(luò)場景。CPN間干擾距離設(shè)為2 m。信道增益 hij=CPN與傳感器的發(fā)射功率 p = 1 00 mW,信道帶寬B= 1 2 kHz,白噪聲功率譜密度 n0為-120 dBm/Hz,公平因子ε為0。著色算法時間復(fù)雜度和空間復(fù)用率分別用一次 while循環(huán)內(nèi)著色輪數(shù) Rpc(Round per circle)和每種顏色平均著色頂點數(shù) Vpc(Vertices per color)來衡量。
圖2 RIC與IRIC顏色空間復(fù)用率分析
圖3 仿真了IRIC算法與RIC算法的時間算法復(fù)雜度pcR 隨可用顏色數(shù)和WBAN用戶部署密度不同而變化的曲線。其中可用顏色數(shù)由1增加至15。由仿真結(jié)果可知,RIC算法隨著可用顏色數(shù)的增加,其執(zhí)行一次著色循環(huán)的著色輪數(shù)基本沒有變化,這是由于RIC算法在對頂點著色過程中,頂點獲得一種顏色即退出著色循環(huán),頂點沒有可用顏色時也立即退出著色循環(huán),顏色數(shù)大小對著色循環(huán)次數(shù)影響很小。隨著 WBAN網(wǎng)絡(luò)部署密度n的增加,CPN間干擾機會增大,因此RIC算法pcR 會有所增加。而在本文所提IRIC算法中,當(dāng)頂點獲得顏色后,頂點為進一步提高顏色復(fù)用率,并不會立即退出著色循環(huán),而是直到其可用顏色集為空集時才退出著色循環(huán),因此,隨著可用顏色數(shù)的增加,其pcR 呈遞增趨勢。隨著WBAN網(wǎng)絡(luò)部署密度n的增加,CPN間干擾機會增大,這樣一方面會造成IRIC算法每次著色循環(huán)內(nèi)著色輪數(shù)pcR 有所增加,另一方面又會使每個頂點的可用顏色集的顏色數(shù)降低,從而造成每個頂點著色輪數(shù)pcR 的減少,最終第 2種影響因素超過了第 1種影響因素,從而造成隨著 WBAN網(wǎng)絡(luò)部署密度n的增加,pcR 呈減少趨勢。
IRIC算法與 RIC算法空間復(fù)用率對比仿真如圖4所示。在一定的WBAN網(wǎng)絡(luò)部署密度下,對RIC算法,CPN節(jié)點分配一種顏色后會立即退出著色循環(huán),隨著顏色數(shù)的增加,每種顏色可著色的頂點數(shù)減少,甚至?xí)霈F(xiàn)某些顏色沒有頂點可著色的情況,因此其顏色復(fù)用率隨可用顏色數(shù)的增加呈遞減趨勢。隨著 WBAN部署密度的增加,節(jié)點對顏色的需求量會上升,因此其顏色復(fù)用率會有所上升。對本文所提IRIC算法,由于CPN節(jié)點在獲得一種顏色后并不會退出著色循環(huán),直到其可用顏色集為空時,CPN節(jié)點才會退出著色循環(huán)。因此,對每種顏色來說,其著色地位是相同的,因此每種顏色空間復(fù)用率是一定值,顏色數(shù)的增加不會降低顏色的空間復(fù)用率。而隨著WBAN網(wǎng)絡(luò)部署密度的增加,每種顏色可著色的頂點數(shù)會上升,意味著每種顏色空間復(fù)用率的提升,因此所有顏色空間復(fù)用率的期望值也就上升。
圖5是IRIC算法與RIC算法的用戶平均功率隨 WBAN網(wǎng)絡(luò)部署密度和可用顏色數(shù)不同而變化的仿真對比曲線。平均功率為
其中 nk為顏色(時隙)k時工作的CPN數(shù)量,K為可用顏色數(shù)量,P為CPN或傳感節(jié)點發(fā)射功率。 由圖5可知,對RIC算法,隨著可用顏色數(shù)量的增加,每種顏色的平均著色點數(shù)降低,意味著每時隙工作的節(jié)點數(shù) nk減少,因此在WBAN部署密度n一定時,用戶的平均功率隨著可用顏色數(shù)的增加而降低。而對IRIC算法,隨著可用顏色的增加,其每種顏色的平均著色點數(shù)基本不變,意味著每時隙工作的節(jié)點數(shù) nk基本不變,因此在WBAN部署密度n一定時,用戶的平均功率隨著可用顏色數(shù)的增加基本保持不變。當(dāng)用戶密度n增加時,由圖5仿真可知,nk增加的幅度遠小于n增加的幅度,因此,對RIC和IRIC算法,隨著WBAN部署密度的增加,用戶平均功率減少。
圖3 IRIC算法與RIC算法時間復(fù)雜度 pcR 仿真對比
圖4 IRIC算法與RIC算法顏色 空間復(fù)用率 pcV 仿真對比
圖5 IRIC算法與RIC算法 用戶平均功率仿真對比
IRIC算法和 RIC算法系統(tǒng)總吞吐量的仿真對比如圖6所示。在WBAN部署密度一定時,隨著可用顏色的增加,RIC算法空間復(fù)用率降低,因此,其系統(tǒng)吞吐量呈下降趨勢;而IRIC算法可保持空間復(fù)用率在較高的穩(wěn)定值,因此系統(tǒng)吞吐量保持恒定。當(dāng)WBAN部署密度變大時,RIC和IRIC空間復(fù)用率上升,因此系統(tǒng)吞吐量都呈上升趨勢。
圖6 IRIC算法與RIC算法系統(tǒng)總吞吐量仿真對比
本文提出了一種改進式隨機不完全著色算法(IRIC),實現(xiàn)了WBAN網(wǎng)絡(luò)間干擾避免的時隙資源分配。該算法在兼顧用戶公平的前提下,提高了資源分配空間復(fù)用率,優(yōu)化了系統(tǒng)吞吐量。仿真結(jié)果表明,所提IRIC算法相比RIC算法時間復(fù)雜度略有惡化,但該算法有效地改善了資源空間復(fù)用率和系統(tǒng)吞吐量。未來會進一步研究公平因子ε對網(wǎng)絡(luò)總吞吐量和WBAN網(wǎng)絡(luò)間公平性的影響。
[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.