一種基于演化博弈的分簇協(xié)作路由算法

張 繼，張大方，謝 鯤，何施茗，喬 宏

(1.湖南大學(xué)信息科學(xué)與工程學(xué)院，湖南長沙 410082； 2.長沙理工大學(xué)計算機(jī)與通信學(xué)院，湖南長沙 410014)

?

一種基于演化博弈的分簇協(xié)作路由算法

張 繼1，張大方1，謝 鯤1，何施茗2，喬 宏1

(1.湖南大學(xué)信息科學(xué)與工程學(xué)院，湖南長沙 410082； 2.長沙理工大學(xué)計算機(jī)與通信學(xué)院，湖南長沙 410014)

現(xiàn)有的分簇協(xié)作路由沒有依據(jù)協(xié)作通信的特點(diǎn)選擇簇頭，也沒能根據(jù)簇頭節(jié)點(diǎn)的服務(wù)能力均衡簇成員負(fù)載，因而不能充分發(fā)揮協(xié)作通信能量高效的優(yōu)勢.本文提出了一種基于演化博弈的分簇協(xié)作路由算法CCREG.算法首先定義虛節(jié)點(diǎn)剩余能量作為簇頭確立的指標(biāo)，然后通過動態(tài)演化博弈為簇聯(lián)盟問題建立模型.簇成員節(jié)點(diǎn)選擇不同簇頭結(jié)成聯(lián)盟，可獲得不同的收益.收益由簇頭的能力、簇成員節(jié)點(diǎn)個數(shù)等因素決定.簇成員節(jié)點(diǎn)都可以根據(jù)自身得到的信息有限理性的選擇簇結(jié)成聯(lián)盟，直到網(wǎng)絡(luò)中所有節(jié)點(diǎn)改變簇聯(lián)盟都不能獲得更高的收益.實(shí)驗(yàn)結(jié)果表明，與協(xié)作多輸入多輸出路由算法CMIMO相比，CCREG算法的網(wǎng)絡(luò)生存周期在兩個簇頭情況下延長14%到70%，三個簇頭情況下延長5%到80%.

協(xié)作路由；演化博弈；分簇路由；網(wǎng)絡(luò)生存周期

1 引言

無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)(Wireless Sensor Networks，WSNs)通常是由小電池供電，為這些傳感器充電或更換電池是十分困難的：(1)傳感器被大規(guī)模部署后，重新收集回來充電需消耗大量的時間和費(fèi)用；(2)在某些環(huán)境中(如災(zāi)難區(qū)域)，傳感器部署環(huán)境的特殊性限制了節(jié)點(diǎn)的回收.因此，提高能量利用效率，延長網(wǎng)絡(luò)生存周期，一直是無線傳感器網(wǎng)絡(luò)研究的一個重要目標(biāo).

現(xiàn)有的無線傳輸大多數(shù)是基于單輸入單輸出 (Single Input and Single Output，SISO)傳輸方式，存在重傳率較高、能耗較高等缺點(diǎn).為了解決這個問題，研究者們提出了協(xié)作通信技術(shù).它利用無線廣播的優(yōu)勢，通過共享網(wǎng)絡(luò)中其他用戶的天線，形成虛擬天線陣列來實(shí)現(xiàn)數(shù)據(jù)的發(fā)送或接收，獲得空間分集增益，可以有效減少信息傳送的能量開銷，延長網(wǎng)絡(luò)生存周期.

協(xié)作路由[1]是聯(lián)合物理層協(xié)作通信技術(shù)和網(wǎng)絡(luò)層路由選擇技術(shù)的跨層路由方案.協(xié)作路由算法通過確立源節(jié)點(diǎn)到目的節(jié)點(diǎn)的傳輸路徑、為路徑上的節(jié)點(diǎn)選擇最優(yōu)的協(xié)作節(jié)點(diǎn)和設(shè)計功率分配算法，來最大化提高協(xié)作傳輸帶來的增益，完成有效節(jié)省網(wǎng)絡(luò)的能量消耗目標(biāo).現(xiàn)有的大部分協(xié)作路由算法[1～5]沒有充分挖掘無線網(wǎng)絡(luò)的節(jié)點(diǎn)分布、拓?fù)浣Y(jié)構(gòu)對協(xié)作路由的影響，沒有根據(jù)這些網(wǎng)絡(luò)特征進(jìn)行算法設(shè)計，對網(wǎng)絡(luò)能量消耗的降低有限.雖然存在少數(shù)分布式協(xié)作路由算法[3]，但是這些算法仍然存在路由效率低下，可擴(kuò)展性差的缺點(diǎn).

