樊文豪，謝志軍,2，俞文彬

（1 . 寧波大學信息科學與工程學院，浙江 寧波 315211；2. 維多利亞大學科學與工程學院，澳大利亞 墨爾本 14428）

基于CPN的WBANs調度算法研究*

樊文豪1，謝志軍1,2，俞文彬1

（1 . 寧波大學信息科學與工程學院，浙江 寧波 315211；2. 維多利亞大學科學與工程學院，澳大利亞 墨爾本 14428）

將無線體域網間調度問題（Inter-WBANs Scheduling，IWS）轉化為基于中央處理節(jié)點（Central Process Node，CPN）的調度，模型化為圖著色問題。提出一種啟發(fā)式混合遺傳模擬退火算法對相應的WBAN進行調度，緩解網間干擾，使無線體域網的整體性能得到優(yōu)化。另外， 本文基于仿真結果對算法進行了評估，實驗結果表明該算法可以在動態(tài)WBAN干擾環(huán)境下更好地適用于功耗和資源受限的WBAN。

無線體域網 體域網間調度 圖著色 混合遺傳

1 引言

無線體域網（WBAN）是一種無線個人傳感網，主要由1組無線傳感器節(jié)點及1個中央處理節(jié)點（CPN）組成，具體如圖1所示。其中CPN主要負責收集來自WSNs的重要數據。與傳統(tǒng)無線傳感網（WSN）不同，WBAN用戶的移動使得對應網絡具有較高的移動性[1]，網絡拓撲結構和WSN相比也不夠穩(wěn)定。多個WBAN的動態(tài)拓撲結構與MANETs相似，但是WBAN是基于組而不是基于節(jié)點的動態(tài)拓撲。當區(qū)域中多個WBAN共存時，各個網絡之間相互沖突的可能性極大，因此WBAN間調度研究就顯得極為重要。

無線體域網的分布式沖突避免調度可以模型化為已知的分布式圖著色問題（常用于W S N、M A N E Ts[2]）。相應的網絡拓撲對應于圖模型G=(V,E)。其中V表示傳感器節(jié)點，E表示相互干擾的2個節(jié)點之間無線資源的沖突，顏色集C表示不同的資源單元（時隙、頻帶或者編碼序列）。圖G的頂點完全k著色對應()V GC→，其中|C|=k。這樣相鄰節(jié)點所獲得的顏色不同，相應的鄰接點獲得的資源不同，避免網絡之間的沖突。

圖1 WBAN網絡模型

本文通過將WBANs調度模型化為圖著色，提出一種啟發(fā)式混合模擬退火遺傳算法。該算法克服了遺傳算法易陷入局部最優(yōu)、模擬退火算法收斂較慢等缺點，以解決無線體域網調度問題。

2 基于CPN的WBAN調度模型分析

根據WBAN簡單星型網絡結構[3]中CPN/WSN的不對等關系，我們將WBAN調度模型簡化為對WBAN中CPN節(jié)點的調度。單個WBAN中，CPN作為主節(jié)點，其他WSNs為其附屬節(jié)點，CPN對WSNs的加入、離開以及資源分配進行管理。基于此，本文假設了1種基于CPN的2步IWS，具體如圖2所示：

圖2 基于CPN的WBAN調度模型

CPN首先與干擾范圍內的其他CPNs進行資源協(xié)商，然后將占有資源向其WSNs進行分配。這樣，當從對應的CPN接收到帶有預先設定的傳輸模式的信標信息并遵循該模式向CPN發(fā)送重要信號時，WSNs被喚醒。

