張 偉，張玲華,2

（1.南京郵電大學(xué)通信與信息工程學(xué)院 南京 210003；2.江蘇省通信與網(wǎng)絡(luò)技術(shù)工程研究中心 南京 210003）

1 引言

無線傳感器能夠利用自組織能力形成網(wǎng)絡(luò)，協(xié)作地感知、采集、處理和傳輸網(wǎng)絡(luò)覆蓋地理區(qū)域內(nèi)被感知對象的信息，并將這些信息發(fā)送給網(wǎng)絡(luò)所有者。因而可以說，傳感器網(wǎng)絡(luò)的出現(xiàn)彌補(bǔ)了人類無法涉足的區(qū)域信息獲取困難的遺憾，具有廣闊的應(yīng)用前景。它將現(xiàn)代社會(huì)三大信息技術(shù)（即傳感器技術(shù)、計(jì)算機(jī)技術(shù)和通信技術(shù)）有效地應(yīng)用于一體。無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)數(shù)目往往很大，節(jié)點(diǎn)只能獲取局部拓?fù)浣Y(jié)構(gòu)信息，路由解決方案要能在局部網(wǎng)絡(luò)信息的基礎(chǔ)上選擇合適的路徑，同時(shí)，傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量有限且一般沒有能量補(bǔ)充，因此路由解決方案是否能高效地利用能量就成為衡量傳感器網(wǎng)絡(luò)系統(tǒng)的重要性能指標(biāo)。傳統(tǒng)路由策略往往需要知道整個(gè)網(wǎng)絡(luò)的全局信息，難以應(yīng)用。其根本問題在于以往的無線傳感器網(wǎng)絡(luò)解決方案中，傳感器節(jié)點(diǎn)傳送數(shù)據(jù)的方式是存儲(chǔ)轉(zhuǎn)發(fā)，即除了數(shù)據(jù)發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)以外的中間節(jié)點(diǎn)只負(fù)責(zé)路由，而不對數(shù)據(jù)內(nèi)容做任何處理，中間節(jié)點(diǎn)扮演轉(zhuǎn)發(fā)器的角色。

網(wǎng)絡(luò)編碼是一種融合了路由和編碼的信息交換技術(shù)，它的核心思想是網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)對各條信道上收到的信息進(jìn)行線性或者非線性處理，然后轉(zhuǎn)發(fā)給下游節(jié)點(diǎn)，中間節(jié)點(diǎn)扮演編碼器或信號處理器的角色。無線傳感器網(wǎng)絡(luò)鏈路的不可靠性和物理層廣播特性非常適合使用編碼的方法。應(yīng)用網(wǎng)絡(luò)編碼，可以解決傳統(tǒng)路由解決方案、跨層路由設(shè)計(jì)等技術(shù)無法解決的問題，提高網(wǎng)絡(luò)性能。

