宋 歡，王建娜

（蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070）

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN，簡(jiǎn)稱傳感器網(wǎng)絡(luò)）由大量隨機(jī)分布的低成本微型傳感器節(jié)點(diǎn)組成，協(xié)作地對(duì)所觀測(cè)的區(qū)域進(jìn)行信息采集、數(shù)據(jù)融合和數(shù)據(jù)轉(zhuǎn)發(fā)，目前已廣泛應(yīng)用于智能交通、醫(yī)療救護(hù)、環(huán)境監(jiān)測(cè)和工業(yè)自動(dòng)化等諸多領(lǐng)域，受到了工業(yè)界和學(xué)術(shù)界的普遍重視[1]。圖1為無(wú)線傳感器網(wǎng)絡(luò)的具體結(jié)構(gòu)。

網(wǎng)絡(luò)中的節(jié)點(diǎn)（微型傳感器）體積小。通過(guò)圖1可以看出，節(jié)點(diǎn)由電池供能，能量非常有限，且當(dāng)電池能量消耗完時(shí)不能進(jìn)行充電或是更換電池[2]。因此，無(wú)線傳感器網(wǎng)絡(luò)的能耗問(wèn)題成為研究的一個(gè)熱點(diǎn)。

圖1 無(wú)線傳感器網(wǎng)絡(luò)構(gòu)成

無(wú)線傳感器網(wǎng)絡(luò)中，數(shù)據(jù)轉(zhuǎn)發(fā)是影響整體能耗的一個(gè)關(guān)鍵因素。因?yàn)楣?jié)點(diǎn)能量有限，節(jié)點(diǎn)盡可能只發(fā)送自身數(shù)據(jù)，拒絕轉(zhuǎn)發(fā)其他節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)以節(jié)省自身能量。這是一種不合作關(guān)系，體現(xiàn)了節(jié)點(diǎn)的“自私性”。但是，為了保證網(wǎng)絡(luò)的整體連通性，節(jié)點(diǎn)之間必須進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，才能將信息傳送到目的地，這樣節(jié)點(diǎn)之間又存在一種合作關(guān)系，而這種合作稱之為聯(lián)盟。

博弈論是數(shù)學(xué)領(lǐng)域的一個(gè)新型分支，主要研究具有相互依賴行為的參與者決策選擇，在現(xiàn)實(shí)生活的各大領(lǐng)域有著廣泛應(yīng)用[3]。博弈論是研究在同一種情況下具有競(jìng)爭(zhēng)關(guān)系、存在利益沖突的各個(gè)成員為了提高自身的收益而進(jìn)行的一系列選擇的過(guò)程。具有這種競(jìng)爭(zhēng)利益關(guān)系的個(gè)體稱之為參與者，個(gè)體成員進(jìn)行的一系列選擇稱之為策略。博弈根據(jù)成員之間可能存在的關(guān)系可以分為合作博弈和非合作博弈。對(duì)于非合作博弈，主要是指?jìng)€(gè)體成員盡最大可能去擴(kuò)大自身收益，同時(shí)減少競(jìng)爭(zhēng)者的收益，強(qiáng)調(diào)自身收益。大多數(shù)情況下，合作博弈也稱為聯(lián)盟博弈，強(qiáng)調(diào)的是參與博弈的個(gè)體成員之間有時(shí)候?yàn)榱说玫礁蟮氖找妫瑫?huì)選擇有相同目標(biāo)的成員進(jìn)行合作。建立聯(lián)盟，使聯(lián)盟的收益盡可能大，強(qiáng)調(diào)的是整體收益。本文總結(jié)了博弈論在數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制中的拍賣博弈和聯(lián)盟博弈兩種模型。

1 拍賣博弈

不完全信息博弈，是博弈的個(gè)體成員之間對(duì)彼此的各種信息不完全了解的一種博弈。其中，最常見(jiàn)的是拍賣博弈。拍賣博弈是一種非合作博弈。拍賣也可以理解為買方的競(jìng)買，是一個(gè)群體進(jìn)行買賣交易的過(guò)程。拍賣的形式各式各樣，規(guī)則也是千差萬(wàn)別。例如，英式拍賣，拍賣過(guò)程有時(shí)間限制，在截止時(shí)間出價(jià)最高的買家可以獲得此物，但當(dāng)出價(jià)最高方的價(jià)格低于賣方對(duì)此物的估價(jià)時(shí)，賣方可以選擇不出售；荷氏拍賣，是將競(jìng)拍物品的價(jià)格不斷降低，直至有人愿意出價(jià)為止；暗標(biāo)拍賣，指的是想?yún)⑴c競(jìng)拍的賣方根據(jù)自身的情況和對(duì)競(jìng)標(biāo)的其他對(duì)手進(jìn)行一個(gè)預(yù)估給出報(bào)價(jià)，報(bào)價(jià)會(huì)在一個(gè)時(shí)間同時(shí)公開(kāi)，出價(jià)最高的買方得標(biāo)，而出價(jià)的其他買方不會(huì)知道中標(biāo)的買方的最終收益[4]。除了這些拍賣博弈，還有好多拍賣方式。