分簇路由能充分利用網(wǎng)絡(luò)節(jié)點(diǎn)分布和拓?fù)浣Y(jié)構(gòu)特征，其優(yōu)點(diǎn)已經(jīng)在無線傳感器網(wǎng)絡(luò)和Ad hoc網(wǎng)絡(luò)得到了廣泛的證實(shí).將分簇結(jié)構(gòu)和協(xié)作路由相結(jié)合，設(shè)計分簇協(xié)作路由算法，有利于提高無線網(wǎng)絡(luò)的可靠性，節(jié)省傳輸能量，延長網(wǎng)絡(luò)生命周期.

分簇協(xié)作路由需要解決的兩個關(guān)鍵問題是如何選擇簇頭和如何確定簇成員.現(xiàn)有的分簇協(xié)作路由[6,7]一般根據(jù)單個節(jié)點(diǎn)的剩余能量確定主簇頭，然后為主簇頭招募從簇頭，所招募的叢簇頭的能量無法保障；由于從簇頭的作用與主簇頭同樣重要，因此它們無法選擇出最優(yōu)的簇頭集.進(jìn)行簇成員確定時，成員節(jié)點(diǎn)均選擇信道最佳的簇頭聯(lián)盟，無法根據(jù)簇頭節(jié)點(diǎn)的服務(wù)能力均衡負(fù)載，勢必不能充分發(fā)揮協(xié)作通信能量高效的優(yōu)勢，對網(wǎng)絡(luò)生存周期提升有限.

為了均衡簇頭節(jié)點(diǎn)的能量開銷，延長網(wǎng)絡(luò)生存周期，我們將演化博弈[8]引入分簇協(xié)作路由中，提出了一種基于演化博弈的分簇協(xié)作路由算法(Cluster Cooperative Routing algorithm based on Evolutionary Game,CCREG).算法定義虛節(jié)點(diǎn)剩余能量作為簇頭確立的指標(biāo)，然后通過動態(tài)演化博弈為如何確定簇成員(簇聯(lián)盟)問題建立模型.剩余節(jié)點(diǎn)選擇不同簇頭結(jié)成聯(lián)盟，可獲得不同的收益，收益由簇頭的能力、簇成員節(jié)點(diǎn)個數(shù)等因素決定.每個節(jié)點(diǎn)都可以根據(jù)自身得到的信息有限理性的選擇簇結(jié)成聯(lián)盟，直到網(wǎng)絡(luò)中所有節(jié)點(diǎn)改變簇聯(lián)盟都不能獲得更高的收益.簇與簇之間通信通過簇頭的VMIMO (Virtual Multi-Input Multi-Output)協(xié)作傳輸進(jìn)行通信，在實(shí)際場景中可能由于簇節(jié)點(diǎn)數(shù)目不夠，達(dá)不到所設(shè)定需要的簇頭節(jié)點(diǎn)數(shù)目，簇間通信有可能退化為多對一(Virtual Multi-Input Single-Output,VMISO)或者一對多(Virtual Single-Input Multi-Output,VSIMO)，甚至是一對一(Single-Input Single-Output,SISO)通信模式.實(shí)驗(yàn)結(jié)果表明，與協(xié)作多輸入多輸出路由算法(Cooperative Multi-Input Multi-Output,CMIMO)相比，CCREG算法的網(wǎng)絡(luò)生存周期在兩個簇頭情況下延長14%到70%，三個簇頭情況下延長5%到80%.

2 簇聯(lián)盟演化博弈模型

我們用動態(tài)演化博弈為簇聯(lián)盟問題建立模型.簇聯(lián)盟問題是指在簇頭已經(jīng)確定的基礎(chǔ)上，如何確定簇成員的問題.一個簇頭被確定時，這個簇頭通信范圍所覆蓋的區(qū)域就是這個簇的服務(wù)區(qū).服務(wù)區(qū)內(nèi)的節(jié)點(diǎn)可以選擇加入這個簇，也就是與這個簇結(jié)成聯(lián)盟，加入后可獲得一定的收益.收益的多少由簇頭的能力和簇所包含的成員節(jié)點(diǎn)個數(shù)等因素決定.當(dāng)節(jié)點(diǎn)處于多個簇的服務(wù)區(qū)時，選擇不同的簇進(jìn)行聯(lián)盟，將獲得不同的收益.假設(shè)節(jié)點(diǎn)具有有限理性，那么每個節(jié)點(diǎn)都會根據(jù)自身得到的信息盡可能選擇收益大的簇結(jié)成聯(lián)盟.如果在相同服務(wù)區(qū)覆蓋別的節(jié)點(diǎn)收益高于自己的收益，節(jié)點(diǎn)可以選擇收益更高的簇結(jié)成聯(lián)盟.簇聯(lián)盟演化博弈的演化均衡解是：網(wǎng)絡(luò)中所有節(jié)點(diǎn)改變簇聯(lián)盟都不能獲得更高的收益.

