基于博弈的协作路由算法

doi:10.3969/j.issn.1000-436x.2013.z1.007

摘要/Abstract

摘要：

协作虚拟多输入多输出（VMIMO）传输是一种有效的无线传输性能优化技术。将物理层协作VMIMO技术和网络层路由选择技术相结合，设计跨层VMIMO路由选择方案可以利用VMIMO的分集增益，显著地降低网络传输能耗。如何设计VMIMO协作路由协议抵抗无线网络的自私节点和欺骗行为，保证高数据转发率和低传V输能耗成为路由设计中的重大挑战。为了提高自私网络的VMIMO路由性能，提出了一种基于重复路由博弈的MIMO协作路由算法。该算法将网络划分成多个Group、Group间使用VMIMO传输数据。将Group间路由选择过程建模为重复路由博弈过程。为了提高数据转发的成功率，提出适用度函数评估节点参与数据分组转发的信誉。以此为基础，提出基于适用度的路由选择子算法和路由转发子算法。理论证明所提重复路由博弈可达到帕累托最优。仿真实验结果表明本算法可以促进自私节点相互合作，可获得较高的数据转发率，较好地减少数据传输时延以及能量消耗。

关键词: VMIMO, 协作路由, 重复博弈, 信誉度

Abstract:

Cooperative virtual multiple-input multiple-output (VMIMO) transmission is an effective technique to im-prove the transmission performance of wireless network. By taking advantage of diversity gain of VMIMO, the cross-layer VMIMO routing design combining cooperative VMIMO technology of physical layer and routing scheme of network layer can reduce power consumption of wireless transmission significantly. A significant challenge is how to make the VMIMO routing protocol robust to selfish and cheating behavior of users while guaranteeing high delivery ratio and low energy consumption. In order to improve the routing performance of selfish wireless network, a VMIMO coop-erative routing algorithm based on game theory was proposed. The network was divided into groups, and data was trans-mitted through VMIMO between groups. VMIMO routing among groups was modeled as a repeated routing game. To improve the data delivery ratio, a fit function was proposed to evaluate the nodes' credit for participating in packet for-warding. Based on the fit function, a fit value based routing selection algorithm and a fit value based routing forward al-gorithm were proposed. The proposed repeated routing game can approach to pareto optimality. Simulation result shows that this algorithm is capable of promoting cooperation between selfish nodes, which results in high delivery ratio, low transmission delay and energy consumption.

Key words: VMIMO, cooperative routing, repeated game, reputation

谢鲲,段申琳,文吉刚,何施茗. 基于博弈的协作路由算法[J]. 通信学报, 2013, 34(Z1): 44-57.

Kun XIE,Shen-lin DUAN,Ji-gang WEN,Shi-ming HE. Cooperative routing algorithm based on game theory[J]. Journal on Communications, 2013, 34(Z1): 44-57.

图/表 13

图1

图2

图3

表1

表2

图4

图5

图6

表3

图7

图8

图9

图10

参考文献 24