文獻(xiàn)[5]提出，無(wú)線傳感器網(wǎng)絡(luò)的某個(gè)節(jié)點(diǎn)能量即將耗盡時(shí)，將自身的任務(wù)信息散布出去，各節(jié)點(diǎn)通過(guò)協(xié)商決定哪個(gè)節(jié)點(diǎn)繼續(xù)任務(wù)并完成[5]。在數(shù)據(jù)包轉(zhuǎn)發(fā)機(jī)制中，由于傳感器節(jié)點(diǎn)的“自私性”，節(jié)點(diǎn)不愿轉(zhuǎn)發(fā)來(lái)自于其他節(jié)點(diǎn)的數(shù)據(jù)。文獻(xiàn)[6]提出了基于拍賣博弈建立了不完全信息的數(shù)據(jù)轉(zhuǎn)發(fā)路徑，并提出了對(duì)轉(zhuǎn)發(fā)節(jié)點(diǎn)價(jià)格進(jìn)行博弈進(jìn)而選擇的算法[6]。其實(shí)，該算法可以理解為進(jìn)行的是暗標(biāo)拍賣。

整個(gè)傳輸路徑建立的過(guò)程中，為了避免能量較低和建立路徑較遠(yuǎn)的節(jié)點(diǎn)當(dāng)選為下一跳路由，可將剩余能量、節(jié)點(diǎn)到Sink節(jié)點(diǎn)的跳數(shù)作為參考因素。在數(shù)據(jù)包轉(zhuǎn)發(fā)過(guò)程中，將發(fā)送數(shù)據(jù)的節(jié)點(diǎn)看作拍賣博弈的買方，將該節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)作為賣方，則賣方節(jié)點(diǎn)根據(jù)自身的剩余能量以及到Sink節(jié)點(diǎn)的跳數(shù)給出自己的價(jià)格，而買方會(huì)根據(jù)價(jià)格等因素決定下一跳節(jié)點(diǎn)。所選的賣方節(jié)點(diǎn)會(huì)成為新的買方，對(duì)下一跳路由節(jié)點(diǎn)進(jìn)行選擇。重復(fù)該過(guò)程，建立一條能耗低、可靠性高的傳輸路徑。博弈過(guò)程中，引用了基于獎(jiǎng)勵(lì)機(jī)制的博弈模型，即Sink節(jié)點(diǎn)會(huì)給買方一定的價(jià)格作為它數(shù)據(jù)發(fā)送消耗能量的一個(gè)補(bǔ)償，而買方通過(guò)拍賣博弈從賣方那里購(gòu)買需要的服務(wù)，一直重復(fù)該過(guò)程，直到數(shù)據(jù)到達(dá)目標(biāo)節(jié)點(diǎn)。

通過(guò)分析可能鏈路的質(zhì)量，需對(duì)下一跳節(jié)點(diǎn)進(jìn)行一個(gè)選擇。要考慮節(jié)點(diǎn)自身的能量和節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的跳數(shù)，對(duì)鏈路質(zhì)量定義如下：

ei(t)表示節(jié)點(diǎn)i在t時(shí)刻的自身剩余能量；hij表示節(jié)點(diǎn)i在t時(shí)刻到節(jié)點(diǎn)j的跳數(shù)。

節(jié)點(diǎn)在進(jìn)行拍賣博弈時(shí)如何確定自身收益，文章給出了如下定義，即節(jié)點(diǎn)a在時(shí)刻t的收益函數(shù)：

αa(t)是節(jié)點(diǎn)在t時(shí)刻數(shù)據(jù)包轉(zhuǎn)發(fā)成功的概率；b是sink節(jié)點(diǎn)支付給節(jié)點(diǎn)a的價(jià)格；esa(t)是節(jié)點(diǎn)a在t時(shí)刻發(fā)送數(shù)據(jù)所消耗的能量；φ(a, j)是節(jié)點(diǎn)a與節(jié)點(diǎn)j的交易價(jià)格。