本章中首先說明簇聯(lián)盟演化博弈中的參與者、群組和策略，然后設(shè)計收益函數(shù)和更新的復(fù)制動態(tài)方程，最后分析演化博弈模型的均衡性.

2.1 參與者、群組和策略

參與者(players)：參與者是未被選為簇頭的剩余節(jié)點(diǎn)，它們需要為自己選擇一個簇進(jìn)行聯(lián)盟.對于每一個簇的簇頭，都有一定的簇內(nèi)通信半徑.我們把簇頭通信半徑所覆蓋的區(qū)域稱為該簇的服務(wù)區(qū).對于在簇服務(wù)區(qū)內(nèi)的參與者，它們都可以選擇這個簇，成為這個簇的成員節(jié)點(diǎn).反之，對于某一個參與者，它會被一個或者多個簇服務(wù)區(qū)所覆蓋.對于只被一個服務(wù)區(qū)覆蓋的參與者，它只有唯一簇頭可以選擇；而被多個服務(wù)區(qū)覆蓋的參與者，就有多個選擇權(quán).如圖1中，區(qū)域a1中的節(jié)點(diǎn)只能選擇簇C1結(jié)成聯(lián)盟，所以這些節(jié)點(diǎn)并不參與演化博弈；區(qū)域a2中的參與者可選擇簇C1或C2來獲得更高的收益.

群組(population)：被相同服務(wù)區(qū)覆蓋的參與者都擁有相同的策略集，我們稱這些參與者所構(gòu)成的集合稱為群組.如圖1，區(qū)域a1中的參與者是一個群組，區(qū)域a2中的參與者組成了另外一個群組.

策略(strategy)：每個參與者選擇不同簇頭結(jié)成簇聯(lián)盟稱之為該參與者采取的策略.如圖1中，區(qū)域a2中參與者的策略集是{C1,C2}，區(qū)域a4中參與者的策略集是{C2,C3}.

收益(payoff)：收益是參與者獲得的凈效用(net utility)，由所選擇的簇頭節(jié)點(diǎn)提供.

2.2 收益函數(shù)

(1)

其中，區(qū)域a是簇i的服務(wù)區(qū)的組成部分，Ni是簇i的節(jié)點(diǎn)總數(shù)，Ui(Ni)是效用函數(shù)，Pi(Ni)是價格函數(shù).在以最大化網(wǎng)絡(luò)生存周期為目的建立的演化博弈模型中，效用函數(shù)Ui(Ni)設(shè)定為簇i生存周期的估計值，通過式(2)計算得到.

簇i內(nèi)的節(jié)點(diǎn)總數(shù)Ni是簇頭的數(shù)目和所有區(qū)域內(nèi)選擇簇i的節(jié)點(diǎn)數(shù)目之和，通過式(3)計算得到.

(3)

當(dāng)一個簇的簇頭節(jié)點(diǎn)的能量耗盡時，這個簇就死亡了，所以所有選擇簇i聯(lián)盟的節(jié)點(diǎn)都有相同的收益函數(shù)πi，定義為式(4).

(4)

因此我們可以得出不同區(qū)域如am和al選擇簇i聯(lián)盟的收益函數(shù)均相等，可表示式(5).

(5)

以圖1為例，a2和a4區(qū)域選擇簇C2的效用相等，

(6)

根據(jù)式(3)，簇C2內(nèi)的節(jié)點(diǎn)總數(shù)NC2由下式計算得到，代入式(4)中，可以計算得到a2和a4區(qū)域選擇簇C2的效用值.

(7)

同樣的方法可以計算πC1，πC3和πC4.

2.3 復(fù)制動態(tài)公式