為模擬WBANs網絡，隨機構造1個2維圖G=(V,E)。V(G)表示CPN集，E(G)表示CPN之間沖突鏈集。在一個區(qū)域內隨機布置n=|V(G)|個頂點，用來模擬WBAN用戶所處的隨機空間位置。如果CPNs之間的距離等于或略小于WBAN之間的相互干擾范圍，用邊連接對應頂點。在這種情況下，基于CPN的IWS與MANET調度類似，但是兩者對資源的調度策略不同。MANET中，每個頂點代表1個無線節(jié)點，MANET注重有效的內節(jié)點通信與路由。因此可以采用邊著色，對應于節(jié)點與節(jié)點之間的通信調度，而在基于CPN的IWS中，每個頂點代表1個傳感器組?；贑PN的IWS試圖解決屬于不同用戶的傳感器組之間的沖突問題。因此頂點著色對應于動態(tài)基于CPN的傳感器組調度問題是合適的。這樣基于CPN的IWS，1個隨機圖的k著色[4]可以對應于V( G)→C，其中|C|=k，鄰接頂點就獲得完全不同的顏色，相應地表示相關數據傳輸的不同資源單元（從WSNs到CPN）。著色算法執(zhí)行1次，完成1次k種資源映射。

3 啟發(fā)式模擬退火遺傳算法解決圖著色問題

簡單的模擬退火遺傳算法[5]結合了全局尋優(yōu)與局部尋優(yōu)性能，相對于單獨的模擬退火算法或者遺傳算法，其計算效率較高。因此在模擬退火遺傳算法基礎上添加啟發(fā)式搜索，更有助于算法性能的提高。

3.1 啟發(fā)式搜索算法

作為啟發(fā)式算法的一種，貪婪算法采用貪婪準則逐步構造最優(yōu)解。即在問題求解的每一個階段，作出在一定標準下可能的最優(yōu)決策。就圖的頂點k著色來說，貪婪算法在進行著色時，會受限于染色體中頂點的次序，只能根據當前已經被著色的頂點和將被著色頂點的鄰接信息來決定本著色頂點的顏色，而不能從全局出發(fā)，利用頂點間的關系構造最優(yōu)著色。本文試圖在已獲得“次優(yōu)解”的鄰域內搜索1個“更好的次優(yōu)解”，不斷進行鄰域搜索直到找到“局部最優(yōu)解”。

3.2 啟發(fā)式混合模擬退火遺傳算法

在貪婪啟發(fā)式遺傳算法的框架下增加模擬退火算子，結合3種算法思想的優(yōu)點，提出新的混合模擬退火遺傳算法。

3.2.1 模擬退火算子設計

根據模擬退火算法思想[6]，本文設計的模擬退火算子如下所示：

1 輸入：初始解S0，鄰接矩陣A

2 輸出：優(yōu)化解S1

3 Begin

4 t=tf×Evaluation(S0)×tp；//計算初始溫度t

5 Do

6 Do

7 n=Neighbor(S0)×Sf；//重新計算搜索次數

8 隨機從S0的鄰域中選擇一個染色體作為S1

9 Δ=Evaluation(S0)-Evaluation(S1)

10 if(Δ＜0)

11 Then S0=S1；

13 While(循環(huán)次數＜n)

14 t=α×t；//α為降溫系數

15 While(不滿足終止條件)

16 Return S0；

17 End //其中tf、tp、Sf、α為用戶自定義參數，控制冷卻調度

另外，算法在每次遺傳算法結束獲得子代個體后，立即對子代個體執(zhí)行模擬退火算子。其目的是：

1）在全體可行解空間的子集內進行搜索，以期望獲得比原來更好的優(yōu)化解。

2）與GGA（貪婪遺傳算法）中只允許解質量的提高不同，必要時也允許解質量下降。以一定概率接受惡化解，擴大搜索范圍，以期望能夠跳過局部最優(yōu)陷阱，盡可能克服早熟與欺騙現象。

3.2.2 啟發(fā)式遺傳算法

（1）建立染色體子空間

對于簡單圖G(n)，頂點集V(G)={v1,v2,…vn}，邊集E(G)={e1,e2,…en}。鄰接矩陣A(G)=(aij)n×n，矩陣A取值如下（n為G中頂點數）：

