基于潛在博弈的多源多跳無線傳感器網絡流量分配算法

張 偉，張玲華,2

（1.南京郵電大學通信與信息工程學院 南京 210003；2.江蘇省通信與網絡技術工程研究中心 南京 210003）

1 引言

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

網絡編碼是一種融合了路由和編碼的信息交換技術，它的核心思想是網絡中的各個節點對各條信道上收到的信息進行線性或者非線性處理，然后轉發給下游節點，中間節點扮演編碼器或信號處理器的角色。無線傳感器網絡鏈路的不可靠性和物理層廣播特性非常適合使用編碼的方法。應用網絡編碼，可以解決傳統路由解決方案、跨層路由設計等技術無法解決的問題，提高網絡性能。

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

2 流量分配算法

本文將無線傳感器網絡建成一個G(V，E)有向圖模型，有|V|=N個節點，邊緣集合為E。兩個節點之間的線段代表它們之間的無線連接。對于每條鏈路 (ni，nj)∈E，ni和nj∈V，存在一個無線信道使得節點ni可以傳輸信息到節點nj。每條鏈路(ni，nj)有相應的傳輸代價αij。αij的大小代表從節點ni到節點nj發送單位信息的傳輸耗費 （傳遞次數）。由于無線信道的廣播特性，ni節點可以將信息同時傳輸到其鄰居節點nj和nk，這個傳輸的最大耗費為max{αij，αik}。

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

圖1 不同路徑流量的競爭關系

n6節點多播傳輸時的消耗如式（1）所示。

式（1）中，右邊的第一項為多播傳輸的代價，由于從n7傳來的數據分組通過多播傳輸，到達目的節點n5和n9，所以發送單位數據的消耗是max{α65，α69}；第二項和第三項是流量“溢出”消耗。當兩條路徑上的流量不相等時，會產生需要傳輸的額外流量。

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

n4節點進行網絡編碼時的消耗如式（2）所示。

式（2）中兩個等式右邊的第一項是通過n4節點進行網絡編碼傳輸產生的消耗，第二項和第三項表示流量“溢出”消耗，這是由于可能不等于，也可能不等于，剩下的流量將不會進行網絡編碼，而是被直接傳輸。

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

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

（4）人為信任。人為信任包括身份認證和證書等其他事先約定的信任。無論是在傳統的一致性算法還是在區塊鏈共識算法中都十分常見。分布式系統中的管理員是身份認證的典型代表。在區塊鏈中一些聯盟鏈需要證書認證都基于此種信任。基于人為信任會極大影響區塊鏈的去中心化程度，但由于事先約定的緣故，不需要大量資源換取信任，是代價最小的一種方式，同時可能換取效率的提升。

式（3）可以解釋為n4節點不使用網絡編碼時的消耗減去使用網絡編碼的增益。同理，在n6節點，將多播產生的增益定義為多播傳輸增益。總的網絡消耗可以表示為式（5）。

為了解決這個問題，引入一個新的決策變量yk，表示網絡編碼多播傳輸鏈接和多播傳輸鏈接的容量。限制節點nk上兩個流之間的總編碼（或多播傳播）流量大約等于鏈路最大負載能力yk，“溢出”流量不進行編碼，直接發送。圖2中，網絡編碼多播傳輸鏈接(n3，n4，n5)和(n8，n4，n5)的容量定義為y41和y42，相應的多播傳輸鏈接的容量定義為y6。在容量為y4的網絡編碼多播傳輸鏈接上傳輸的總消耗如式（6）所示。

式（6）的前兩項表示多播傳輸消耗。值得注意的是，無論在網絡編碼多播傳輸鏈接上有沒有足夠的逆向流進行編碼發送，都必須承擔相應的消耗。之后使用共軛梯度下降法調整鏈接的容量，使網絡得到優化。

n4節點的消耗可以重寫為式（7）。

因此，當系統狀態為(X，Y)時，修改后的效用函數（網絡總消耗）如式（8）所示。

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

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

用Mr代替min函數，得到一個近似的網絡總消耗方程，如式（10）所示。

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

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

在網絡構建初期，將網絡編碼和多播傳輸的鏈接分別申明為NCMC鏈接和MC鏈接，并給定其容量分別為YNCMC和YMC。NCMC鏈接是具有逆向編碼及多播傳輸能力的鏈接，將逆向數據流進行編碼后以多播方式發送給周邊節點；MC鏈接為只具有多播傳輸能力的鏈接，將相同的數據流以多播方式發送給多個目的節點。在網絡構建時，將NCMC鏈接和MC鏈接的容量及代價進行廣播。

在網絡運行階段，網絡節點收到NCMC鏈接和MC鏈接廣播的鏈接容量，即YNCMC、YMC及代價，根據兩種鏈接代價的計算方法計算鏈接總傳輸代價，節點利用拉格朗日乘子法分布式地求出最優路徑分配流量。

根據拉格朗日乘子法得到的最優解，即當前網絡流量分配狀態X，利用最速梯度下降法求新的鏈接容量，即YNCMC、YMC，在新的鏈接容量下重復上述操作，最終得到最小網絡傳輸代價時的路徑分配流量。

本文已經設計了一個分布式方案，該方案可以在給定網絡流量與傳輸鏈接及其容量Y時，實現網絡代價局部最小。之后將基于當前系統狀態，調整鏈接容量Y，使得在給定負載流量X的情況下，網絡代價進一步減小。在鏈接容量Y的微小改變前后，系統始終處于Wardrop平衡狀態。

3 仿真與分析

通過MATLAB仿真評估系統的性能。根據圖1所示的網絡模型，源節點S1、S1’、S2和S3給定的負荷量分別為2.32、2.32、4.27和3.19。對各個鏈接的路徑代價定義為：α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。假設鏈路上的消耗是對稱的，令r=-100，使用式（10）所示的近似效用函數進行仿真。

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

圖2 不同算法網絡總代價比較

圖3 仿真了每條路徑所分配流量的動態變化及其收斂情況。可以看出，動態流量分配算法可以驅使每條路徑的流量到達一個最佳狀態，從而減少網絡代價，使得網絡吞吐量顯著增加。根據潛在博弈論的性質，動態流量分配算法可以使網絡達到納什平衡。

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

4 結束語

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

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