本文把參與者選擇不同簇聯(lián)盟(即采用不同策略)的過程設(shè)計為演化博弈.這個博弈是反復(fù)的，在某個時間段里，參與者觀察同群組中其他節(jié)點(diǎn)的收益，在下個時間段這個參與者可以改變自己的策略以獲得更高的收益.在這段時間里，參與者策略的變化率由復(fù)制動態(tài)方程決定，可以表示為：

(9)

3 基于演化博弈的分簇協(xié)作路由算法設(shè)計

3.1 算法概述

基于演化博弈的分簇協(xié)作路由算法CCREG是一個分布式的自適應(yīng)分簇路由算法.CCREG算法以節(jié)省無線傳感網(wǎng)絡(luò)傳輸能量，延長網(wǎng)絡(luò)生存周期為目的.它采用動態(tài)簇構(gòu)建算法把網(wǎng)絡(luò)劃分成N個簇，每個簇選定一個主簇頭和k-1個從簇頭.簇頭節(jié)點(diǎn)集合構(gòu)成VMIMO天線陣列與其他簇通過協(xié)作通信傳輸數(shù)據(jù).簇構(gòu)建算法決定了分簇網(wǎng)絡(luò)的基礎(chǔ)特性，對簇內(nèi)通信與簇間通信的開銷起決定性的作用.簇內(nèi)通信和簇間協(xié)作通信作為分簇協(xié)作路由的組成部分，我們將沿用文獻(xiàn)[7]提出的方法.

簇構(gòu)建算法分為鄰居發(fā)現(xiàn)，簇頭確立和簇聯(lián)盟三個步驟.鄰居發(fā)現(xiàn)收集周圍鄰居狀態(tài)信息，以此作為確定簇頭的依據(jù).與其他簇頭確立算法不同，我們以虛節(jié)點(diǎn)能量作為確立簇頭的標(biāo)準(zhǔn).CCREG算法最大的貢獻(xiàn)是簇聯(lián)盟方案.

3.2 鄰居發(fā)現(xiàn)

在鄰居發(fā)現(xiàn)中，節(jié)點(diǎn)通過Hello消息進(jìn)行信息交互.Hello消息包括節(jié)點(diǎn)自身的ID、剩余能量、鄰居表和虛節(jié)點(diǎn)剩余能量.

虛節(jié)點(diǎn)剩余能量是我們設(shè)計的一個新的指標(biāo)，將作為簇頭選擇的標(biāo)準(zhǔn).每個節(jié)點(diǎn)在鄰居表中選擇剩余能量最高的k-1個鄰居節(jié)點(diǎn)(k為算法設(shè)置的簇頭個數(shù))作為該節(jié)點(diǎn)的備選伙伴.將該節(jié)點(diǎn)u與其備選伙伴{vk-1,vk-2,…,v1}組成的節(jié)點(diǎn)集定義成虛節(jié)點(diǎn)u′.虛節(jié)點(diǎn)u′的剩余能量等于節(jié)點(diǎn)集合的平均剩余能量(Ru+Rv-k-1+…+Rv-1)/k.

與其他無線路由協(xié)議發(fā)現(xiàn)鄰居的方法一樣，當(dāng)節(jié)點(diǎn)v成功申請到信道，它就以一個固定的功率發(fā)送一個Hello消息給它的鄰居，其中Hello消息包含節(jié)點(diǎn)v的ID、剩余能量、鄰居表和虛節(jié)點(diǎn)v′的剩余能量.收到這一消息的節(jié)點(diǎn)u檢查自己的鄰居表是否含有節(jié)點(diǎn)v的項.如果沒有，則將節(jié)點(diǎn)v及其相關(guān)信息添加到鄰居表中；否則，找到節(jié)點(diǎn)v的項，比較表中信息，如不同則更新.

3.3 簇頭確立

在本文的簇協(xié)作路由模型中，簇頭包括主簇頭和從簇頭，且兩者在數(shù)據(jù)聚合和轉(zhuǎn)發(fā)中同等重要.另外，簇頭節(jié)點(diǎn)比成員節(jié)點(diǎn)要完成更多的工作(比如數(shù)據(jù)匯合，轉(zhuǎn)發(fā)和分發(fā)等)，因而簇頭節(jié)點(diǎn)的剩余能量是一個簇生存的關(guān)鍵.基于以上兩個原因，我們把虛節(jié)點(diǎn)剩余能量作為簇頭確立的指標(biāo).

以虛節(jié)點(diǎn)剩余能量為指標(biāo)的簇頭確立算法步驟如下：

