CN43-1258/TP 计算机工程与科学2012年第34卷第9期Vol. 34,No. 9,2012 ISSN 1007-130X COMPUTER ENGINEERING &-SCIENCE 文章编号:1007-130X(2012)09-0123-05 基于博弈论的物联网语义社区演化模型*IOT Semantic Community Evolution Model Based on Game Theory 王杨，张林静，黄亚坤，赵传信，陈付龙WANG Yang,ZHANG Lin-jing,HUANG Ya-kun,ZHAO Chuan-xin,CHEN Fu-Iong (安徽师范大学数学计算机学院，安徽芜湖241000)(School of Mathematics Computer Science, Anhui Normal University, Wuhu 241000, China) 摘要:针对物联网环境下的语义社区演化问题，提出了一种基于博弈论的语义社区动态演化模型。首先给出物联网语义社区(Internetof Things Semantic Community. ITSC)的定义和特征;然后提出了一种基于动态博弈论的物联网语义社区演化模型，给出了物联网语义社区预处理算法(SCPA)、博弈节点选择算法(GNSA)、基于博弈的语义社区演化算法(GTEA)及算法的性能分析。通过实际网络社区数据的仿真实验表明，演化模型能够真实地反映物联网语义社区的演化规律。Abstract: In order to discover the evolution principle of th巳semanticcommunity in the Internet of things (IOT).a new semantic community evolution model based on game theory is proposed. The con›cept of the Internet of Thing Semantic Community (lTSC) and its characteristics are presented. Then a dynamic game theory based ITSC evolution model is proposed. The Semantic Community Preprocessing Algorithm (SCPA) .the Game Node Strategy Selection Algorithm (GNSA) and the Game Theory based semantic community Evolution Algorithm (GTEA) are given. In also perform the perform›ance analysis about these algorithms. The experiment results show that the proposed model can reflect the basic principle of the semantic community in the IOT. Meanwhile. the simulation results also indicate that the proposed algorithm is effective and feasible when the actual network data set is input. 关键词:物联网;语义社区;博弈论;演化模型Key words: Internet of things; semantic community; game theory; evaluate method doi:lO. 3969/j. -130X. 20l2. 09. 023 中图分类号:TP181文献标识码:A密和缩减的规律。二是社区节点行为与社区结构之间的关系。如Backstorm等人[3J发现个体加入1 引言社区与社区结构有密切的关系。三是社区演化规近年来，物联网逐渐成为学术界和产业界双重律。如文献[4J提出了一种基于染色方法的算法框关注的焦点之一旧。物联网可以认为是将信息空架来进行社区演化分析，文献[5J综述了感知信息间扩展到物与物的彼此交流的动态服务网络。已系统中的过程动态演化研究技术。以上的研究均有的相关研究成果主要从三个方面展开:一是揭示基于线性增长特征的网络演化，而忽略了其动态随了网络演化过程中网络节点和边的变化特性。如机性。本文在假定物联网语义社区(lnternetof Leskov町等人问基于网络基本特征研究了社区致Things Semantic Community.简称ITSC)节点之带收稿日期:2012-04-13;修订日期:2012-06-25基金项目:中国博士后基金(20100480701);教育部人文社科青年基金项目(11YJC880119) 通讯地址:241000安徽省芜湖市安徽师范大学数学计算机学院Address:School of Mathetnatics Cotnputer Science, Anhui Nortnal University, Wuhu, Anhui 241000,P. R. China
124 计算机工程与科学2012,34(9) 间具有动态博弈的特性川的基础上，提出了一种基5im (丘，5)=f1(l) f2(h) = j于博弈论的物联网语义社区演化模型。首先从节e’" •工r七言.5i共5je"" -t-e 1’" (3) 点的语义信息挖掘出博弈策略;然后在考虑随机性{于1,5= 5; i 基础上，提出物联网语义社区的演化算法;最后通5ij =5im(5，5)表示5间的语义相似度，ji和5之i j过实际数据对该演化方法进行了仿真验证。其中乱、5j是任意两个语义节点概念，l是在语义概念树上的最短路径，h是它的深度。从公式(3)2 相关定义与问题描述可以得出，两个语义概念相似度关于l单调递减，关于h单调递增[lIJ;5=5im()表示5iii与代为了更好地进行问题描述，首先给出如下相关理节点之间的语义概念相似度，即某成员节点包含概念。[12，13J丸，的语义信息在A本体概念信息中的权重定义1物联网语义社区定义为六元组IT5C如公式(4)所示:={ID, N, R, A, 5，D}。它是将具有相同或者相似信息的角色语义节点构建成具有关联性的主5im(A,5;) =λ=卫~(4) 、'M题社区。其中，ID为社区的编号;N为社区的主题名称J为角色语义节点的集合，它表示其所具其中.M;表示的是该成员节点的语义概念，三JMz有的语义信息(如兴趣)需与具有相同或相似信息表示的是社区语义概念的集合。图1是物联网语的其他角色语义节点[7]关联起来;A表示语义社区义社区模型示意图。图中展示的是以34号节点和的代理节点，负责整个网络信息的中转和资源的合1号节点为代理形成的两个语义社区模型。理分配，它是通过计算语义节点的社区影响度来决定的，通常影响度最大的语义节点将成为该社区的代理节点;5表示语义节点间的相似度;D是节点之间相关联的边数。定义2(节点影响度I(i )[8J )设在物联网环境下角色语义节点集合{R}中的节点信息内容服从高斯分布，从中任取两个节点R、凡，设L、元是1、1的信息内容，其概率分布函数(ρdf)为Pi(X)、Pj (X)。那么，置信距离测度dij如公式(1)所示:F f dη=ωf I U一_Ji)1, 图1物联网语义社区模型、2σzfi -f d=ωf I (一τ_Jj)1(1) ji 3 基于博弈论的物联网语义社区的、2σJ其中，eof(f))为误差函数，dij(0ζdij ~l)是指Ri演化模型对Rj的支持程度，dij越小说明Ri支持矶的程度为了刻画物联网语义社区的动态演化过程，我越高。但是，为了说明每个节点的综合影响度，定们给出节点的博弈策略和博弈收益的定义。义公式如下所示:定义4(博弈策略)它是一个三元组集合~d(i，j) 5T=(，R)。博弈策略是个体与其他个体交互I(i) =主立A;一(2) 过程中能够选择的动作选项。本文以囚徒困境博其中Ai是Ri的影响域，可通过凤所连接的所有弈的模型为参考。其中D表示在单次囚徒困境博角色语义节点数目来衡量。弈中参考该对象历史和当前信息，若语义相似度高定义3(语义相似度5ij)它是将角色语义节时，则合作的概率就高，即采取合作策略;反之则亦点的信息内容表中的关键词概念化，并计算出概念然。R是不考虑对方的历史，随机决定合作还是背之间的相似程度。本文基于概念相似性的边"计算叛。方法帅，10J即基于两个概念在本体领域中的最短定义5(博弈收益)博弈收益是个体对行路径和所处的深度为度量，如公式(3)所示:动结果的满意程度。通常，两者之间的博弈收益用
王杨等:基于博弈论的物联网语义社区演化模型125 else if (Rj的语义相似度高11声望高)表l来表示。收益U;是当前节点与所有对象进行R，采取R策略;博弈后的总收益。else 表1双人形式博弈的收益表R，采取D策略;参与者2End) : eZl eZR End: eu I (Au,Bu) (AlR,B) lR博弈发起人需要选择博弈对手，本文从节点声参与者1望和节点距离因素出发，节点声望是在已知的局中elQ I (A,BQ1 Q1) (AQR ，β咄)人集合中，自然愿意与信誉度高的局中人进行交互矩阵中AüUj(ej;，e2j)表示在策略组合Uj(eJ; , 和博弈;节点距离是在己知的信誉度满足要求的局e2j)下的参与者1的收益，B;j = U2 (ej; ，e2j)是参与中人集合中，需要考虑距离因素，因为处于社会网者2的收益。络中局中人之间的距离会影响它们相互之间的紧博弈论的动态语义社区演化模型算法如下所密关系。那么，假设博弈发起人为): 习亏:(1)网络节点的度越大，被选择的概率越大2算法1i吾义社区预处理算法(Semantic π(kJ =兰」(5) Comm uni ty Preprocessing Algori thm，简称SC~kj PA)。j=O 其中，π(走;)是被选择的概率，k;表示节点凡的节输入:博弈的语义社区A;输出:初始化后的语义社区A'。点度，~kj是当前节点所处环境的节点总度数。For each player in population A j=O PayoH=O;/ /初始时的收益为O(2)距离自己越近的节点，和自己发生博弈的For each pair of antibodies of player 概率越大。InputCISD[n]) : / /输入每个节点的ISDd, = f 1，如th()ζ1(6) End; \ 0 ,otherwise For (i=O;i<η;l十t-)综合(1)、(2)得到博弈发起人j对个体z的总体评Get a random data, O<ran<l;/ /0到1之间取随价值:机数If(ran<) W;=δ×π(k;l十一主一Xd; (7) +0’ player’s History[i]=O; 这里的参数0', ( 0 <δ<l，O<À<l)表示/祷历史信息为0，该节点相对孤立，博弈可各个影响因子的影响力权重。当博弈发起人选择能性低祷/博弈对于时，首先根据公式计算社会网络中其余个Else player’s H口tory[i]= ISD[i]: //将初始相似度赋予历史信息体的评价值，然后根据该评价值选择出对手。当某End: 节点选择好进行博弈的节点后，采用→定的博弈策End: 略使自己的收益最大。每个节点根据自己的特性假设局中人群体规模为N。初始化阶段主要进行选择。有两个任务，第一个是语义相似度的初始化，第二算法3基于博弈的语义社区演化算法(GT个是计算局中人的历史信息。初始相似度CInitialEA) Similar Degree，简称ISD，O<ISD<l)表示演化初输入:J个语义社区;始时社区群体之间的语义相似度。输出:博弈演化后的J个语义社区。算法2博弈节点策略选择算法(GameNode Begin Input(C= (η1 ,n2 ，n3'叫，…，nm))Strategy Selection Algorithm，简称GNSA)j Initial(Cand C)://社区进行初始化1 2输入:当前节点R，:ForCi= 1: i<j:i十十)输出:节点R，选择的策略(或R)。For(k=l :k<m:k十十)Begin {该社区的语义节点选择对手D进行博弈;For(j=O:j十十:j<η)If(strategy( nk) =合作)Then { if(R，的语义相似度高&&声望高)R，采取C策略;If从nk到D无连接Then
126 计算机工程与科学2012，34(盯18 添加一条连接从n，到D;End; Else If strategy(D)二合作ThenIf(从n，到D有连接)Then删除此条连接pEnd; End; End; 节点编号通过初始化算法给出博弈开始时的群体信息图2节点度的计算比较图设置(如语义相似度等);然后从博弈树最底层对语 效率比较义节点采取对于选择算法选择博弈对象，进行单次本实验将提出的GTEA与基于染色体法的社囚徒困境博弈，并利用策略选择算法进行策略选区演化算法之间的性能进行了比较。我们选取34择;最后根据语义节点的收益采用连接调整算法对个节点集，初始社区数目是2个。如图3所示:(1)社区结构进行演化调整。与代理节点关系密切的节点集在演化过程中进行本文提出的SCPA算法对每个语义节点进行搜索比较的节点量少，在重叠区域的代理节点则需了遍历操作，则算法1的时间复杂性为O(n);GN 要搜索大量的节点;(2)两种算法在处理与代理节SA算法采取的是广度优先算法进行搜索，且对搜点关系密切的节点集时，搜索的效率相差不大，当索深度进行限制，则算法2的时间复杂性为O处理其他关系非密切的节点时，GTEA的效率明2(n); GTEA算法主要是通过对节点的局部搜索显高于染色体法。进行策略选择并根据博弈的收益进行调整连接，分35 析得出算法3的时间复杂性为OCn勺。如表2所30 口3E二j忐鸣，eze"3f 习亏。表2本文算法的时间复杂度算法时间复杂度语义社区预处理算法。(n)2博弈节点选择算法。(n) 策略选择算法。(n)2演化算法。(n) 图3GTEA与染色体法效率比较示意图 网络密度与距离变化4 仿真实验及分析 密度与距离如图4所示，通过对演化过程中的不同时间步为了评价所提模型的性能，使用Matlab软件长的社区网络密度和平均距离进行仿真表明，密度和Ucinet软件对GTEA算法进行验证，并将该演在初始阶段逐渐升高波动大，然后降低，最后逐渐化方法与Tan ti pa thananandh等人提出的方法进稳定;而平均距离则是相反，初始阶段逐渐降低，然行了对比。后升高，最后趋于稳定。这说明了社区网络在演化 社区节点度的动态演化的初始阶段节点之间的行为较活跃，而后趋于稳定。依据时间步长的变化，社区内各节点的度也在不断地变化。图2表明:(1)随着时间步长的变化， 一致性分析社区网络呈现一定的规律性，社区在开始时演化波利用Ucinet软件对多语义社区不同时间步长动较大，随着时间步长变化一段时间后逐渐稳定。的一致性演化进行了分析。图5说明:(1)社区中图示中在10轮步长时波动大，30轮后直至50轮代理节点的一致性低于0，表明代理节点随时间步时逐渐稳定。(2)分别与不同社区均有关联节点的长很难发生改变;(2)处于社区重叠区域的节点的度波动大，说明这些节点在演化过程中处于活跃状一致性波动较大，即重叠区域受到关联节点的影响态。较大;(3)重叠区域的节点一致性在演化后期逐渐
127 王杨等:基于博弈论的物联网语义社区演化模型[2J 1ure L,10n M K,Christos F. Graphs over Time:Densification laws,Shrinking Diameters and Possible Explanations[CJ // Proc of the KDD’05, 2005:177-187. [3J Backstrom L, Huttenlocher D,Kleinberg J ,et al. Group For 5 10 15 20 25 30 35 时间步长mation in Large Social Networks: Membership, Growth, and a密度一一，一一←一「牛一…叩……呵?一由于一…『…一中一…r白--，Evolution[CJ//Proc of the KDD’06,2006:44-54. 破气一斗[4J Tantipathananandh C,Berger-Wolf T Y,Kempe D. A Frame›罢2斗飞)叫一二千i work for Community Identification in Dynamic Graphs[CJ /扩E←2扎一一←一一一~一~一一一一一~一一JProc of the KDD’07,2007:717-726. o 5 10 15 20 25 30 35 40 45 50 时间步长[5J 宋巍，马晓星，胡吴，等.过程感知信息系统中过程的动态演b距离化[J].软件学报，2011 ,22(3) :417-439. 图4密度与距离的变化图[6J Mucha P J. Community Structure in Time-Dependent, Multi›趋于稳定状态，说明此时社区中的节点归属逐渐稳scale,and Multiplex[J]. Science, 2010,328(5980) :876-878 [7J Fudenber D, Tirole J. Game Theory[M]. Beijing: Renmin U›定。niversity of China Press,2010. [8J Shi Chuyi. Agent-Based Computing[M]. Beijing: Tsinghua 器-lE二二之二二十二二二二3o 5 10 15 20 25 30 35 University Press, 2007. 节点编号a初始状态[9J 王杨，张林静，严远亭.应用Max-Min策略的物联网社区构建祖!r:卫工声叫回南丐.~『甲-…唱F由喃喃喃卢喃睛都回ζC寸方法[JJ.计算机工程与应用，2012，48门的:244←248.中-b豆山---"ï5可「寸53’0 35 节点编号[10J Budanitsky A, Hirst G. Semantic Distance in WordNet:An b 10轮步长Experimenta[, Application-Oriented Evaluation of Five 号JE±:1? "土士丑Measures[C]//Proc of the Workshop on WordNet and oth 节点编号er Lexical Resources, 2001 :29-34. c 30轮步长[11J 陈汉华，金海，宁小敏，等.SemreX:一种基于语义相似度的号-iL二;ι二iiL刀之士25P2P覆盖网络[JJ.软件学报，2006，17(5): 1170-118l. 节点编号[12J Jiang J J, Conrath D W. Semantic Similarity Based on Cor d 50轮步长pus Statistics and Lexical Taxonomy[CJ // Proc of the Int’1 图5社区一致性分析Conf Research on Computational Linguistics ( ROCLING X),1997:1-15. [13J Yuhua L,Bandar Z A,McLean D. An Approach for Measur›5 结束语ing Semantic Similarity Between Words Using Multiple In›formation Sources [J]. IEEE Transactions on Knowledge 物联网语义社区演化的动态建模和仿真是物and Data Engineering,2003, 15(4) :871-882. 联网理论与应用研究的重要内容之一。我们引入了物联网语义社区和语义相似度的概念，结合社区王杨0971-)，男，安徽灵璧人，博士，网络的一般特征，提出了一种基于博弈论的语义社教授，CCF会员(E200014866M)，研究方向区演化模型。下一步我们将主要研究物联网语义为物联网、机器学习和数据挖掘。E-mail:社区仿真器的设计与实现。wycap@ustc. edu. cn WANG Yang, born in 1971, PhD, pro›参考文献:fessor,CCF member( E200014866M) ,his research interests include Internet of things, machine learning, and data min›[lJ Newman M E J. Fast Algorithm for Detecting Community Structure in Network[J]. Phys Rev E, 2004,69 (2) : 1-10. mg.