在拍賣博弈模型中，節(jié)點(diǎn)通過(guò)對(duì)所有可能的鏈路的質(zhì)量和其他等因素的分析，對(duì)自身數(shù)據(jù)進(jìn)行拍賣。在買方節(jié)點(diǎn)中選擇下一跳節(jié)點(diǎn)，并獲得自身收益，選擇的下一條買方節(jié)點(diǎn)會(huì)作為新的賣方節(jié)點(diǎn)繼續(xù)該過(guò)程，直至將數(shù)據(jù)傳輸至目標(biāo)節(jié)點(diǎn)。拍賣的過(guò)程中，充分考慮了節(jié)點(diǎn)的剩余能量和跳數(shù)，因此可以選擇出一條能耗低、可靠性高的路徑。

2 聯(lián)盟博弈

在一個(gè)競(jìng)爭(zhēng)過(guò)程中，當(dāng)參與者較多（參與者大于2）時(shí)，為了減少自身消耗，提高自身收益，參與者在進(jìn)行競(jìng)爭(zhēng)的同時(shí)，有可能選擇與有著共同目標(biāo)的其他參與者合作，使合作的整體獲得盡可能大的整體效益。競(jìng)爭(zhēng)關(guān)系結(jié)束后，再對(duì)整體效益進(jìn)行分配，從而提高參與者自身的收益[7]，這種關(guān)系稱之為聯(lián)盟博弈。即將選擇合作的參與者們看成是一個(gè)聯(lián)盟，與其他聯(lián)盟之間進(jìn)行競(jìng)爭(zhēng)。這里建立一個(gè)參與者為N人的一個(gè)博弈N={n1,n2,n3,…,nn}，v表示效益函數(shù)，建立一個(gè)聯(lián)盟U，U∈2N,v(U)則為這個(gè)聯(lián)盟的收益[8]。

聯(lián)盟博弈的應(yīng)用有以下兩個(gè)約束條件：

（1）參與者之間的合作關(guān)系建立后，聯(lián)盟產(chǎn)生的整體效益必須大于參與者單獨(dú)行動(dòng)時(shí)產(chǎn)生的個(gè)人效益之和，即：

（2）在建立的聯(lián)盟內(nèi)部，每個(gè)參與者最終分配的效益必須大于參與者單獨(dú)行動(dòng)時(shí)的收益。

聯(lián)盟內(nèi)的成員對(duì)聯(lián)盟的整體收益如何進(jìn)行再分配，常用的幾種方式如下。

聯(lián)盟建立后，沒(méi)有成員加入或者退出，聯(lián)盟處于一個(gè)穩(wěn)定的狀態(tài)。將穩(wěn)定狀態(tài)下的聯(lián)盟叫做具有可傳遞性（TU）聯(lián)盟核，描述如下：

聯(lián)盟內(nèi)的成員所獲得收益不小于成員單獨(dú)行動(dòng)時(shí)所獲得的收益，則有：

θi表示聯(lián)盟內(nèi)成員對(duì)聯(lián)盟整體收益分配時(shí)的收益。

如果聯(lián)盟的可傳遞性核為空或者很大時(shí)且無(wú)法選擇恰當(dāng)?shù)氖找娣峙浼蠒r(shí)，則對(duì)于每個(gè)聯(lián)盟成員i∈N，由Shapley值分配的收益為：

對(duì)于給定的2個(gè)聯(lián)盟集合U={U1,…,Ul}和S={S1,…,Sp}，定義i?表示兩個(gè)聯(lián)盟的傳遞的二元關(guān)系，iUS?表示進(jìn)行聯(lián)盟博弈的參與者i更偏向于加入聯(lián)盟集合U。

所以，把穩(wěn)定集作為聯(lián)盟博弈的解只適用于某些特殊問(wèn)題。按聯(lián)盟成員對(duì)聯(lián)盟貢獻(xiàn)的大小進(jìn)行分配收益具有唯一性和公平性，被廣泛應(yīng)用于各種場(chǎng)景。