步驟1 所有節(jié)點(diǎn)都被初始化成“待定”狀態(tài)；

步驟2 網(wǎng)絡(luò)中的每個“待定”節(jié)點(diǎn)u均與其“待定”鄰居節(jié)點(diǎn)比較對應(yīng)的虛節(jié)點(diǎn)剩余能量.若虛節(jié)點(diǎn)u′的剩余能量比所有“待定”狀態(tài)下鄰居節(jié)點(diǎn)所對應(yīng)的虛節(jié)點(diǎn)剩余能量都高，則確立節(jié)點(diǎn)u為“主簇頭”，節(jié)點(diǎn)u的備選伙伴確立為“從簇頭”；

步驟3 主簇頭和從簇頭廣播簇頭信息給各自的鄰居節(jié)點(diǎn)，收到消息的鄰居節(jié)點(diǎn)把自己的狀態(tài)設(shè)定為“成員”；

步驟4 對于剩下的“待定”節(jié)點(diǎn)，重復(fù)簇頭確立方法的步驟2和步驟3，直到確定所有節(jié)點(diǎn)的狀態(tài).

3.4 簇聯(lián)盟

簇聯(lián)盟的主要工作是為每一個“成員”狀態(tài)的節(jié)點(diǎn)確定一個簇聯(lián)盟，這一步也是整個算法的核心.

簇聯(lián)盟算法如算法1中所示.每個“成員”節(jié)點(diǎn)初始時都隨機(jī)選擇一個簇聯(lián)盟.初始化完成后，進(jìn)入動態(tài)演化博弈階段，每個獨(dú)立的節(jié)點(diǎn)都通過博弈尋找收益更高的簇聯(lián)盟.簇頭節(jié)點(diǎn)通過式(4)計算出簇內(nèi)成員節(jié)點(diǎn)可得到的收益，并廣播給所有成員節(jié)點(diǎn).節(jié)點(diǎn)不但能收到各自本身的收益，也能觀察得到同區(qū)域內(nèi)其他節(jié)點(diǎn)的收益.通過式(9)計算能得到該區(qū)域的平均收益，如果節(jié)點(diǎn)收益小于平均收益，則進(jìn)行策略調(diào)整隨機(jī)選擇收益高于平均收益的簇聯(lián)盟.所有成員節(jié)點(diǎn)做出策略調(diào)整后，簇頭節(jié)點(diǎn)重新計算收益，成員節(jié)點(diǎn)再進(jìn)行策略調(diào)整，直到達(dá)到演化博弈均衡點(diǎn).

算法1 簇聯(lián)盟算法

// 初始化

1.所有節(jié)點(diǎn)隨機(jī)選擇簇聯(lián)盟.

Loop

3.foru∈成員節(jié)點(diǎn)

// 以下步驟，每個成員節(jié)點(diǎn)同步進(jìn)行

8. end if

9. end if

10.end for

11.end Loop

4 仿真實(shí)驗(yàn)

我們在Matlab中通過仿真實(shí)驗(yàn)來說明所提算法的性能.首先仿真演化博弈過程來分析演化博弈的均衡點(diǎn)，然后實(shí)驗(yàn)比較算法的性能，獲得的實(shí)驗(yàn)結(jié)果表明我們算法能有效提高網(wǎng)絡(luò)生存周期.

4.1 演化均衡性分析

從實(shí)驗(yàn)中可以得出，不管參與者選擇各個簇聯(lián)盟的初始化比率是多少，都能通過演化博弈達(dá)到均衡點(diǎn).

4.2 性能分析

4.2.1 實(shí)驗(yàn)配置

我們在不同簇頭節(jié)點(diǎn)個數(shù)下，將CCREG與協(xié)作MIMO路由算法CMIMO[7]進(jìn)行比較.

實(shí)驗(yàn)中數(shù)據(jù)將按輪進(jìn)行傳輸.定義在一輪的數(shù)據(jù)傳輸過程中，所有成員節(jié)點(diǎn)按順序隨機(jī)選擇一個目的節(jié)點(diǎn)進(jìn)行一個單位的數(shù)據(jù)傳輸.所有節(jié)點(diǎn)傳輸完成后，一輪傳輸結(jié)束，進(jìn)入下一輪的傳輸.比較的指標(biāo)為不同路由選擇方式下獲得的網(wǎng)絡(luò)生存周期.網(wǎng)絡(luò)生存周期為網(wǎng)絡(luò)開始到第一個節(jié)點(diǎn)能量耗盡之間的數(shù)據(jù)傳輸?shù)妮啍?shù).為了比較網(wǎng)絡(luò)的生存周期，需要根據(jù)功率分配方式[10]確定數(shù)據(jù)傳輸時所消耗的能量.實(shí)驗(yàn)中，我們采用文獻(xiàn)[2]定義能量模型.采用VSISO和VSIMO通信模型的能量開銷為式(10)所示.