用C(k)={1,2,…k}來表示顏色集，即用k種顏色進行頂點著色。根據圖著色以及遺傳算法原理，染色體采用整數編碼，具體如下：染色體由長度為n的序列x1x2…xn表示，xi(1≤i≤n)表示圖中頂點vi所著顏色，xi∈C(k)。根據染色體子空間的定義，k種顏色對圖G(n)著色，染色體子空間（即所有可能的著色方案）大小將達到kn，算法效率受到很大影響。為提高算法執(zhí)行速度，將染色體的隨機編碼方案改為啟發(fā)式著色染色體基因。

（2）適應度函數設計

執(zhí)行啟發(fā)式算法頂點著色時，為獲取最優(yōu)著色方案，需要得到最佳著色數。由此，適應度函數設計如下：

令wi(1≤i≤n)值恒為1，此時cmax即表示染色體序列中的最大顏色值。

（3）遺傳算子設計

1）選擇

選擇算子采用簡單輪盤賭策略[7]，即染色體的適應值越大，被選中的概率就越大。規(guī)模為n的種群中，染色體i的適應度值為fi，選擇概率為pi：

2）交叉

染色體子空間設計過程中，由于采用整數編碼方式，為避免產生非法染色體（不包含所有頂點或包含有重復頂點），交叉算子采用部分匹配交叉法[8]（PMX）。具體過程如下：

Begin

1 隨機產生兩個交叉點，并定義兩點之間的區(qū)域為匹配區(qū)域

2 交換兩個染色體的匹配區(qū)域

3 確定匹配區(qū)域間映射關系

4 染色體合法化

End

3）變異

變異算子采用簡單換位變異[9]。過程如下：

Begin

1 染色體的兩個基因位

2 將這兩個基因位上的基因值進行交換

End

4）收斂性分析

定義：若P{M.C(x)=y}＞0，那么稱作y通過x遺傳可達。其中M.C(x)表示單個染色體x通過交叉和變異產生的個體。P{.}表示隨機事件{.}的概率。

引理：若一個遺傳算法滿足如下2個條件：

a）對可行域中任意2個個體x和y，通過遺傳是可達的；

b）種群序列P(0),P(1),…P(t),…是單調的。

定理：算法以概率1收斂到全局最優(yōu)解（全局收斂性）。

證明：

x通過選擇算子被選擇的概率為Pc＞0。設c是由x通過交叉產生的任一子代染色體，z是由局部搜索產生的新子代，z參與變異的概率為Pm＞0，那么經過交叉變異由x產生y的概率滿足：

設z=(z1z2…zn)，y=(y1y2…yn)，由變異算子可知，從xi產生yi的概率為（其中δ為已求得的k頂點著色方案中所用的最少顏色數）。

因此y由x通過遺傳是可達的。

由算法的選擇策略可知，P(0),P(1),…P(t),…具備單調性。綜合以上2點可知遺傳算法以概率1收斂到全局最優(yōu)。

（4）啟發(fā)式混合模擬退火遺傳算法

啟發(fā)式混合模擬退火遺傳算法描述如下：初始產化種群N（包含n個染色體序列）。對種群N中的每個染色體進行貪婪著色（調用coloring）[11]，得到n個相應的著色序列，并對種群進行評價。若當前尚不滿足終止條件，遺傳算子作用于N，再次執(zhí)行貪婪著色，并進行適應度函數評價。模擬退火算子作用于新種群，產生優(yōu)質子代種群，再次執(zhí)行貪婪著色，進行適應度函數評價，直至滿足終止條件。具體描述如下：

1輸入：圖G，鄰接矩陣A

2輸出：最優(yōu)著色序列

3Begin

4 i=0；

5 種群P(i)初始化；

6 種群P(i)中的每一染色體，調用coloring過程；

7 評價種群P(i)；

8 While(終止條件不滿足)

9 遺傳算子作用于種群P(i)產生子代種群C(i)；

10 模擬退火算子分別作用于子代種群C(i)中個體，

11產生優(yōu)化的子代種群P(i+1)；

12 種群P(i+1)中每個染色體，調用coloring過程

13 評價種群P(i+1)；

14 i=i+1；

15 End While

16End

