作者：刘丽
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
社会感知网络路由及激励机制试读：
前言
随着智能移动设备的广泛应用，移动设备之间通过短距离通信技术组成的间歇式连接网络越来越多地受到人们的关注。近年来，移动设备常由人携带，与人之间的关系越来越密切。人们之间的社交关系及其运动规律在一定程度上反映了移动节点的某些特征。所以，研究者开始关注社交因素对这类移动网络的影响。因此，以社交因素为主要依据，指导网络协议设计的社会感知网络应运而生，并逐渐成为研究领域的热点。
在间歇式连接模式下，点对点的通信路径难以得到保障。移动节点之间的数据传播主要依靠其偶然的相遇机会，通过“存储—携带—转发”的合作模式实现。因此，对节点间相遇机会的预测及节点间的合作成为影响数据转发效率的主要因素。根据是否考虑自私节点，本书将社会感知网络中的数据转发分为全合作节点的路由问题和存在自私节点的激励机制问题。节点间的社群、社交强度、相似度及运动规律性等社交属性和特征潜在地隐含了节点间接触的规律性，对解决路由问题和激励机制问题具有显著的指导意义。
作者对社会感知网络中路由问题和激励机制展开了深入、细致的研究。针对网络拓扑结构变化频繁、社交因素多样化的问题，提出了基于蜂群及兴趣驱动的路由协议和基于多维度社交因素进行数据转发的路由协议。针对节点的自私特性及分布式的网络结构造成的信息维护困难等问题，提出了基于副本调节的激励机制和基于社群等量交换的激励机制。本书涉及的内容包括：（1）社群是社会感知网络中常用的一种社交属性。然而，由于频繁变化的网络拓扑结构的影响，使得社群的建立和维护都存在着一定的困难。作者提出了一组基于蜂群及兴趣驱动的路由协议BEEINFO。BEEINFO以节点对数据的兴趣为主要研究对象，隐式地划分社区，即具有相同数据兴趣的节点称为一个社群。节点只需要维护自己的兴趣，而不必维护社群的信息。另外，数据的兴趣具有分类明确、数量有限的特点，这使得社群可以自然地形成。利用群体智能，节点模拟蜜蜂采蜜的行为，对所经过的社群浓度和同社群中节点的社交强度进行动态感知，及时捕捉并适应周边环境的变化，从而实现更加高效、可靠的数据转发。基于社群模型的仿真实验表明，BEEINFO的数据转发性能优于Epidemic和ProPhet，得到更高的数据交付率、产生了更少的负载及更少的平均跳数。（2）在社会感知网络中，移动节点间往往存在多种社交联系，数据的转发路由也会受到多方面社交因素的影响。为了平衡多种社交因素的影响，实现更加可靠、高效的数据传输，作者提出了多维度数据转发协议PIS。PIS从物理临近性、数据兴趣及社交联系三个维度来考虑数据转发问题，并利用移动节点运动的规律性，分时间片来细化三个维度的影响。基于SIGCOMM 2009和INFOCOM 2006实际数据集的仿真实验表明，PIS的数据转发性能优于SimBet、Epidemic和ProPhet，获得了预期的稳定优越的性能。（3）在社会感知网络中，自私节点的存在严重影响以合作为基础的数据转发路由的性能。作者提出了基于副本调节的激励机制CAIS。CAIS从节点自身对数据的高效转发需求出发，将节点的合作程度与其消息副本数量结合起来，以激励节点积极地进行数据转发合作。即节点的合作程度越高，其消息产生的副本数量越多，从而影响节点产生的消息的转发效率。另外，CAIS利用social credit和non-social credit对社群内、外的节点操作分别管理。同时，它还采用了单源分发模式来简化credit的分配管理。仿真结果表明，CAIS可以有效地激励自私节点进行转发合作，并维持高效的数据转发性能。（4）在社会感知网络中，等量交换原则是节点间最公平的合作原则。然而，这种原则对节点间的相遇预测和转发数据的选择提出了更高的要求，难以保证数据转发的效率。作者提出了基于节点与社群等量交换的问题模型，采用宏观的观点进行节点与社群之间的等量交换，并依据此模型将自私节点的激励问题转化为节点在社群间合理分配转发资源的问题，从而形成基于社群等量交换的激励机制 Com-BIS。基于实际数据集INFOCOM 2006的仿真实验表明，Com-BIS在成功激励自私节点进行合作的同时，有效地提高了数据转发效率。第1章 绪 论
近年来，智能移动设备之间的社交因素成为延迟容忍网络、机会网络等间歇式连接的自组织网络的研究热点。结合延迟容忍网络、信息物理系统和社交网络分析理论，笔者提出了社会感知网络。社会感知网络是一种新的网络模式，它借助于移动节点间的社交联系或特征来设计网络通信的各种协议。本书主要研究社会感知网络中的数据转发问题，包括全合作状态下的路由协议和存在自私节点的激励机制。本章首先阐述本书的选题背景及意义，接着介绍社会感知网络的体系结构、社交特点和关键技术，最后介绍本书的研究内容、创新点及本书的组织结构。1.1 研究背景及意义
近年来，随着无线通信技术和网络技术的迅猛发展，普适网络（普遍存在的网络）架构逐渐形成。大量智能移动设备以前所未有的速度迅速加入网络，并占有越来越高的比重。2011年，全球移动智［1］能终端的出货量超越PC。移动手机正逐步代替个人计算机成为［2］Web访问最常用的设备。随之也产生了很多新的应用，如移动社［3］［4］［5］交网络、移动环境监测、移动城市遥感等。
大量移动设备的网络连接需求，造成3G、4G等蜂窝网络的过量通信负载，从而严重影响到应用程序的服务质量（QoS）。因此，智能移动设备借助蓝牙、WiFi等短距离无线通信技术形成的自组织网络，［6～9］如延迟容忍网络（Delay Tolerant Network，DTN）、机会网络［10～14］（Opportunistic Network，OppNet）等开始越来越多地受到人们的关注。在这类网络中，由于节点（移动设备）的移动、节点稀疏分布、通信范围有限等原因，网络常常处于间歇式连接状态。因此，节点之间通常利用偶然的相遇机会，采用“存储—携带—转发（Store—Carry—Forward）”的模式，通过多跳的方式进行数据转发传输。这类网络普遍应用于难以建立结构化、全连通网络的领域，如［15］野生动物追踪、手持设备组网、车载网络及偏远地区网络传输等。
随着越来越多的移动应用，移动设备组成的自组织网络也表现出一些新的特点。（1）移动节点密度增大。随着移动设备的增多，移动节点不再以稀疏为特点，其密度逐渐增大。这使得移动设备之间的通信更加容易。（2）移动设备更加智能，具有更大的存储空间，以及更强的计算和数据处理的能力。这些移动设备在网络中形成的巨大资源不容小觑。这使得移动设备有了更大的应用空间。（3）移动设备与人的关系越来越紧密。移动设备越来越多地在人们的生活中得到应用，如车载移动设备、智能手机等，都与人有着密切的联系。这为人们的生活带来更多便利的同时，也为研究移动设备的联网技术提供了新的方向。
早在19世纪初期，社会学家就提出“社交网络（Social ［16，17］Network）”来研究社会个体成员之间的社交联系，并形成很多著名的理论，如“小世界现象”“六度分隔理论”“中心性”“聚簇”［18］等。人们之间的社交联系和特征表现出一定的规律性和稳定性。由于人与移动设备之间的密切关系，移动设备就像是人在网络中的缩影。人们之间的社交联系及人的移动等特征，都直接或间接影响到移动设备。因此，近年来，很多研究者从社交因素入手，探索移动设备之间的通信问题，形成了很多具有社交特性的新领域，如社交机会网［18～20］络（Social Opportunistic Network）、车辆社交网络（Vehicle ［21～23］［24，25］Social Network）、机会物联网（Opportunistic IoT）、［26，27］移动社交网络（Mobile Social Network，MSN）等。
结合延迟容忍网络、信息物理系统（Cyber-Physical System，［28，29］CPS）、社交网络分析理论（Social Network Analysis Theory），笔者提出社会感知网络（Socially Aware Networking，SAN）［30］来表示以移动节点之间的社交联系或特征作为主要依据进行网络通信设计的新模式。社会感知网络可以在很多领域得到应用，具有广阔的应用前景，如口袋交换网络（Pocket Switched Network，PSN）［31，32］［33，34］、车载网络（Vehicular ad hoc Network）、信息物理［35～37］系统等。同时，它也需要来自如移动感知（Mobile Sensing）、［38］社会感知计算（Socially Aware Computing）、社交网络分析［39］（Social Network Analysis）等方面的技术支持。
社会感知网络主要有两方面的特点。一方面，社会感知网络主要研究智能移动节点通过蓝牙、WiFi等组成的自组织网络中的无线通信问题。在这一点上，社会感知网络与延迟容忍网络有相似之处。节点均采用“存储—携带—转发”的模式，通过相遇的中间节点进行多跳的转发。与延迟容忍网络不同的是，在社会感知网络中，节点更加密集，网络连接的程度更高。当然，网络中可能存在很多无关联节点，而有效节点之间仍然处于间歇式连接状态。从而，如何在大量的移动节点中找到更加合适的转发节点，就成为一个不同于延迟容忍网络中的新问题。另一方面，移动设备之间很大程度上受到社交因素的影响。由于移动设备常由人、动物、交通工具等社会对象携带，因此，移动设备之间表现出较强的社交特性。
数据转发中的路由问题和自私节点的激励问题是社会感知网络实现各种应用的基础技术，也是目前社会感知网络中的研究热点。在间歇式连接的网络环境中，数据转发的核心工作是如何选定合适的转发节点，将数据有效地传送到目的节点，并实现数据交付率、网络负载［40］及传输延迟之间的平衡。在以往的数据转发协议研究中，数据的转发效率主要通过两种方式来保障。一种方式是增加消息副本，如传［41］染病算法Epidemic。在Epidemic算法中，消息会被转发给遇到的所有节点，以此方式增加遇到目的节点的概率。另一种方式是通过预［42］测节点的未来相遇概率来选择转发节点，如 ProPhet 。在ProPhet中，节点通过历史相遇记录，维护节点间的相遇概率，从而选择与目的节点相遇概率较高的节点作为转发节点。
然而，新形势下节点的密度越来越大，采用增加副本的方式，不仅会产生大量的网络负载，而且对于存储空间有限的移动节点来说，会产生频繁的消息替换，无法保证数据转发的效率。因此，采用预测未来相遇概率的方式选择转发节点成为主要的路由策略。与频繁的节点移动相比，社交特性具有更加稳定、更加规律的特点。例如，人们的社交圈是比较有限的，具有相同爱好或具有一定社交联系（如朋友联系、同事联系等）的人接触的频率更高。人们的运动具有一定的规律性，如上班族朝九晚五的工作时间和固定的工作环境等使得他们在一定周期内做着重复运动。这些相对稳定、规律的社交联系将有利于更准确地预测节点的相遇概率。这也是社交网络路由的中心问题。
另外，数据的转发主要依赖节点间的转发合作。然而，现实生活中却存在着大量的自私节点。即节点只转发与自己相关的消息，而不愿意帮助别的节点转发。其原因主要在于，一方面，移动设备能量、存储空间等资源有限，为了节约稀缺的资源，节点可能采取自私行为。另一方面，移动设备中往往存储着重要或隐私信息，为了保障安全性，节点也会拒绝合作。自私节点的存在严重影响数据转发的效率。因此，对自私节点的激励机制也是研究社会感知网络数据转发的重点。
节点间的社交联系和特征具有更加稳定并容易获得的特点，而且与很多实际的应用有直接关系。例如，微信、微博等社交应用都会维护节点的朋友圈等信息。移动设备中会存储相关的朋友列表等信息。移动设备的操作历史也会反映节点感兴趣的数据、习惯等信息。因此，社交因素对于新形势下，间歇式连接网络的数据转发及社交应用都有着积极的作用。
社会感知网络通过感知、分析、利用节点间的社交联系和特征，实现间歇式连接网络环境下，移动设备间的数据转发和应用。其在众多领域有着巨大的应用潜力。路由技术和激励机制是社会感知网络进行应用的基础技术，其研究还存在很多实际的挑战。因此，对路由技术和激励机制的研究，对推动社会感知网络的理论研究，以及实际应用、对普适网络的实现都有着重要的意义。1.2 社会感知网络1.2.1 体系结构
社会感知网络首先通过感知移动节点的实时数据获取情景信息；其次采用分析、演绎的方法对数据进行处理，从而推断出节点间的社交联系和属性；最后利用这些社交联系和属性来制订合理的协议以支持上层应用。社会感知网络的体系结构如图1.1所示。图1.1 社会感知网络的体系结构
1.数据感知
数据感知主要指利用现实世界部署的大量传感设备，以及智能移动设备完成节点、环境等各类信息的实时感知，得到感知数据。通常包括三类信息的感知：个人感知、接触感知、环境感知。个人感知指通过人们对移动设备的操作来获取个人爱好、习惯等个人特征信息。接触感知指通过移动设备的探测和交互来记录节点间的接触信息。环境感知指移动设备对周边环境信息的感知。目前的智能移动设备一般都配备功能强大的嵌入式传感器，如计速器、数字罗盘、陀螺仪、GPS、麦克风和摄像头，从而可有效地获取各类信息。
2.分析演绎
通过对感知数据的分析、演绎，研究节点的个人特征及节点间的社交联系和特征。节点的个人特征包括节点的爱好、意愿、习惯等。节点间的社交联系和特征指节点间的社群、相似度、社交强度、移动规律等特征。节点间的社交联系和特征通常可以分为节点与社群间的［43,44］联系、节点间的联系，以及节点与环境间的联系三类。分析演绎得到的这些信息是制订路由协议和数据分发算法的重要依据。
3.社会感知网络协议
在了解个体社交行为、群体社交状态及规律的前提下，研究和制定基于社交因素的各种支持策略、协议和机制是各种上层应用的基础，包括数据转发路由协议、激励机制、数据传播协议及安全性协议。其中，数据转发路由协议和数据传播协议是社会感知网络中最基本的问题。激励机制和安全性协议则是数据转发的重要保障措施。
4.应用服务
应用服务是指研究社会感知网络理论和技术在不同领域的应用。社会感知网络的出现为许多其他领域的研究提供了新的视角，可以应用于诸如卫生健康（传染病预防工作）、智能交通管理（道路交通协同监测）、公共安全（突发事件的预警）、城市规划与发展（人口、资源、环境预测与规划）等领域。1.2.2 社交特点
在社会感知网络中，携带移动节点的主体是与人关系密切的社会对象，如人、动物、交通工具等。人与人之间通过彼此的互动交流，形成更稳定、更自然的社交联系和特征。社会感知网络获取、演绎、分析、利用这些内在的社交联系及属性来进行网络协议及应用的设计。因此，社会感知网络具有不同于延迟容忍网络的独特的特点。
1.网络的社群特征
现实中，人们的社交圈通常较小，并且比较稳定。某种社交联系［45］紧密的人们之间就构成了社群（Community）。如具有相同工作地点、生活地点或相似兴趣爱好的人经常性地联系在一起，就可以构成社群。社群中的节点通常具有较大的相遇概率和频率。在社群中，移动节点之间可以通过较少的跳数彼此联系，从而更加方便地进行通信。
2.节点行为的规律性
人们的行为具有时间、空间上的规律性。例如，人的活动存在周期循环性，员工朝九晚五的工作、学生按课表上课等，体现了人类活动在时间上的规律性。又如，人们往往对一些地点更感兴趣，访问该地点的频率更高，体现了人类活动的空间规律性。由于移动节点由人支配和控制，因此，移动节点的行为在一定程度上也表现出时间、空间上的规律性。
3.节点社交联系的异质性
在实际社会中，受到各种因素影响，人们的社交能力和社交范围［46,47］都存在或多或少的差异。因此，移动节点的社交联系也存在差异性。有的节点与其他节点的联系较多，而有的点节点则较少。将这种差异称为社交联系的异质性。节点在网络中的社交联系程度，可以使用中心度（Centrality）来表示。中心度值较高的节点，更容易成为联系其他节点的中介或桥梁。1.2.3 关键技术
1.路由协议
在间歇式连通的社会感知网络中，数据的路由采用节点之间多跳转发的模式。因此，如何预测节点间的相遇概率，从而选择合适的数据转发节点是数据转发路由协议的核心问题。节点间相对稳定、规律的社交联系和特征为转发节点的选择提供了更加可靠、有效的预测依据。社群是最常用的社交联系之一。社群中的节点往往具有较高的相遇概率。利用社群划分算法将节点划分为若干社群。那么，与目的节点在同一社群的节点更合适作为转发者。利用这一特性，研究者提出［48］［49］［50］了很多协议，如LABEL、BUBBLE RAP、LocalCom等。社群的划分算法通常比较复杂，很多研究基于节点间的社交联系如相似度、朋友联系、社交强度等构造效用函数来进行转发节点的选择，［51］［52］［53］如 SimBet、SimBetTS、HiBop等。另外，节点的移动规律及社群的移动规律也可以用来指导路由。比较著名的协议有［54］［55］DR、Predict and relay等。
2.数据传播协议
生活中存在很多应用，其传输数据的目的节点不是一个节点，而是一类节点，如广告数据的传播、电子新闻等媒体的订阅服务等。这些数据的传播不同于点对点的路由，称为数据传播协议。目前，“发布—订阅机制（Pub/Sub）”是数据传播协议中最常用的机制之一。［56］该机制把节点分为三类：产生者、消费者和代理。产生者生成用于传播的消息。消费者则是对某种数据感兴趣、接收数据的节点。代理则负责完成产生者和消费者之间的数据转发。可以看出，产生者、消费者、代理之间彼此可能并不熟悉。而一个节点在不同的时刻可能充当不同的角色。围绕着“发布—订阅机制”，各地的研究人员分别提出了不同的方案，其中最具有代表性的是苏黎世联邦理工学院和瑞［57］典皇家工学院合作完成的PodNet项目。类似的研究还包括［58］［59］［60］CCCDF、DRIP、Ripple等。另外，比较典型的，从社交［61］［62］因素来考虑的数据传播协议有ContentPlace、PrefCast、［63］［64］［65］Habit、SocialCast、MOPS等。
3.激励机制［66～
节点的自私行为会严重影响到数据路由及数据传播的性能70］。因此，对自私节点的激励机制必不可少。由于社会感知网络的间歇式连接性，原有用于无线网络的激励机制无法直接迁移到社会感［66］知网络中 。而且，考虑到社交因素，自私节点也表现出不同的特征。社会感知网络中的自私性可以分为个人自私性（Individual ［71］Selfishness）和社交自私性（Social Selfishness）两种。社交自私性是指节点对与其具有社交联系的节点表现出合作性，而对没有社交联系的其他节点表现出自私性。个人自私性则是对其他节点均采取自私行为。
目前的研究中，对于自私行为的激励机制主要分成四种类型：基于信用（Reputation Based）的激励机制、基于分值（Credit Based）的激励机制、基于等量交换（TFT Based）的激励机制和基于信任（Trust Based）的激励机制。基于信用的激励机制通过发现、惩罚自［72］私节点的方式来激励自私节点合作。如RADON、［73］［74］［75］Give2Get、MobiID及IRONMAN都采用了基于信用的激励机制。基于分值的激励机制使用虚拟的货币或者分值来调节不同节［76］［77］［78］点间的数据转发。如SMART、MobiCent、PI等属于基于分值的激励机制。基于等量交换的激励机制采用等量交换的原则，即［79］［80］两个节点交换同样多的数据。如物物交换的激励、RELICES等。社会自私行为不仅与节点的转发意愿有关，还涉及节点之间的信任关系。节点间相互信任程度越高，表示节点间的连接度越高。基于信任的激励机制主要是通过建立信任关系解决自私节点问题，进而完［81］［82］成路由转发任务。例如，TTBR算法，Trifunovic等人提出的显示（Explicit）与隐式（Implicit）社会信任方法等。基于信任的激励机制也涉及与安全性相关的问题。1.3 研究内容与创新点1.3.1 研究内容
本书针对社会感知网络中的数据转发问题进行研究，包括两个方面。一方面，在节点是全合作的状态下，研究数据的路由问题。另一方面，在存在自私节点的状态下，研究对自私节点进行处理的激励机制。
1.路由协议
1）动态感知路由研究
社会感知网络借助于节点间的社交联系等特性来进行消息的转发和路由。社群是常用的一种方式。然而，由于现实生活中存在大量的节点，而且节点常处于频繁移动的状态，使得网络的拓扑结构不断变化。因此，对于资源稀缺的移动设备来说，检测和维护社群的物理拓扑结构的代价非常大，难以实现。从某种意义上说，各社群在网络中的瞬态分布反映了节点当时的周边环境信息。因此，增强节点对周边环境的动态感知能力，有利于实时捕捉网络结构的变化，从而更加有效地进行转发节点的选择。本书在分析基于社群进行数据转发的路由的基础上，使用节点对数据的兴趣进行社群划分，并借助节点动态感知周边环境的群体智能设计路由协议，以适应动态变化的环境，提高数据转发性能。
2）基于多维度社交属性的路由研究
节点间的社交联系往往多种多样。它们在不同时刻、不同地点对节点的影响也不同。如果只利用某种社交联系，那么在某些情境，可能无法正确反映节点之间的关联，数据转发的性能必将受到不同程度的影响。那么，如何获得稳定的数据转发性能呢？针对这一问题，笔者研究了影响数据转发路由的多个维度的社交属性。从物理临近性、数据属性及社交联系三个维度，提出了基于多维度的数据转发路由协议。
2.激励机制
由于稀缺的能源、存储空间和通信带宽、时间的限制等因素，节点经常采取自私行为，拒绝为其他节点转发数据。自私节点的存在严重影响到数据转发的性能。针对自私节点的激励机制对保障高效的数据转发效率至关重要。笔者针对目前的激励机制进行了深入研究。发现在现有的激励机制中，很少考虑社交联系对激励机制的影响，而且也存在着很多问题。
1）分值的合理分配
在基于信用的激励机制和基于分值的激励机制中，信用和分值的分配依赖中央控制机制的支持。然而，在间歇式连接的网络环境中，很难维护中央控制机制。因此，信用和分值的分配难以保障。本书提出了单源分发模式，并将分值的分配工作与消息绑定，提出基于副本调节的激励机制，实现了不依赖中央控制机制的合理分值分配。
2）等量交换原则引起数据转发效率下降
在基于等量交换的机制中，节点之间常因为没有足够的消息交换而错失数据转发时机。从而严重影响到数据转发的效率。在本书中，扩大了数据等量交换的范围，提出节点与社群间进行等量交换的新模式，并利用机制设计理论将对自私节点的激励问题转化为节点在社群间合理分配转发资源的问题。提出基于社群等量交换的激励机制，有效地解决了由等量交换原则引起的数据转发效率下降的问题。
3）忽略了节点自身的需求
由于移动设备的资源限制、安全性等方面的因素，节点表现出自私性是可以理解的。只有与节点自身的需求相联系，才能够有效地激励节点进行合作。然而，目前的研究大都忽略了节点自身的需求。本书充分考虑了节点的需求，在基于副本调节的激励机制中，将节点的高效数据转发需求与节点的合作程度联系在一起。在基于社群等量交换的激励机制中，使节点在为社群作出的贡献和从社群获得的收益之间建立平衡，保障了节点自身的利益。1.3.2 创新点
本书的创新点如下：
1.基于蜂群及兴趣驱动的路由协议
为了动态适应社会感知网络中频繁变换的网络环境（拓扑结构），受到人工蜂群算法的启发，本书提出一组基于蜂群及兴趣驱动的路由协议BEEINFO（Artificial BEE Colony inspired INterest-based FOrwarding），包括三个算法：BEEINFO-D、BEEINFO-S，BEEINFO-D&S。假定以节点的兴趣分类来识别社群，BEEINFO利用节点的智能感知和计算能力，充分利用群体智能，模拟蜜蜂采蜜的行为，对所经过社群的浓度和同社群节点的社交强度进行动态感知，并依据这些信息指导数据转发策略。BEEINFO充分利用了节点的智能分析能力，能够及时捕捉并适应周边环境的变化。仿真结果表明，BEEINFO的数据转发性能优于Epidemic和ProPhet。
2.多维度数据转发路由协议
移动节点之间存在着多种复杂的社交联系，在不同时段受到不同社交属性的影响。笔者提出多维度数据转发路由协议 PIS（Physical proximity-Interest-Social relationship），综合三个维度的影响来考虑数据转发和路由问题，分别是物理临近性（决定哪些节点能够直接进行数据交换）、数据兴趣属性（决定节点交换的内容）及社交联系（决定消息转发的源节点和目的节点）。在此基础上，利用移动节点运动的规律性，分时间片来管理和分析节点的三种不同社交属性。通过比较不同节点与目的节点之间在三个维度上的相似度来决定更适合的转发节点，以达到更加稳定、可靠的数据转发。基于实际数据集SIGCOMM 2009、INFOCOM 2006的仿真实验表明，PIS获得了稳定优越的性能。
3.基于副本调节的激励机制
自私节点的存在严重影响了数据转发的效率。笔者从节点对数据高效转发的需求出发，将节点的合作程度与其消息副本数量结合起来，以激励节点积极地进行数据转发合作。提出了基于副本调节的激励机制 CAIS（Copy Adjustable Incentive Scheme）。CAIS利用social credit和non-social credit跟踪节点对社群内外节点的数据转发行为，并根据节点的social credit和non-social credit值来产生转发到社群内外的消息副本的数量。同时，CAIS还采用了单源分发模式来简化credit的分配管理。仿真结果表明，CAIS可以有效地激励自私节点进行转发合作，并维持网络中较高的消息交付率、较低的负载及较短的平均延迟。
4.基于社群等量交换的激励机制
对于自私节点来说，进行等量交换是最简单、最直接也是最公平的激励机制。但在实际应用中，直接进行节点与节点间的等量交换，往往由于交换的数据量太少，而使数据转发效率下降。本书提出基于社群等量交换的激励机制Com-BIS（Community Barter Incentive Scheme），采用长远、宏观的观点进行节点与社群之间的等量交换。Com-BIS将自私节点的激励问题转化为节点在社群间合理分配转发资源的问题，给出接近最优的方案。基于实际数据集INFOCOM 2006的仿真实验表明，Com-BIS不仅可以成功激励自私节点的合作行为，而且能有效地提高数据转发效率。1.4 全书组织结构
全书共分7章。第1章概述了社会感知网络的研究背景和意义。第2章描述了社会感知网络的研究现状，针对社会感知网络的路由协议和激励机制做了全面的分类综述，并对存在的问题进行了分析。
第3～6章，描述了社会感知网络中的数据转发问题，分为全合作节点状态下的路由协议和存在自私节点的激励机制两个方面。
第3章和第4章描述了全合作节点状态下的路由问题。研究中，以节点对数据的兴趣为依据进行社群的隐式划分。第3章中提出了一组基于蜂群及兴趣驱动的路由协议BEEINFO。节点通过模拟蜜蜂采蜜的行为，充分发挥群体智能，完成对环境和社交强度的探测和感知，并利用这些信息来动态调节数据转发策略。在此基础上，第4章中考虑了多种社交因素的影响，提出了多维度数据转发路由协议PIS，以保障实现稳定的数据传输。
第5章和第6章描述了存在自私节点状况下的激励机制问题。从节点的自身需求出发，考虑对自私节点的激励问题。第5章中将节点的数据转发效率与其合作程度联系起来，提出了基于副本调节的激励机制CAIS。第6章中利用等量交换原则，实现节点在各个社群间的交换平衡，提出了基于社群等量交换的激励机制Com-BIS。两种激励机制均对社群内外节点做了不同的处理，并考虑了节点自身的需求，做出了更加实际的假设。如在节点需求得到保障时，自私行为是完全可以被允许的。
第7章对全书进行了总结回顾，归纳了本书的主要内容和创新点，并对未来的领域研究发展进行了展望。
全书的组织结构如图1.2所示。图1.2 全书组织结构第2章 研究现状
社会感知网络借助于节点之间的社交联系及特征来解决网络中的问题。数据路由技术及自私节点的激励机制是社会感知网络进行数据传输的基础，也成为目前研究的热点领域。本章首先介绍社交网络分析理论中相关的若干社交联系和特征，然后对社会感知网络中的路由问题和激励机制问题的研究现状进行详细分析。本章内容是后续研究的重要基础。2.1 社交联系及特征
19世纪初期，法国的社会学家 Émile Durkheim 和德国的 Ferdinand Tönnies 将人与人的社交关系抽象为社交网络。社交网络分析理论通过社会网络研究人类社会中人与人之间的社交联系及特征。由于移动设备与人之间的密切相关性，人与人之间的社交联系及特征会影响到移动设备的运动。同样，移动设备的运动和接触也能反映出人们之间的社交联系。因此，社交网络分析理论和社会感知网络之间相辅相成。社交网络分析理论为社会感知网络中分析节点的社交特性提供了理论支持。社会感知网络通过对实际节点移动及联系的分析，为社交网络分析提供现实的依据。本节将介绍目前在社会感知网络中常用的若干社交联系和特征。2.1.1 社群［83］
社群的概念来自社交网络分析理论中的“小世界现象”。1967年，哈佛大学的社会心理学家Stanley Milgram研究发现，在一个成员众多的社会网络中，可以按照某种方式来建立成员之间的关系链，平均最短关系链的链长远小于人群的人数。他将这种现象称为“小世界现象”。社群是指具有直接或间接社交联系的人组成的关系紧密的群体。如具有相同的兴趣爱好、工作环境、学习环境、生活环境的人之间就可能构成社群。通常，社群中的成员之间的社交联系比社群外成员的社交联系要强烈。因此，社群内的成员往往更加频繁地相遇和接触。节点间的社群特性在社会感知网络的路由协议设计中具有积极的作用。2.1.2 中心度
幂律分布（Power Distribution）是指两个随机变量服从形如 −γy=Ax 形式的分布。它是一种非常常见的分布模式。社交网络中的节点往往符合幂律分布，即大多数的联系集中在少量的节点上。也就是说，同一社群中的各个节点之间的联系程度存在着差异。实验表明，网络中30％的节点具有较强的数据转发能力，而70％的节点的转发［29］能力较弱或处于中等水平。节点的中心度表示节点在社群中连接其他节点的能力，即节点在社群中的重要程度。中心度较大的节点具有更强的连接其他节点的能力，被称为中心节点。借助于社群中的中心节点，可以提高社群内数据传播的效率。因此，中心度也是目前常用的一个重要社交特征。
Freeman提出了三种中心度：度中心度（Degree Centrality）、介数中心度（Betweenness Centrality）、接近中心度（Closeness ［84，85］Centrality）。
1.度中心度
度中心度是指网络中与节点具有直接社交联系的节点的比例［86］。假设网络中有N个节点，则第i个节点的度中心度 DegCi可以通过式（2.1）计算得到。
式中，deg（i）是与i节点有直接社交联系的节点的数量。如果一个节点的度中心度值较高，则说明此节点在网络中较活跃，与其他节［51］点具有比较多的关联。
2.介数中心度
节点i的介数中心度表示网络中包含节点i的最短路径与所有最短［87］路径的比率。节点i的介数中心度 i BetC可以由式（2.2）计算得到。
式中，spj,k是网络中连接节点j和k的最短路径长度，spj,k（i）是网络中连接节点j和k且经过i的最短路径长度。介数中心度可以用来衡［88］量控制网络中节点信息流通的程度。介数中心度较高的节点可以桥接两个不相邻的节点，并可能影响社群之间的数据流通程度。因此，介数中心度可以用于社群间的有效连接。
3.接近中心度
节点i的接近中心度是指从节点i到网络中其他节点的总路径长度［89］的转置。节点i的接近中心度 CloCi可以由式（2.3）计算得到。
式中，dis（i,j）是节点i和j之间的最短路径长度。如果节点的接近中心度值较高，说明此节点到网络中其他节点的最短路径较短。当需要一个节点向网络中所有节点广播消息时，可以使用接近中心度来［90］选择节点。2.1.3 相似度
长期以来，社会学家普遍认为社交网络具有一定的传递性。例如，如果两个人具有若干共同的朋友，那么他们认识的可能性也比较大。［31］这种现象也被称为聚簇（Clustering）现象。节点之间的相似度通常使用节点间的共同属性（如共同的朋友、数据兴趣等）的重合程度来表示。当一个节点与消息的目的节点的相似度较高时，两个节点相遇的概率较大。因此，相似度常被用于社会感知网络中数据转发节点的选择。2.1.4 社交强度
社交强度的概念是由Granovetter在1973年提出的，用来表示接［91］触时间长短、情感强度、共同爱好多少等人与人之间的联系程度。社交强度用量化的方式表示网络中节点之间的社交联系的强弱。社交强度高的节点比强度低的节点具有更多的相遇机会。目前，常用的社交强度标识包括相遇频率、亲密度、接触长度、互惠程度、共同的社［92］会环境、信任程度等。与目的节点具有较高社交强度的节点可以作为数据转发节点。Granovetter的研究表明，社交强度较弱的节点也可以有效地帮助社群间的连接。故而，社交强度较弱的节点在数据广播中也可以得到很好的应用。2.1.5 运动规律性
通过分析实际移动轨迹，研究者发现人们的运动具有时间规律性［93～95］和空间规律性。时间规律性表示从长期的时间看，人们的运动具有规律性。例如，人们从周一到周五进行工作时，往往遵循一定的工作运动模式。空间规律性表示人们通常频繁并有规律地访问相对固定的若干区域。例如，学生常常在宿舍、教室、餐厅、图书馆等区域规律运动。这两种运动的规律性可以有效地帮助预测节点未来的运动轨迹，从而为转发节点的选择提供参考。2.2 路由协议
由于节点的频繁移动，数据在传送过程中难以寻找和维护一条端对端的通信链路。因此，近年来这类间歇式连接的网络如延迟容忍网络、机会网络等，通常采用“存储—携带—转发”的模式，利用节点间的相遇机会来完成数据传输。因此，数据转发路由的主要任务是进行转发节点的选择和转发策略的制定。而节点间相遇机会的预测就成为路由设计的关键。社会感知网络将节点间的社交联系和属性作为路由设计的主要依据。与节点的频繁移动相比，节点间的社交联系则表现出相对的稳定性和规律性。因此，社交联系就成为预测未来相遇机会的更加理性的选择。
社群是数据转发路由中常用的概念。按照路由协议是否与社群相关，将近年来的路由协议分为两类：基于社群的路由协议（Community-based Routing Protocol）和独立于社群的路由协议（Community-independent Routing Protocol）。2.2.1 基于社群的路由协议
目前的很多路由协议的设计都与社群有关。社群中的节点比社群外的节点具有更高的相遇概率。这一特点可以有效地帮助节点预测相遇机会、选择适合的转发节点。社群通常需要社群检测（Community Detection）算法的支持。社群检测算法按照一定的规则将整个社交网络划分为若干相对独立的社群。不同的社群在节点移动中可能相互交叉。基于社群的路由通常将数据转发过程分为两个阶段：社群间数据转发（Inter-community Forwarding）和社群内数据转发（Intra-community Forwarding），如图2.1所示。图2.1 基于社群的路由协议的数据转发过程
如果携带消息的节点与消息的目的节点不在同一社群，则要选择转发节点将此消息转发到目的社群（目的节点所在的社群）。这一阶段称为社群间数据转发。当消息被转发到目的社群后，就开始了社群内数据转发阶段。这一阶段要求尽快将此消息转发给目的节点。所以，通常先将消息转发给中心节点，然后由中心节点将此消息转发给目的节点。
最早基于社群进行路由研究的是Hui和Crowcroft等人。在INFOCOM 2005 和INFOCOM 2006两次国际会议中，Hui等人开展了人类移动性实验，对前来参会人员的移动轨迹和接触信息进行了跟踪［28］记录和分析。对数据集中相遇时间间隔分布的实验分析表明，社群内的节点比社群外的节点具有更高的幂律系数，即社群内的节点之间接触更加频繁。相遇时间间隔是指两个节点连续两次相遇之间的时［96］［48］间间隔。在实验中，Hui等人提出了LABEL协议。在该协议中，为每个节点都设置一个标签来表示其社群关系。携带消息的节点选择目的社群中的节点为转发节点。
在基于社群的路由中，社群的检测和构建算法至关重要。在LABEL协议中，通过节点的社交联系指定社群。这是一种简单的方式，但是有太多的局限性。很多社群检测算法基于对历史移动轨迹的分析来建立社群。Hui等人基于节点社交联系图实现了在线分布式社群检［49］测，提出了三种算法：SIMPLE、K-CLIQUE和MODULARITY。［49］同时，Hui等人提出了BUBBLE RAP路由协议。BUBBLE RAP采用K-CLIQUE算法，根据历史相遇记录生成社交联系图来发现社群。它将社群分层管理，处在下层的是较小的社群。下层的多个社群构成上层的较大社群。依次类推，所有节点构成了最上层的最大的社群。BUBBLE RAP利用社群中的中心节点构建并维护了全局等级树（Global Ranking）和局部等级树（Local Ranking）。当数据进行转发时，首先依据底层的全局等级树将数据向上传递，直到传递到与目的节点属于同一个社群为止。然后沿着全局等级树将数据向下传递，直到传递到目的节点所在的最小的社群为止。最后，在此社群中根据局部等级树将数据转发给目的节点。［97］
Bulut和Szymansk 基于节点间的直接和间接朋友联系标识节点间的社交联系，并由此建立基于朋友的社群。他们认为亲密的朋友联系具有接触频率高、接触时间长并存在规律性三个特点。因此，他们定义了社会压力指标（SPM）和有条件的社会压力指标（Conditional SPM）来分别表示直接和间接朋友联系，并通过分析历史接触记录来维护这两个指标的值。直接或间接朋友联系超过临界值的节点就构成了朋友社群。而且，为了表示时间上的差异，为每个节点在一天中不同的时段建立了不同的朋友社群。当进行数据转发时，将选择目的社群中朋友联系较强的节点作为下一个转发节点。［54］
Zhou等人观察发现，节点的习惯性运动有助于减少平均通信延迟。而偏离习惯的行为则会严重影响路由的性能。他们采用类似于社群的形式，提出可以处理偏离习惯行为的DR路由协议。DR协议将网络按照聚簇的特性分为若干个临近的社交簇。数据转发时，为每个簇转发一个消息副本。用这种方法，来弱化偏离行为对路由性能造成的影响。
另外，很多研究考虑了社群间的联系，指定了社群间的数据转发［50］策略。LocalCom通过分析历史的相遇频率、相遇长度及分离周期等信息，定义了名为“相似度”的指标来标识节点之间的相似程度，并依据这个指标建立相邻图（Neighboring Graph）。根据相邻图和相关的相似度，分布式地发现社群。LocalCom为社群间和社群内数据转发制定了不同的策略。LocalCom将在社群间有直接朋友联系的节点设置为网关节点（Gate）。基于介数中心度，采用静态预剪枝（Static Pre-pruning）和动态剪枝（Dynamic Pruning）两种方式来从网关节点中选择转发节点，完成社群间的转发。在社群内，则通过比较相似度指标来选择更合适的转发者。［98］［99］
Gently融合了CAR和LABEL两种算法。CAR是一种上下文感知的自适应路由。LABEL算法只选择目的社群中的节点进行转发，在到达目的社群前，节点只能携带消息等待；到达目的社群后，则采用Epidemic的方式来散播消息。Gently采用类似CAR的算法来弥补LABEL的缺陷。在遇到目的社群的节点前和进入目的社群后的两个阶段中，采用CAR提高转发性能。［100］
Wong等人考虑社交关系和移动模式等解决路由问题，提出基于社交关系的机会路由（Social Relation Opportunistic Routing，SROR）算法。在SROR中，断连社群构成一个集合，每个节点都属于某个确定的社群。SROR执行三个子过程，分别匹配社交信息、社交连通性及社交交互信息，来实现转发节点的选择。［101,102］
Xiao等人提出一个分布式的基于社群的路由算法。该文将节点经常访问的“社群”命名为“家”，建立“家感知（Home-aware）”的社群模型。在扩展的关系图中采用反向迪杰斯特拉算法为每个“家”计算最短的预期延迟，为路由选择提供依据。另外，该算法还把中心度的概念从单一的节点扩展到节点组。2.2.2 独立于社群的路由协议
由于网络的拓扑结构不断地动态变化，使得社群的检测、构建和维护面临很大的挑战。因此，很多研究者相继提出了不依赖社群的路由协议，即独立于社群的路由协议。在这类路由协议中，节点通过维护与自身有联系的其他节点等部分网络信息，建立自我网络（Ego ［51，92］Network）。从而从局部衡量节点间的社交联系或特性，建立相应的效用函数。然后通过效用函数来计算，选择满意的转发节点。［51］
SimBet基于自我网络，利用介数中心度和节点与目的节点之间的相似度信息建立效用函数。当节点相遇时，首先交换彼此的接触列表来更新介数中心度和相似度信息。然后交换消息的目的节点信息，计算并比较效用函数，从而将消息转发到效用值较高的节点中。［52］SimBetTS在 SimBet的基础上，考虑了节点间的连接强度信息。［103］SimBetAge则添加了新鲜度（Freshness）的概念来指导数据转发。
节点的上下文信息对数据的路由也起着积极的作用。ProPhet利［104］用节点的历史相遇记录来预测未来的相遇概率。MobySpace、［105］［106］MVRA 、MaxProp利用了节点的移动模式和频繁访问的区域来指导路由。而节点间的社交联系也可以看作一种重要的上下文信［53］息。HiBop通过综合考虑节点间环境的相似性、当前及历史的行动信息来分析节点间的熟悉程度，从而确定转发策略。受PageRank［107］思想的启发，Mibaa等人利用在线社交网络平台或应用程序（如Facebook、Orkut、MySpace等）中的社交信息构成社交联系图，提出了PeopleRank算法。具有较高PeopleRank值的节点在网络中的中心度较高，更适合作为数据的转发者。
另外，人们移动的规律性也常用来作为选择数据转发者的参考依［54］据。Predict and relay 使用齐次半马尔可夫过程模型来描述节点在若干可能位置间的移动。节点在这些位置间的移动和逗留的时间概［108］率分布则根据节点的历史移动记录来决定。Nazir等人假设人们每天按照相似的移动模式运行，以这种具有时间特性的社交相遇为基础，建立了内容分发系统。
时间和空间因素也是十分重要的。历史时间和空间信息往往表现了人们的运动模式。很多研究基于累计接触信息的方式来制定路由决［109 ］策，如ProPhet。Gao等人观察发现，人们在短期内的短暂社交接触模式与累计接触模式存在着一定的差异。这种短暂社交接触模式反映了节点接触分布、网络连接及社群结构等的短暂特征。通过分析MIT reality、INFOCOM和UCSD数据集的信息，Gao等人建立了基于短暂接触模式的数据转发策略，有效地提高了数据的转发性能。［110］
Mei等人则基于节点的兴趣相似性，并结合社会感知和状态无关（Stateless）的方法提出了SANE策略，该策略的有效性被Díaz等人在文献［111］中得到验证。［112～122］
相关的算法还有很多，在此不一一列举。本书主要考虑数据的单播问题，即节点到节点一对一的数据传输。近年来的很多研［122～128］［129～134］究还涉及路由中的拥塞问题、移动模型问题及多播
［135～137］问题。在此，对这类问题不再做详细描述。2.3 激励机制2.3.1 激励机制概述
节点之间的合作是社会感知网络中数据转发路由的基础。很多研究都假设网络中的节点具有合作意识，是愿意参与合作的“利他主义者（Altruism）”。然而，在现实生活中，却可能存在很多不愿参与合作的节点，如自私节点、恶意节点。这些节点总是希望尽量节省自己的资源，并将利益最大化。自私节点为了节省稀缺有限的能量、存储空间等资源，只对与自己相关或自己感兴趣的数据进行转发。恶意节点则故意破坏网络的主体功能，它们可能会通过故意丢包或制造虚假包等措施来扰乱数据转发过程。本书只涉及自私节点。因此，接下来主要对自私节点加以描述。
研究者将节点的自私性分为个人自私性和社交自私性。从社交联系的角度出发，自私节点往往愿意为与其具有社交联系（如朋友、同事、同学）或在同一社群的节点提供转发帮助。根据社交联系强度的不同，社交自私性节点对同一社群中的节点也可能采取不同程度的合作，尤其是在其资源紧张的情况下。这种与社交联系相关的自私性被称为社交自私性。与社交自私性不同，个人自私性对其他所有节点均采用同样的自私态度。
很多研究从不同方面考查了合作节点和自私节点对间歇式连接网络下数据转发路由的影响。结果表明，与无合作情景相比，节点的合作（即使是有限的合作）可以很大程度地提高数据转发的效率。节点的自私行为对网络的路由性能有着很大的负面影响。因此，激励自私节点参与合作是一个必不可少的重要问题，这就需要激励机制的支持。
社会感知网络中的激励机制旨在激励节点的合作意识，发现自私行为、惩罚自私节点。由于网络连接的频繁中断、有限的资源限制及较长的延迟，使得应用在无线网络上的激励机制无法有效地应用在间歇式连接的网络中。因此，间歇式连接网络下的激励机制引起了很多研究者的关注，成为目前的研究热点之一。
近年来，解决自私问题的激励机制可以分为四个类别：基于信用的激励机制（Reputation based Incentive Mechanism）、基于分值的激励机制（Credit based Incentive Mechanism）、基于等量交换的激励机制（TFT based Incentive Mechanism）和基于信任的激励机制（Trust based Mechanism）。前三种激励机制是传统的激励机制。基于信任的机制则主要从节点间的信任出发，认为参与合作的节点是值得信任的节点。社交自私性表现了一定的信任关系，我们把与社交自私性相关的机制归到基于信任的激励机制中。同时，这种机制也涉及部分安全问题。2.3.2 基于信用的激励机制
基于信用的激励机制采取识别自私节点，并对其惩罚的方式（如将其排除在网络外）激励节点进行合作。节点的合作转发行为可以增加其信用值。具有较高信用的节点在进行数据转发时，具有较高的优先权。自私行为则会使得节点的信用值下降。当激励机制探查到一个节点信用值低于临近值时，就认为此节点的信用差。这时，激励机制通过广播的形式通知网络中的其他节点，从而将此节点从网络中排除。［72］
RADON是一个基于信用的数据转发协议。在 RADON的信用管理系统中，设置了看门狗并通过发送和接收名为“正反馈消息（Positive Feedback Message）”的特殊消息来检测节点的转发行为。然后，综合考虑节点的信用和与目的节点相遇的概率来制定转发策略。RADON能够有效地阻止节点随意丢包、随意转发等恶意行为，并能够在恶劣的环境下提高网络性能。［73］
Give2Get包含两个阶段：转发阶段和测试阶段。在转发阶段，产生消息的节点S将消息转发给其首先遇到的两个节点，并与节点协商加密会话密钥。假设节点B转发了此消息，则B寻找两个节点继续转发过程。这样，每个节点都可以找到两个节点来证明其转发行为。当节点B再次遇到节点S时，则开始测试阶段。如果节点B能够给出两个转发证明或者消息仍在其存储器中，则说明节点B具有较高的信用。否则，节点S将节点B的自私行为在整个网络中进行广播。这种情况下，如果节点B拿不出有力的证据来证明S有误，则将被驱逐出网
试读结束[说明：试读内容隐藏了图片]