[1]	YUAN Y , HE Z , CHEN M . Virtual MIMO-based cross-layer design for wireless sensor networks[J]. IEEE Trans Veh Technol, 2006,55:856-864.
[2]	QU Q , MILSTEIN L B , VAMAN D R . Cooperative and constrained MIMO communications in wireless ad hoc/sensor networks[J]. IEEE Transactions on Wireless Communications, 2010,9:3120-3129.
[3]	COSO A , SAVAZZI S , SPAGNOLINI U . Virtual MIMO channels in cooperative multi-hop wireless sensor networks[A]. Proc Conf on Infor-mation Sciences and Systems[C]. Princeton, NJ, 2006.75-80.
[4]	RENATO M , DE M , HYUNCHUL K , et al. A new distributed coop-erative MIMO scheme for mobile ad hoc networks[J]. Information Sciences, 2013,232:88-103.
[5]	MYERSON R . Game Theory of Conflict[M]. Cambridge: Harvard University Press, 1991.
[6]	ALLEN B M , LUIZ A D . Game theory for wireless engineers[J]. Synthesis Lectures on Communications, 2006,1(1):1-86.
[7]	PAVLIDOU F N , KOLTSIDAS G . Game theory for routing modeling in communication networks-a survey[J]. Journal of Communications and Networks, 2008,10(3):268-286.
[8]	LBRAHIM A , HAN Z , LIU K . Distributed energy-efficient coopera-tive routing in wireless networks[J]. IEEE Transactions on Wireless Communication, 2008,7(10):3930-3941.
[9]	GUAN Y , XIA Y , SHEN C C . Csr: cooperative source routing using virtual miso in wireless ad hoc networks[A]. IEEE WCNC[C]. 2011.1119-1124.
[10]	SIAM M Z , KRUNZ M , YOUNIS O . Energy-efficient clustering/routing for cooperative mimo operation in sensor networks[A]. IEEE INFO-COM[C]. Rio De Janeiro, Brazil, 2009.621-629.
[11]	BILAL Z , SOHEYL G , MARTIN H . A joint clustering and routing scheme to maximize link performance in cooperative MIMO ad-hoc networks[A]. 2011 IEEE the 22nd International Symposium on PIMRC[C]. 2011.51-55.
[12]	SATHIAN D , BASKARAN R , DHAVACHELVAN P . A trustworthy energy efficient MIMO routing algorithm based on game theory for WSN[A]. IEEE-International Conference on Advances in Engineering, Science and Management (ICAESM-2012)[C]. Nagapattinam, Tamil Nadu, India, 2012.499-502.
[13]	SECCI S , ROUGIER J L , PATTAVINA A , et al. Peering equilibrium multipath routing: a game theory framework for Internet peering set-tlements[J]. IEEE/ACM Transactions on Networking, 2011,19(2):419-432.
[14]	ASWANI A , TOMLIN C . Game-theoretic routing of GPS-assisted vehicles for energy efficiency[A]. 2011 American Control Confer-ence[C]. San Francisco, CA, USA, 2011.3375-3380.
[15]	ANDEREGG L , EIDENBENZ S . Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents[A]. Proc of the 9th Annual Int′l Conf Mobile Comp and Net (MobiCom 2003)[C]. 2003.245-59.
[16]	GROOT N , SCHUTTER B D , HELLENDOORN H . Dynamic optimal routing based on a reverse stackelberg game approach[A]. 2012 the 15th International IEEE Conference on Intelligent Transportation Sys-tems[C]. Anchorage, AK, USA, 2012.782-787.
[17]	BUCHEGGER S , BOUDEC J L . Nodes bearing grudges: towards routing security, fairness, and robustness in mobile ad hoc net-works[A]. Proceedings of the Tenth Euromicro Workshop on Parallel, Distributed and Network-based Processing[C]. Canary Islands, Spain, 2002.403-410.
[18]	BUCHEGGER S , BOUDEC J L . Performance analysis of the CON-FIDANT protocol: cooperation of nodes-fairness in dynamic ad-hoc networks[A]. Proceedings of IEEE/ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC)[C]. Lausanne, Switzerland, 2002.226-236.
[19]	MICHIARDI P , MOLVA R . CORE: a collaborative repudiation mechanism to enforce node cooperation in mobile ad hoc networks[A]. The Sixth IFIP Conference on Security Communications, and Multi-media (CMS 2002)[C]. Portoroz, Slovenia, 2002.107-121.
[20]	KOMATHY K , NARAYANASAMY P . Trust-based evolutionary game model assisting AODV routing against selfishness[J]. Journal of Network and Computer Applications, 2008,31 (4):446-471.
[21]	CUI S G , GOLDSMITH A J , BAHAI A . Energy-efficiency of MIMO and cooperative MIMO techniques in sensor networks[J]. IEEE Journal on Selected Areas in Communications, 2004,22 (6):1089-1098.
[22]	JAYAWEERA S K . A virtual MIMO-based cooperative communications architecture for energy-constrained wireless sensor networks[J]. IEEE Trans Wireless Commun, 2006,5 (5):984-989.
[23]	JAYAWEERA S K . An energy-efficient virtual MIMO architecture based on V-BLAST processing for distributed wireless sensor net-works[A]. Proc of Sensor and Ad Hoc Commun and Network[C]. Santa Clara, CA, USA, 2004.299-308.
[24]	AYFER O , OLIVER L , DAVID T . Spatial degrees of freedom of large distributed MIMO systems and wireless ad hoc networks[J]. IEEE Jour-nal on Selected Areas in Communications, 2013,31 (2):202-214.

博弈历史	行为
第t轮	转发
第t-1轮	丢弃
…	…
第t-(n-2)轮	转发
第t-(n-1)轮	丢弃

B	A
	转发		丢弃
	转发丢弃	R,RT,S		S,TP,P

参数名称	参数值	参数名称	参数值
数据分组大小	1 000 byte	R_b	2 Mbit/s
P_mix	30.3 mW	P_syn	50 mW
P_filr	2.5 mW	P_filt	2.5 mW
P_LNA	20 mW	P_IFA	2 mW
P_DAC	15 mW	P_ADC	15 mW