Coloring過程描述如下：

1 Coloring

2 輸入：染色體y1y2…yn

3 輸出：已著色染色體x1x2…xn

4 Begin

5 For(k=1 to n)

6 Call nextcolor(k)；//頂點著色

7 End For

8 End

nextcolor過程描述如下：

1 輸入：等位基因yk，鄰接矩陣A

2 輸出：著色xk

3 Begin

4 k=0；

5 xk=0;

6 While(k＜n)

7 xk=xk+1；//從最小顏色值開始試探

8 i=0；

9 While(i＜n)

10 if(aij=1) and (xk=xi)

11 Then xk=xk+1，i=0；

12 End if

13 i=i+1；

14 End While

15 k=k+1；

16 End While

17 End

通過試驗發(fā)現，引入啟發(fā)式搜索和提高局部搜索能力的模擬退火算子之后，啟發(fā)式混合模擬退火遺傳算法在圖著色問題中的尋優(yōu)能力[10]有了很大提高，能夠獲取較好的最優(yōu)解。

4 算法模擬仿真與實驗結果對比

為驗證算法性能，采用不同頂點密度的二維隨機圖對算法性能進行評估。根據第2部分中的系統(tǒng)模型，選用10個經典圖集分別用來模擬空間WBAN低密度、中密度、高密度以及超高密度分布的情況，相互干擾距離設為2m。為保證算法對比的公平性，將不同算法在同樣的參數環(huán)境下，對選用的圖集分別進行10次試驗，結果分別采用列表與仿真圖進行對比。

啟發(fā)式混合遺傳模擬退火算法與傳統(tǒng)遺傳[12]算法試驗結果對比如表1所示。其中，n表示圖集中頂點數，m為邊數，N表示種群規(guī)模，其中δ為已求得的k頂點著色方案中所用的最少顏色數，C表示當前算法求得的最優(yōu)解，Tavg表示10次運行中求得最優(yōu)解所用的平均進化代數。

表1 GA與HHGSAA同等條件下的實驗結果數據對比

從表1中的數據可以看出，對10個標準圖集，HHGSAA（混合遺傳模擬退火算法）均找到了最優(yōu)解。隨著頂點數、邊數的增加，算法求得最優(yōu)解所需的進化代數也不斷增加。對于高密度（Myciel5、Queen_8-8）及超高密度（Myciel6、Myciel7、Queen_9-9），HHGSAA也可以在不到50代的進化過程中獲得問題的最優(yōu)解。

圖3、圖4分別比較了算法GA和HHGSAA應用到圖集Myciel以及Queen時所用的平均時間（算法GA與HHGSAA分別運行100次，計算平均尋優(yōu)時間）。

圖3 GA與HHGSAA算法性能比較（Myciel圖集）

除此之外，本文還對3種不同算法尋優(yōu)結果中采用的平均最佳著色數進行比較。圖5、圖6分別為3種算法對Myciel圖集和Queen圖集的試驗結果。

圖4 GA與HHGSAA算法性能比較（Queen圖集）

圖5 GA、RIC、HHGSAA尋優(yōu)結果（Myciel圖集）

圖6 GA、RIC、HHGSAA尋優(yōu)結果（Queen圖集）

由實驗結果可以看出，HHGSAA與傳統(tǒng)遺傳算法以及RIC相比，在尋優(yōu)能力和運行速度上都有相當大的提高。由此可見，HHGSAA在解決著色問題上有較大的潛力。

5 結束語

本文提出了一種啟發(fā)式混合遺傳模擬退火算法，實現了快速收斂、有效的WBAN間調度。與傳統(tǒng)的完全著色模式不同，HHGSAA算法具備以下特性：

（1）采用啟發(fā)式搜索方式，優(yōu)化初始種群，以減少尋優(yōu)時間。

（2）通過遺傳與模擬退火這2種算法性能互補，加快算法尋優(yōu)時間的同時提高解質量。

試驗結果表明，HHGSAA算法克服了WBAN之間的沖突，從而提高了移動無線體域網的系統(tǒng)吞吐量。