(10)

其中，s為發(fā)送節(jié)點(diǎn)，T為接收節(jié)點(diǎn)集，LsT為s發(fā)送給節(jié)點(diǎn)集T所需要的能量，Pη是接收端噪聲的方差，SNRmin為最小信噪比大于門限值(當(dāng)接收端的信噪比大于門限值時，接收端就能正確解碼)，αst是節(jié)點(diǎn)s到節(jié)點(diǎn)t的功率損耗因子.

采用VMISO和VMIMO協(xié)作通信模型的能量開銷為式(11)、(12)所示.

(11)

s.t. |ωs|2≤Pγs,?s∈S

(12)

節(jié)點(diǎn)s直接傳輸一個單位數(shù)據(jù)所需要的能量為

(13)

其中，D表示發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)間的距離.

實(shí)驗(yàn)場景為一定區(qū)域內(nèi)隨機(jī)分布節(jié)點(diǎn)，節(jié)點(diǎn)s和t之間的功率損耗因子αst與它們的距離的平方成反比.簇內(nèi)通信的最大通信半徑為160m，簇間通信半徑設(shè)定為簇內(nèi)通信的2.5倍.每個節(jié)點(diǎn)都可以調(diào)整發(fā)送功率以調(diào)整通信半徑.節(jié)點(diǎn)的初始能量為1.實(shí)驗(yàn)中，節(jié)點(diǎn)按輪進(jìn)行數(shù)據(jù)傳輸，直至第一個節(jié)點(diǎn)能量耗盡網(wǎng)絡(luò)死亡.在相同的網(wǎng)絡(luò)拓?fù)渑c節(jié)點(diǎn)初始狀態(tài)下，順序執(zhí)行CMIMO和CCREG兩種路由方式來獲得的生存周期.我們在不同節(jié)點(diǎn)密度，網(wǎng)絡(luò)大小以及簇內(nèi)通信半徑條件下評估算法性能.每組試驗(yàn)中，我們都會對比兩個和三個簇頭下兩種路由方式的性能.

4.2.2 節(jié)點(diǎn)密度

在固定大小的區(qū)域(320m*320m)內(nèi)隨機(jī)分布40，80，120，160，200和240個節(jié)點(diǎn)，對比兩個和三個簇頭下兩種路由算法的網(wǎng)絡(luò)生存周期.在這組實(shí)驗(yàn)中簇內(nèi)通信半徑為100m，簇間通信半徑為250m.

圖3是在不同節(jié)點(diǎn)密度網(wǎng)絡(luò)中的網(wǎng)絡(luò)生存周期對比圖，縱坐標(biāo)是網(wǎng)絡(luò)生存周期，即網(wǎng)絡(luò)死亡前已完成的數(shù)據(jù)傳輸?shù)妮啍?shù)；橫坐標(biāo)是節(jié)點(diǎn)密度，即固定區(qū)域內(nèi)隨機(jī)分布的節(jié)點(diǎn)個數(shù).隨著網(wǎng)絡(luò)密度的增加，網(wǎng)絡(luò)中數(shù)據(jù)傳輸量增加，網(wǎng)絡(luò)生存周期隨之降低.但不管在哪種密度下，CCREG算法的網(wǎng)絡(luò)生存周期都比CMIMO算法長.隨著網(wǎng)絡(luò)密度的增加，CCREG3算法的網(wǎng)絡(luò)生存周期比CMIMO3算法分別延長36%、24%、14%、25%、72%和70%；使用CCREG2算法的網(wǎng)絡(luò)生存周期比CMIMO2算法分別延長5%、40%、23%、59%、48%和80%.在高密度網(wǎng)絡(luò)中，CCREG算法的性能更加優(yōu)秀，這是因?yàn)橛懈嗟墓?jié)點(diǎn)能參加博弈.在240節(jié)點(diǎn)的網(wǎng)絡(luò)中，CCREG算法的網(wǎng)絡(luò)生存周期比兩個簇頭和三個簇頭的CMIMO算法分別延長70%和80%.