許多現(xiàn)有的研究[1～4]已經(jīng)論證了無線網(wǎng)絡(luò)中網(wǎng)絡(luò)編碼的益處。但是這些研究都是假定了所有節(jié)點(diǎn)是相互合作的。實(shí)際上，無線傳感器網(wǎng)絡(luò)是通過自組織而形成的網(wǎng)絡(luò)，網(wǎng)絡(luò)節(jié)點(diǎn)有一個(gè)重要特性——自利。當(dāng)傳輸機(jī)制用于由自利節(jié)點(diǎn)組成的分布式網(wǎng)絡(luò)時(shí)，必須分析動(dòng)態(tài)系統(tǒng)的均衡點(diǎn)，平衡各用戶收益，設(shè)計(jì)有效的策略促使穩(wěn)定、高效的傳輸機(jī)制能夠?qū)崿F(xiàn)。參考文獻(xiàn)[5]基于非合作潛在博弈，提出了動(dòng)態(tài)數(shù)據(jù)流分割算法，在平衡各用戶效用的基礎(chǔ)上，最大化網(wǎng)絡(luò)編碼機(jī)會(huì)。隨著無線傳感器網(wǎng)絡(luò)的快速發(fā)展，如何對分布式系統(tǒng)中參與網(wǎng)絡(luò)編碼的用戶增益和代價(jià)分析，設(shè)計(jì)動(dòng)態(tài)算法，平衡用戶收益，得到較高系統(tǒng)效率，將是業(yè)界面臨的關(guān)鍵性挑戰(zhàn)問題。參考文獻(xiàn)[6]研究了網(wǎng)絡(luò)編碼中繼能量消耗與傳輸時(shí)延的折中關(guān)系，在每個(gè)源節(jié)點(diǎn)都試圖最優(yōu)其折中關(guān)系的條件下，建立非合作博弈模型，提出一種分布式激勵(lì)策略，得到和中心式算法相同的性能。這些研究成果初步說明了使用博弈論分析網(wǎng)絡(luò)編碼中合作行為的可行性和重要性。由于無線傳輸?shù)膹V播性質(zhì)，當(dāng)一個(gè)節(jié)點(diǎn)傳送數(shù)據(jù)分組時(shí)，在一定范圍內(nèi)的所有節(jié)點(diǎn)都能接收這個(gè)數(shù)據(jù)分組，如何有效利用這樣的廣播增益也是本文的研究點(diǎn)之一。本文在研究無線網(wǎng)絡(luò)編碼的基礎(chǔ)上，結(jié)合節(jié)點(diǎn)的廣播特性，將多個(gè)源、多個(gè)目的流量分割問題建立為博弈模型，分析在具有網(wǎng)絡(luò)編碼增益及廣播增益情況下的網(wǎng)絡(luò)代價(jià)問題，提出分布式控制方案，使得節(jié)點(diǎn)間的計(jì)算彼此獨(dú)立，不依賴于全局信息。經(jīng)論證，該控制方案可以收斂到納什均衡這一最優(yōu)解決方案，使得系統(tǒng)代價(jià)收斂到最小代價(jià)的穩(wěn)態(tài)。

2 流量分配算法

本文將無線傳感器網(wǎng)絡(luò)建成一個(gè)G(V，E)有向圖模型，有|V|=N個(gè)節(jié)點(diǎn)，邊緣集合為E。兩個(gè)節(jié)點(diǎn)之間的線段代表它們之間的無線連接。對于每條鏈路 (ni，nj)∈E，ni和nj∈V，存在一個(gè)無線信道使得節(jié)點(diǎn)ni可以傳輸信息到節(jié)點(diǎn)nj。每條鏈路(ni，nj)有相應(yīng)的傳輸代價(jià)αij。αij的大小代表從節(jié)點(diǎn)ni到節(jié)點(diǎn)nj發(fā)送單位信息的傳輸耗費(fèi) （傳遞次數(shù)）。由于無線信道的廣播特性，ni節(jié)點(diǎn)可以將信息同時(shí)傳輸?shù)狡溧従庸?jié)點(diǎn)nj和nk，這個(gè)傳輸?shù)淖畲蠛馁M(fèi)為max{αij，αik}。

如圖1所示，網(wǎng)絡(luò)結(jié)構(gòu)中有4個(gè)源節(jié)點(diǎn)，其中S1和S1’有相同的內(nèi)容。目的節(jié)點(diǎn)n3和n5對S1、S2和S3的內(nèi)容感興趣，而目的節(jié)點(diǎn)n9對S1和S3的內(nèi)容感興趣。網(wǎng)絡(luò)存在6條網(wǎng)絡(luò)傳輸流：第1條流從n3節(jié)點(diǎn)到n5節(jié)點(diǎn)；第2條流從n5節(jié)點(diǎn)到n3節(jié)點(diǎn)；第3條流從n8節(jié)點(diǎn)到n5節(jié)點(diǎn)；第4條流從n8節(jié)點(diǎn)到n9節(jié)點(diǎn)；第5條流從n7節(jié)點(diǎn)到n5節(jié)點(diǎn)；第6條流從n7節(jié)點(diǎn)到n9節(jié)點(diǎn)。將xi定義為第i條路徑上傳輸?shù)牧髁?。從圖1可以看出，第1條流的數(shù)據(jù)分組可以通過路徑P11=(n3，n4，n5)和P12=(n3，n1，n2，n5)傳輸。路徑P11和P12上分配的流量分別為和，則有+=x1。相似地，第6條流的數(shù)據(jù)分組通過路徑P61=(n7，n6，n9)和P62=(n7，n10，n9)傳輸，x6為x61和x62的總和。值得注意的是，第5條流的路徑P51=(n7，n6，n5)和第6條流的路徑P61=(n7，n6，n9)共享同一個(gè)鏈接(n7，n6)。因此，通過這兩條路徑發(fā)送的數(shù)據(jù)分組可以通過多播減少傳輸代價(jià)，這里n6被稱為多播傳輸節(jié)點(diǎn)，鏈路(n7，n6)被定義為多播傳輸鏈接，記為MC鏈接。