本文著重于多用戶隨機場合，即可以模型化為2D隨機圖。在以后的工作中，將進一步分析算法在其他特殊場景中的性能。比如排隊中的用戶、影院里的用戶、咖啡廳中的用戶。這些場景可以分別模型化為線型、網格、簇圖，以此評估其實時性能，并與已存在的WBAN解決方案（比如IEEE 802.15.4、藍牙網絡）進行比較。

[1] M Chen, S Gonzalez, A Vasilakos, et al. Body Area Networks: A Survey[J]. Mobile Networks and Applications, 2011,16(2): 171-193.

[2] S Gandham, M Dawande, R Prakash. Link Scheduling in Wireless Sensor Networks: Distributed Edge-Coloring Revisited[J]. Journal of Parallel and Distributed Computing, 2008,68(8): 1122-1134.

[3] S Cheng, C Huang. Colo ring-Based Inter-WBAN Scheduling for Mobile Wireless Body Area Networks[J]. IEEE Transactions on Parallel and Distributed System, 2013,24(2): 250-259.

[4] K Kothapalli, C Scheideler, M Onus, et al. Dist ributed coloring in O/spl tilde/(/spl radic/(log n)) bit rounds[J]. Parallel and Distributed Processing Symposium, 2006: 10-10.

[5] Eiben A E, Vender Hauw J K, Van Hemert J I. Graph Coloring with Adaptive Evolutionary Algorithms[J] . Journal of Heuristics, 1996,4(1): 16-24.

[6] D A Fotakis, S D Likothanassis, S K Stefanakos.

An E volutionary Annealing Approach to Graph Coloring[J]. Applications of Evolutionary Computing, 2001: 120-129.

[7] B L Miller, D E Goldberg. Genetic algorithms, selection schemes, and the varying effects of noise[J]. Evolutionary Computation, 1996,4(2): 113-131.

[8] L D Davis. Hand book of genetic algorithms[M]. New York: Van Nostrand Reinhold, 1991: 1-6.

[9] Fleurent C, Ferland J A. Genetic and Hybrid Algorithms for Graph Coloring[J]. Annals of Operations Research, 1995,63(3): 437 463.

[10] 楊啟文,蔣靜坪,張國宏. GA優(yōu)化 速度的改進[J]. 軟件學報, 2000,12(2): 270-275.

[11] Morgenstem C. Dist ributed Coloration Neighborhood Search[J]. Discrete Mathematic and Theoretical Computer Science, 1996,26(5): 335- 358.

[12] 陳國良,王煦法,莊鎮(zhèn)泉,等. 遺傳算法 及其應用[M].北京: 人民郵電出版社, 1996: 274-284.★

Research on CPN-based Inter-WBANs Scheduling Algorithm

FAN Wen-Hao1, XIE Zhi-Jun1,2, YU Wen-Bin1

(1. Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China; 2. Faculty of Engineering, Victoria University, Melbourne 14428, Australia)

Inter-WBANs (wireless body area networks) scheduling can be transformed into CPN (central process node) scheduling to be modeled as a graph coloring problem. A heuristic hybrid genetic simulated annealing algorithm for scheduling was proposed to mitigate the inter-WBAN interference which optimizes WBAN overall performance. In addition, the proposed algorithm was evaluated according to simulation results. Experimental results demonstrate that the proposed algorithm is more applicable for power-consumption and resources limited WBANs.

WBAN inter-WBANs scheduling coloring hybrid genetic

10.3969/j.issn.1006-1010.2015.08.015

TP393

A

1006-1010(2015)08-0069-06

樊文豪,謝志軍,俞文彬. 基于CPN的WBANs調度算法研究[J]. 移動通信, 2015,39(8): 69-74.

國家自然科學基金項目（51303157）；寧波市自然基金（2013A610044)；“信息與通信工程”浙江省重中之重學科開放基金資助（xkxl1422）

2014-12-15

責任編輯：劉妙 liumiao@mbcom.cn