4.2.3 網(wǎng)絡(luò)大小

在不同網(wǎng)絡(luò)區(qū)域(240m*240m，320m*320m，400m*400m和480m*480m區(qū)域)內(nèi)隨機(jī)分布160個節(jié)點(diǎn)，簇內(nèi)通信半徑為100m，簇間通信半徑為250m.

圖4是不同網(wǎng)絡(luò)大小的網(wǎng)絡(luò)生存周期對比圖，縱坐標(biāo)是網(wǎng)絡(luò)生存周期，橫坐標(biāo)為網(wǎng)絡(luò)大小.隨著網(wǎng)絡(luò)區(qū)域擴(kuò)大，網(wǎng)絡(luò)被劃分為更多的簇，需要部署更多的簇頭節(jié)點(diǎn)，網(wǎng)絡(luò)生存周期相應(yīng)延長.兩個簇頭的情況下，CCREG2算法比CMIMO2算法的生命周期分別延長49%、59%、55%和53%.三個簇頭的情況下，CCREG3算法比CMIMO3算法的生命周期分別延長14%、25%、34%和40%.

4.2.4 簇內(nèi)通信半徑

在固定大小的區(qū)域(320m*320m)內(nèi)隨機(jī)分布160個節(jié)點(diǎn)，設(shè)定簇間通信半徑是簇內(nèi)通信半徑的2.5倍，簇內(nèi)通信半徑從60m增加到160m.

圖5是不同的簇內(nèi)通信半徑下的網(wǎng)絡(luò)生存周期圖，縱坐標(biāo)是網(wǎng)絡(luò)生存周期，橫坐標(biāo)是簇內(nèi)通信半徑.網(wǎng)絡(luò)生存周期隨著簇內(nèi)通信半徑增加而減少.這是因?yàn)榇貎?nèi)通信半徑增加，能形成的簇的個數(shù)減少，使得為網(wǎng)絡(luò)服務(wù)的簇頭個數(shù)減少，從而縮短了網(wǎng)絡(luò)生存周期.隨著通信半徑增加，CCREG2算法比CMIMO2算法的生命周期分別延長77%、64%、59%、33%、69%和11%.CCREG3算法比CMIMO3算法的生命周期分別延長41%、37%、25%、23%、14%和20%.

5 結(jié)論

針對分簇協(xié)作路由的簇頭選擇和成員節(jié)點(diǎn)確定問題，本文提出了一種基于演化博弈的分簇協(xié)作路由算法CCREG.算法定義虛節(jié)點(diǎn)剩余能量作為簇頭確立的指標(biāo)，然后通過動態(tài)演化博弈為簇聯(lián)盟問題建立模型.剩余節(jié)點(diǎn)選擇不同簇頭結(jié)成聯(lián)盟，可獲得不同的收益，收益由簇頭的能力、簇成員節(jié)點(diǎn)個數(shù)等因素決定.每個節(jié)點(diǎn)都可以根據(jù)自身得到的信息有限理性的選擇簇結(jié)成聯(lián)盟，直到網(wǎng)絡(luò)中所有節(jié)點(diǎn)改變簇聯(lián)盟都不能獲得更高的收益.實(shí)驗(yàn)結(jié)果表明，與CMIMO相比，CCREG算法的網(wǎng)絡(luò)生存周期在兩個簇頭情況下延長14%到70%，三個簇頭情況下延長5%到80%.

[1]Khandani A E,Abounadi J,Modiano E,et al.Cooperativerouting in static wireless networks[J].IEEE Transactions on Communications,2007,55(11):1-23.

[2]LI F,WU K,LIPPMAN A.Energy-efficient cooperative routing in multi-hop wireless ad hoc networks[A].IEEE International Performance,Computing,and Communications Conference[C].Piscataway,NJ:IEEE Press,2006.215-222.

[3]IBRAHIM A S,HAN Z,LIU KJR.Distributed energy-efficient cooperative routing in wireless networks[J].IEEE Transactions on Wireless Communications,2008,7(10):3930-3941.

[4]ELHAWARY M,HAAS Z.Energy-efficient protocol for cooperative networks[J].IEEE/ACM Trans Netw,2011,19(2):561-574.

[5]ZHANG J,ZHANG D,Xie K,et al.A cooperative routing algorithm for maximizing network lifetime[A].Advances in Wireless Sensor Networks[C].Huangshan,China Springer Berlin Heidelberg,2013.665-675.

