基于CPN的WBANs調(diào)度算法研究*

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

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

基于CPN的WBANs調(diào)度算法研究*

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

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

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

無線體域網(wǎng) 體域網(wǎng)間調(diào)度 圖著色 混合遺傳

1 引言

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

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

圖1 WBAN網(wǎng)絡(luò)模型

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

2 基于CPN的WBAN調(diào)度模型分析

根據(jù)WBAN簡單星型網(wǎng)絡(luò)結(jié)構(gòu)[3]中CPN/WSN的不對等關(guān)系，我們將WBAN調(diào)度模型簡化為對WBAN中CPN節(jié)點(diǎn)的調(diào)度。單個WBAN中，CPN作為主節(jié)點(diǎn)，其他WSNs為其附屬節(jié)點(diǎn)，CPN對WSNs的加入、離開以及資源分配進(jìn)行管理?；诖?，本文假設(shè)了1種基于CPN的2步IWS，具體如圖2所示：

圖2 基于CPN的WBAN調(diào)度模型

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

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

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

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

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

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

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

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

3.2.1 模擬退火算子設(shè)計(jì)

根據(jù)模擬退火算法思想[6]，本文設(shè)計(jì)的模擬退火算子如下所示：

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

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

3 Begin

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

5 Do

6 Do

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

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

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

10 if(Δ＜0)

11 Then S0=S1；

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

14 t=α×t；//α為降溫系數(shù)

15 While(不滿足終止條件)

16 Return S0；

17 End //其中tf、tp、Sf、α為用戶自定義參數(shù)，控制冷卻調(diào)度

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

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

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

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

（1）建立染色體子空間

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

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

（2）適應(yīng)度函數(shù)設(shè)計(jì)

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

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

（3）遺傳算子設(shè)計(jì)

1）選擇

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

2）交叉

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

Begin

1 隨機(jī)產(chǎn)生兩個交叉點(diǎn)，并定義兩點(diǎn)之間的區(qū)域?yàn)槠ヅ鋮^(qū)域

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

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

4 染色體合法化

End

3）變異

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

Begin

1 染色體的兩個基因位

2 將這兩個基因位上的基因值進(jìn)行交換

End

4）收斂性分析

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

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

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

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

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

證明：

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

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

因此y由x通過遺傳是可達(dá)的。

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

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

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

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

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

3Begin

4 i=0；

5 種群P(i)初始化；

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

7 評價(jià)種群P(i)；

8 While(終止條件不滿足)

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

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

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

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

13 評價(jià)種群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)；//頂點(diǎn)著色

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

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

4 算法模擬仿真與實(shí)驗(yàn)結(jié)果對比

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

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

表1 GA與HHGSAA同等條件下的實(shí)驗(yàn)結(jié)果數(shù)據(jù)對比

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

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

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

[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ìn)[J]. 軟件學(xué)報(bào), 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)泉,等. 遺傳算法 及其應(yīng)用[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調(diào)度算法研究[J]. 移動通信, 2015,39(8): 69-74.

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

2014-12-15

責(zé)任編輯：劉妙 liumiao@mbcom.cn