圖1 不同路徑流量的競爭關(guān)系

n6節(jié)點(diǎn)多播傳輸時(shí)的消耗如式（1）所示。

式（1）中，右邊的第一項(xiàng)為多播傳輸?shù)拇鷥r(jià)，由于從n7傳來的數(shù)據(jù)分組通過多播傳輸，到達(dá)目的節(jié)點(diǎn)n5和n9，所以發(fā)送單位數(shù)據(jù)的消耗是max{α65，α69}；第二項(xiàng)和第三項(xiàng)是流量“溢出”消耗。當(dāng)兩條路徑上的流量不相等時(shí)，會(huì)產(chǎn)生需要傳輸?shù)念~外流量。

如圖1所示，n4節(jié)點(diǎn)有兩對反向流量，n3節(jié)點(diǎn)和n5節(jié)點(diǎn)之間的一對流量與n5節(jié)點(diǎn)和n8節(jié)點(diǎn)之間的一對流量相互競爭。值得注意的是，由于無線網(wǎng)絡(luò)的廣播特性，n3節(jié)點(diǎn)和n8節(jié)點(diǎn)都可以從n4節(jié)點(diǎn)接收數(shù)據(jù)分組進(jìn)行解碼，并相互交換信息。將多播鏈接(n3，n4，n8)定義為網(wǎng)絡(luò)編碼多播（network coding and multicast，NCMC）傳 輸 鏈 接，記 為NCMC鏈接。將n4節(jié)點(diǎn)定義為網(wǎng)絡(luò)編碼多播傳輸節(jié)點(diǎn)。

n4節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼時(shí)的消耗如式（2）所示。

式（2）中兩個(gè)等式右邊的第一項(xiàng)是通過n4節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼傳輸產(chǎn)生的消耗，第二項(xiàng)和第三項(xiàng)表示流量“溢出”消耗，這是由于可能不等于，也可能不等于，剩下的流量將不會(huì)進(jìn)行網(wǎng)絡(luò)編碼，而是被直接傳輸。

此外，S1和S1’有相同的內(nèi)容，目的節(jié)點(diǎn)可以從這兩個(gè)源節(jié)點(diǎn)中的任意一個(gè)節(jié)點(diǎn)獲取內(nèi)容。例如節(jié)點(diǎn)n5可以從源S1（節(jié)點(diǎn)n3）和源S1’（節(jié)點(diǎn)n7）獲得內(nèi)容，即S1和S1’同時(shí)為節(jié)點(diǎn)n5服務(wù)。對于節(jié)點(diǎn)n5，++=x1，可以發(fā)現(xiàn)多播傳輸鏈接和網(wǎng)絡(luò)編碼多播傳輸鏈接之間也存在競爭。如果通過網(wǎng)絡(luò)編碼多播傳輸鏈路(n3，n4，n5)傳遞數(shù)據(jù)，n3節(jié)點(diǎn)可以獲得更多逆向流信息。但是對于n9節(jié)點(diǎn)，則更希望在多播傳輸鏈接(n7，n6)上分配較多的流量。因此，面臨的挑戰(zhàn)在于如何設(shè)計(jì)一種有效的分布式機(jī)制，在路徑上分配流量，從而使得網(wǎng)絡(luò)傳輸代價(jià)最小。