在WSN中，數(shù)據(jù)傳輸過(guò)程是將數(shù)據(jù)由源節(jié)點(diǎn)通過(guò)節(jié)點(diǎn)轉(zhuǎn)發(fā)發(fā)送至目標(biāo)節(jié)點(diǎn)。當(dāng)目標(biāo)節(jié)點(diǎn)相同時(shí)，節(jié)點(diǎn)為了最大化自身利益，會(huì)與其他節(jié)點(diǎn)合作，建立一個(gè)聯(lián)盟，最后根據(jù)商量好的方案對(duì)利益進(jìn)行再分配。文獻(xiàn)[9]將聯(lián)盟博弈應(yīng)用到無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合過(guò)程中，減少了網(wǎng)絡(luò)的能量消耗，延長(zhǎng)了網(wǎng)絡(luò)的生存周期。聯(lián)盟建立時(shí)，將節(jié)點(diǎn)分為源節(jié)點(diǎn)和匯聚節(jié)點(diǎn)。源節(jié)點(diǎn)主要負(fù)責(zé)數(shù)據(jù)采集和轉(zhuǎn)發(fā)，匯聚節(jié)點(diǎn)則是對(duì)接收到的數(shù)據(jù)信息進(jìn)行融合。如何選擇合適的節(jié)點(diǎn)建立一個(gè)聯(lián)盟？文獻(xiàn)[9]中給出了一個(gè)思路，即將數(shù)據(jù)發(fā)送至同一目標(biāo)匯聚節(jié)點(diǎn)且傳輸路徑在一定程度上可以實(shí)現(xiàn)的源節(jié)點(diǎn)看作一個(gè)聯(lián)盟。在一個(gè)聯(lián)盟中，節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)的數(shù)量以及與其他節(jié)點(diǎn)合作時(shí)所轉(zhuǎn)發(fā)數(shù)據(jù)的數(shù)量對(duì)聯(lián)盟的收益有很大影響，同時(shí)會(huì)消耗節(jié)點(diǎn)能量，對(duì)消耗的能量可將其視作聯(lián)盟的成本消耗[9]。

考慮到節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)的數(shù)量和節(jié)點(diǎn)間合作時(shí)轉(zhuǎn)發(fā)的數(shù)據(jù)量的影響，聯(lián)盟的收益函數(shù)定義如下：

pij表示的是聯(lián)盟內(nèi)節(jié)點(diǎn)發(fā)送自身收集的數(shù)據(jù)數(shù)量；qij表示的是聯(lián)盟內(nèi)節(jié)點(diǎn)轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的數(shù)據(jù)的數(shù)量。聯(lián)盟收益函數(shù)C其實(shí)是聯(lián)盟內(nèi)節(jié)點(diǎn)的接收數(shù)據(jù)總量和節(jié)點(diǎn)與其他節(jié)點(diǎn)之間的合作度的乘積。這里的合作度反映的是聯(lián)盟內(nèi)節(jié)點(diǎn)與其他節(jié)點(diǎn)合作轉(zhuǎn)發(fā)的數(shù)據(jù)數(shù)量多少的程度。

關(guān)于合作度的描述如下：

式中C代表的是聯(lián)盟中的源節(jié)點(diǎn)，S代表匯聚節(jié)點(diǎn)。

假定在t時(shí)段源節(jié)點(diǎn)ai接收到的數(shù)據(jù)總量可以定義為：

式中，Ai為節(jié)點(diǎn)ai接收的數(shù)據(jù)流強(qiáng)度；n為接收的數(shù)據(jù)個(gè)數(shù)。

在一個(gè)聯(lián)盟中，節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)的數(shù)量以及與其他節(jié)點(diǎn)合作時(shí)轉(zhuǎn)發(fā)數(shù)據(jù)的數(shù)量太多，節(jié)點(diǎn)消耗能量也會(huì)增多。本文中，能耗的模型如下：聯(lián)盟的特征函數(shù)為收益函數(shù)除去本身的能量消耗。利用聯(lián)盟博弈對(duì)WSN節(jié)點(diǎn)數(shù)據(jù)融合進(jìn)行優(yōu)化，一定程度上降低了節(jié)點(diǎn)能耗，延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

3 結(jié) 語(yǔ)

通過(guò)對(duì)博弈論在WSN數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制的研究，本文總結(jié)了非合作博弈（拍賣博弈）和合作博弈（聯(lián)盟博弈）在數(shù)據(jù)轉(zhuǎn)發(fā)、數(shù)據(jù)融合中的具體應(yīng)用，理論上一定程度降低了網(wǎng)絡(luò)能耗，延長(zhǎng)了網(wǎng)絡(luò)的生命周期，但也存在不足。