[6]謝鯤,孫家奇,龔闖,文吉剛.無線多跳網(wǎng)絡(luò)分簇協(xié)作路由算法[J].小型微型計算機(jī)系統(tǒng),2013,34(2):210-215.

XIE Kun，SUN Jia-qi，GONG Chuang，WEN Ji-gang.A cluster cooperative routing algorithm in wireless multi-hop networks[J].Journal of Chinese Computer Systems,2013,34(2):210-215.(in Chinese)

[7]Krunz M,Siam M Z,Nguyen D N.Clustering and power management for virtual MIMO communications in wireless sensor networks[J].Ad Hoc Networks,2013,11(5):1571-1587.

[8]SMITH J M.Evolution and the Theory of Games[M].New York:Cambridge University Press,1982.

[9]NIYATO D,HOSSAIN E.Dynamics of network selection in heterogeneous wireless networks:An evolutionary game approach[J].IEEE Transactions on Vehicular Technology,2009,58(4):2008-2017.

[10]王俊波,曹哲,陳明,焦媛.無線并行放大轉(zhuǎn)發(fā)中繼傳輸中基于信噪比的功率分配研究[J].電子學(xué)報,2011,39(7):1663-1667.

WANG Jun-bo,CAO Zhe,CHEN Ming,JIAO Yuan.SNR-Based power allocation in wireless parallel amplify-and-forward relay transmissions[J].Acta Electronica Sinica,2011,39(7):1663-1667.(in Chinese)

張 繼 男，1984年生，湖南長沙人，湖南大學(xué)博士生.主要研究方向?yàn)閰f(xié)作路由、無線傳感網(wǎng).

E-mail:tosky984@163.com

張大方 男，1959年生，上海人，湖南大學(xué)教授、博士生導(dǎo)師.主要研究方向?yàn)榭尚畔到y(tǒng)與網(wǎng)絡(luò)、軟件容錯.

E-mail:dfzhang@hnu.edu.cn

謝 鯤 女，1978年生，湖南黔陽人，湖南大學(xué)教授，博士生導(dǎo)師.主要研究方向?yàn)榉植际接嬎?、協(xié)作路由.

E-mail:xiekun@hnu.edu.cn

何施茗 女，1986年生，湖南本州人，博士，長沙理工大學(xué)講師.主要研究方向?yàn)闄C(jī)會路由.

E-mail:heshiming-hsm@163.com

喬 宏 男，1984年生，湖南岳陽人，湖南大學(xué)博士生.主要研究方向?yàn)闊o線Mesh網(wǎng)、協(xié)作路由.

E-mail:hqiao@hnu.edu.cn

A Cluster Cooperative Routing Algorithm Based on Evolutionary Game

ZHANG Ji1,ZHANG Da-fang1,XIE Kun1,HE Shi-ming2,QIAO Hong1

(1.SchoolofInformationScienceandEngineering,HunanUniversity,Changsha,Hunan410082,China；2.SchoolofComputerandCommunicationEngineering,ChangshaUniversityofScienceandTechnology,Changsha,Hunan410004,China)

Since the existing cluster cooperative routing algorithms select cluster heads without considering the characteristics of cooperative communication and don't balance the cluster member according to the capacity of cluster heads,they can't fully exploit the advantage of cooperative communication on saving energy consumption.A cluster cooperative routing algorithm based on evolutionary game (CCREG) is proposed.Firstly,the energy of virtual node is the metric of cluster head selection.Secondly,the model of cluster membership based on the evolutionary game is formulated,where member nodes select different clusters to join in leading to different payoffs which are decided by the capacity of the cluster head and the number of cluster members.Each member node selects a cluster to join in,till it can’t achieve more payoffs by changing the cluster to join in.The experiment shows that CCREG can prompt the network lifetime by 14%～70% with two cluster headers,by 5%～80% with three cluster headers,compared with cooperative multi-input multi-output routing (CMIMO).

cooperative routing;the evolutionary game;cluster routing;network lifetime

2014-12-30;

2015-05-08;責(zé)任編輯：梅志強(qiáng)

國家973重點(diǎn)基礎(chǔ)研究發(fā)展計劃(No.2012CB315805);國家自然科學(xué)基金(No.61173167，No.61472130)

TP393

A

0372-2112 (2016)09-2158-06

??學(xué)報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.020