眾所周知，max{xi,xj}+min{xi,xj}=xi+xj，式（1）和式（2）的消耗可以重寫為式（3）。

（4）人為信任。人為信任包括身份認(rèn)證和證書等其他事先約定的信任。無論是在傳統(tǒng)的一致性算法還是在區(qū)塊鏈共識算法中都十分常見。分布式系統(tǒng)中的管理員是身份認(rèn)證的典型代表。在區(qū)塊鏈中一些聯(lián)盟鏈需要證書認(rèn)證都基于此種信任?；谌藶樾湃螘?huì)極大影響區(qū)塊鏈的去中心化程度，但由于事先約定的緣故，不需要大量資源換取信任，是代價(jià)最小的一種方式，同時(shí)可能換取效率的提升。

式（3）可以解釋為n4節(jié)點(diǎn)不使用網(wǎng)絡(luò)編碼時(shí)的消耗減去使用網(wǎng)絡(luò)編碼的增益。同理，在n6節(jié)點(diǎn)，將多播產(chǎn)生的增益定義為多播傳輸增益?？偟木W(wǎng)絡(luò)消耗可以表示為式（5）。

為了解決這個(gè)問題，引入一個(gè)新的決策變量yk，表示網(wǎng)絡(luò)編碼多播傳輸鏈接和多播傳輸鏈接的容量。限制節(jié)點(diǎn)nk上兩個(gè)流之間的總編碼（或多播傳播）流量大約等于鏈路最大負(fù)載能力yk，“溢出”流量不進(jìn)行編碼，直接發(fā)送。圖2中，網(wǎng)絡(luò)編碼多播傳輸鏈接(n3，n4，n5)和(n8，n4，n5)的容量定義為y41和y42，相應(yīng)的多播傳輸鏈接的容量定義為y6。在容量為y4的網(wǎng)絡(luò)編碼多播傳輸鏈接上傳輸?shù)目傁娜缡剑?）所示。

式（6）的前兩項(xiàng)表示多播傳輸消耗。值得注意的是，無論在網(wǎng)絡(luò)編碼多播傳輸鏈接上有沒有足夠的逆向流進(jìn)行編碼發(fā)送，都必須承擔(dān)相應(yīng)的消耗。之后使用共軛梯度下降法調(diào)整鏈接的容量，使網(wǎng)絡(luò)得到優(yōu)化。

n4節(jié)點(diǎn)的消耗可以重寫為式（7）。

因此，當(dāng)系統(tǒng)狀態(tài)為(X，Y)時(shí)，修改后的效用函數(shù)（網(wǎng)絡(luò)總消耗）如式（8）所示。

可以看到，效用函數(shù)里包含“min”函數(shù)，這使得函數(shù)不連續(xù)、不可微。為了得到一個(gè)連續(xù)可微的效用函數(shù)，用“min”函數(shù)的廣義平均值函數(shù)替代，利用夾逼定理可證。

設(shè)a={a1,a2,…,an}是正實(shí)數(shù)集，r為非零實(shí)數(shù)。集合a的廣義平均函數(shù)可表示為：

用Mr代替min函數(shù)，得到一個(gè)近似的網(wǎng)絡(luò)總消耗方程，如式（10）所示。

其中，F(xiàn)是網(wǎng)絡(luò)中的流量數(shù)，Si是可選擇的策略，即一條備選路徑，akd是兩個(gè)相鄰節(jié)點(diǎn)間的通信代價(jià)。近似的效用函數(shù)C(X,YNCMC,YMC)是連續(xù)、可微的，因此使用該近似效用函數(shù)作為勢函數(shù)，遵循潛在博弈的定義[8]。本文的目標(biāo)是在給定網(wǎng)絡(luò)負(fù)載的情況下，最小化系統(tǒng)代價(jià)C(X，Y)，如式（11）所示，可以將其視為一個(gè)最優(yōu)化問題解決。