拍賣博弈模型應(yīng)用中，在進(jìn)行鏈路質(zhì)量的定義時(shí)，考慮到節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的跳數(shù)，并沒(méi)有將節(jié)點(diǎn)之間的距離考慮在內(nèi)。如果節(jié)點(diǎn)之間跳數(shù)少，但是節(jié)點(diǎn)之間距離較大，同樣會(huì)產(chǎn)生較多的能量損耗。

聯(lián)盟博弈中，能量消耗部分沒(méi)有考慮到節(jié)點(diǎn)自身的電路能耗。在節(jié)點(diǎn)之間進(jìn)行傳輸時(shí)，對(duì)自由空間損耗的考慮是否可以忽略，是值得考慮的問(wèn)題。

現(xiàn)實(shí)生活中，博弈論已經(jīng)應(yīng)用于各個(gè)領(lǐng)域，如金融經(jīng)濟(jì)、軍事領(lǐng)域、政治領(lǐng)域等。近年，博弈論在無(wú)線傳感器網(wǎng)絡(luò)中的應(yīng)用方面增多，如能耗均衡、定位技術(shù)等。博弈論在WSN中的應(yīng)用雖然存在不足，但對(duì)現(xiàn)實(shí)生活的意義不可否認(rèn)。因此，后續(xù)將進(jìn)一步加深對(duì)博弈論在WSN中應(yīng)用的研究。

參考文獻(xiàn)：

[1] Lin C,Wu Y,Liu Z,et al.GTCharge:A Game Theoretical Collaborative Charging Scheme for Wireless Rechargeable Sensor Networks[J].Journal of Systems and Software,2016(121):88-104.

[2] 沈士根.基于博弈論的無(wú)線傳感器網(wǎng)絡(luò)安全若干關(guān)鍵問(wèn)題研究[D].上海:東華大學(xué),2013.SHEN Shi-gen.Research on Some Key Issues of Wireless Sensor Network Security Based on Game Theory[D].Shanghai:Donghua University,2013.

[3] 田得潤(rùn),李長(zhǎng)云,張瑤等.博弈論在無(wú)線傳感器網(wǎng)絡(luò)路由機(jī)制中的應(yīng)用[J].湖南工業(yè)大學(xué)學(xué)報(bào),2012,26(01):55-60.TIAN De-run,LI Chang-yun,ZHANG Yao,et al.Application of Game Theory in Wireless Sensor Network Routing Mechanism[J].Journal of Hunan University of Technology,2012,26(01):55-60.

[4] 李夢(mèng)君.暗標(biāo)拍賣的博弈分析[J].科技創(chuàng)業(yè)月刊,2009(09):43-44.LI Meng-jun.Game Analysis of Underbill Auctions[J].Pioneering with Science & Technology,2009(09):43-44.

[5] Li Y,Gao Z,Yang Y,et al.An Improved Auction Scheme for Task Allocation in Wireless Sensor Network[C].Wireless Communications Networking and Mobile Computing(WiCOM),2010:1-4.

[6] 先興平,劉群,吳濤.拍賣博弈模型在無(wú)線傳感器網(wǎng)絡(luò)路由中的應(yīng)用研究[J].小型微型計(jì)算機(jī)系統(tǒng),2012,33(05):1083-1088.XIAN Xing-ping,LIU Qun,WU Tao.Application of Auction Game Model for Wireless Sensor Network Routing[J].Journal of Chinese Computer Systems,2012,33(05):1083-1088.

[7] 吳添英,岳昆,劉惟一.一種無(wú)線傳感器網(wǎng)絡(luò)的節(jié)能聯(lián)盟博弈模型[C].中國(guó)自動(dòng)化學(xué)會(huì)控制理論專業(yè)委員會(huì)A卷,2011.WU Tian-ying,YUE Kun,LIU Wei-yi.An Energyefficient Coalition Game Model for Wireless Sensor Networks[C].Control Conference (CCC),2011:4940-4945.

[8] Liu Q,Yang S,Zhang L,et al.Game-theory-based Coordination in Wireless Sensor and Actor Networks[J].IET Wireless Sensor Systems,2016,6(05):166-172.

[9] 韓格,楊金華,楊文靜等.一種面向無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合的路由聯(lián)盟博弈方法[J].云南大學(xué)學(xué)報(bào):自然科學(xué)版,2011(05):511-516,520.HAN Ge,YANG Jin-hua,YANG Wen-jing,et al.A Routing Coalition Game Approach for Data Fusion in Wireless Sensor Networks[J].Journal of Yunnan University:Natural Science Editi on,2011,33(05):511-516,520.