值得注意的是，博弈論中每一個(gè)參與者（即數(shù)據(jù)流）都會(huì)試圖減少所消耗的代價(jià)。第i條數(shù)據(jù)流選定合適的路徑后，會(huì)通過調(diào)整流量分配的多少達(dá)到Wardrop平衡[9,10]。

在網(wǎng)絡(luò)構(gòu)建初期，將網(wǎng)絡(luò)編碼和多播傳輸?shù)逆溄臃謩e申明為NCMC鏈接和MC鏈接，并給定其容量分別為YNCMC和YMC。NCMC鏈接是具有逆向編碼及多播傳輸能力的鏈接，將逆向數(shù)據(jù)流進(jìn)行編碼后以多播方式發(fā)送給周邊節(jié)點(diǎn)；MC鏈接為只具有多播傳輸能力的鏈接，將相同的數(shù)據(jù)流以多播方式發(fā)送給多個(gè)目的節(jié)點(diǎn)。在網(wǎng)絡(luò)構(gòu)建時(shí)，將NCMC鏈接和MC鏈接的容量及代價(jià)進(jìn)行廣播。

在網(wǎng)絡(luò)運(yùn)行階段，網(wǎng)絡(luò)節(jié)點(diǎn)收到NCMC鏈接和MC鏈接廣播的鏈接容量，即YNCMC、YMC及代價(jià)，根據(jù)兩種鏈接代價(jià)的計(jì)算方法計(jì)算鏈接總傳輸代價(jià)，節(jié)點(diǎn)利用拉格朗日乘子法分布式地求出最優(yōu)路徑分配流量。

根據(jù)拉格朗日乘子法得到的最優(yōu)解，即當(dāng)前網(wǎng)絡(luò)流量分配狀態(tài)X，利用最速梯度下降法求新的鏈接容量，即YNCMC、YMC，在新的鏈接容量下重復(fù)上述操作，最終得到最小網(wǎng)絡(luò)傳輸代價(jià)時(shí)的路徑分配流量。

本文已經(jīng)設(shè)計(jì)了一個(gè)分布式方案，該方案可以在給定網(wǎng)絡(luò)流量與傳輸鏈接及其容量Y時(shí)，實(shí)現(xiàn)網(wǎng)絡(luò)代價(jià)局部最小。之后將基于當(dāng)前系統(tǒng)狀態(tài)，調(diào)整鏈接容量Y，使得在給定負(fù)載流量X的情況下，網(wǎng)絡(luò)代價(jià)進(jìn)一步減小。在鏈接容量Y的微小改變前后，系統(tǒng)始終處于Wardrop平衡狀態(tài)。

3 仿真與分析

通過MATLAB仿真評估系統(tǒng)的性能。根據(jù)圖1所示的網(wǎng)絡(luò)模型，源節(jié)點(diǎn)S1、S1’、S2和S3給定的負(fù)荷量分別為2.32、2.32、4.27和3.19。對各個(gè)鏈接的路徑代價(jià)定義為：α12=1.3、α13=1.7、α25=1.6、α34=1.7、α38=1.5、α45=1.8、α48=1.6、α56=2.1、α67=1.6、α69=1.8、α710=1.6、α89=2.2、α910=1.6。假設(shè)鏈路上的消耗是對稱的，令r=-100，使用式（10）所示的近似效用函數(shù)進(jìn)行仿真。

如圖2所示，比較了多播傳輸無網(wǎng)絡(luò)編碼算法、集中控制流量分配算法、無網(wǎng)絡(luò)編碼無多播傳輸算法和動(dòng)態(tài)流量分配算法的網(wǎng)絡(luò)總代價(jià)。多播傳輸無網(wǎng)絡(luò)編碼算法是指網(wǎng)絡(luò)中沒用到網(wǎng)絡(luò)編碼，但存在多播傳輸；無網(wǎng)絡(luò)編碼無多播算法是一種無網(wǎng)絡(luò)編碼的單一傳播算法；動(dòng)態(tài)流量分配算法是本文提出的算法，通過分配流量增加編碼機(jī)會(huì)。為了衡量動(dòng)態(tài)流量分配算法的性能，仿真了集中控制流量分配算法的網(wǎng)絡(luò)代價(jià)，該算法是一個(gè)LP（linear program，線性規(guī)劃）方法，需要完整的網(wǎng)絡(luò)信息。本文提出的控制方案中節(jié)點(diǎn)間的計(jì)算彼此獨(dú)立，不依賴于全局信息。仿真結(jié)果表明，動(dòng)態(tài)流量分配算法的總消耗比無網(wǎng)絡(luò)編碼的方法小，與最佳解決方法十分相近。另外，流量分配控制算法具有良好的收斂性。

圖2 不同算法網(wǎng)絡(luò)總代價(jià)比較

圖3 仿真了每條路徑所分配流量的動(dòng)態(tài)變化及其收斂情況?？梢钥闯觯瑒?dòng)態(tài)流量分配算法可以驅(qū)使每條路徑的流量到達(dá)一個(gè)最佳狀態(tài)，從而減少網(wǎng)絡(luò)代價(jià)，使得網(wǎng)絡(luò)吞吐量顯著增加。根據(jù)潛在博弈論的性質(zhì)，動(dòng)態(tài)流量分配算法可以使網(wǎng)絡(luò)達(dá)到納什平衡。

圖3 不同路徑的流量變化情況

4 結(jié)束語

本文研究了無線傳感器網(wǎng)絡(luò)中，N個(gè)源節(jié)點(diǎn)通過多徑傳遞K個(gè)不同內(nèi)容到D個(gè)目的節(jié)點(diǎn)的問題，源節(jié)點(diǎn)根據(jù)效用函數(shù)拆分流量，并分配到不同路徑上，增加網(wǎng)絡(luò)編碼的機(jī)會(huì)，從而減少網(wǎng)絡(luò)傳輸代價(jià)。利用博弈論的方法解決了多源、多徑的流量分配問題，提出了可以達(dá)到納什均衡的動(dòng)態(tài)流量分配算法，并證明這個(gè)過程是漸進(jìn)收斂的。數(shù)值仿真結(jié)果表明，動(dòng)態(tài)流量分配算法是有效的，并且可以快速收斂到最優(yōu)解，在網(wǎng)絡(luò)節(jié)點(diǎn)利己的情況下，分布式動(dòng)態(tài)控制方案可以達(dá)到最優(yōu)解。

1 Ahswede R,Cai N,Li S,et al.Network information flow.IEEE Transactions on Information Theory,2000,46(4):1204～1216

2 Marden J,Effros M.The price of selfishness in network coding.IEEE Transactions on Information Theory,2012,58(4):2349～2361

3 Li W,Chen J,Zhou B.Game theory analysis for graded punishment mechanism restraining free-riding in P2P networks.Proceedings of International Symposium on Computer Science and Society,Kota Kinabalu,Malaysia,2011:262～266

4 Zhao F,Medard M.On analyzing and improving COPE performance.Proceedings of Information Theory and Applications Workshop,San Diego,CA,USA,2010:1～6

5 Reddy V,Shakkottai S,Sprintsom A,et al.Multipath wireless network coding:a population game perspective.Proceedings of IEEE INFOCOM,San Diego,CA,USA,2010:1～9

6 Ciftcioglu E,Sagduyu Y E,Berry R,et al.Cost-delay tradeoffs for two-way telay networks.IEEE Transactions on Wireless Communications,2011,10(12):4100～4109

7 Aperjis C,Johari R,Freedman M J.Bilateral and multilateral exchanges for peer-assisted content distribution.IEEE/ACM Transactions on Networking,2011,19(5):1290～1303

8 Han Z,Niyato D,Saad W,et al.Game Theory in Wireless and Communication Networks.Oxford:Cambridge University Press,2012

9 Neely M J,Golubchik L.Utility optimization for dynamic peer-to-peer networks with tit-for-tat constraints.Proceedings of IEEE INFOCOM,Shanghai,China,2011:1458～1466

10 Zhao J,Zhang P,Cao G.On cooperative caching in wireless P2P networks.Proceedings of the 28th International Conference on Distributed Computing Systems,Beijing,China,2008:731～739