认知社会物联网中能量感知的编码机会路由协议

钟晓雄 陆 瑛 农英雄 陈智斌 孙 忱 卢仁浩

1(桂林电子科技大学广西可信软件重点实验室 广西 桂林 541004)2(广西中烟工业有限责任公司信息中心 广西 南宁 530001)

0 引 言

随着计算机网络与通信技术的高速发展，物联网[1]吸引了许多学术界、产业界学者的重点关注。物联网中海量的异构设备互联可以应用不同的场景，比如智慧家庭、智慧城市、智慧医疗等。其中社会物联网[2](Social Internet of Things，SIoT)是物联网的一个分支，它是在物与人之间构建社会图，并以此模式进行数据传输。目前在物联网路由研究领域的相关工作比较少。针对物联网的应急响应问题，Qiu等[3]提出了一种利用全局信息决策的保障物联网可靠传输的路由协议。Marco等[4]提出一种MAC感知的跨层优化的路由协议，它兼顾了传输可靠性和网络生存时间。但上述两种路由协议均未考虑到频谱资源对路由设计的影响。认知无线电技术(cognitive radio,CR)[5]可以提高频谱资源的使用率。面对海量设备的接入，如何利用CR技术提高频谱资源及数据传输可靠性显得尤为重要。机会路由(opportunistic routing,OR)[6]充分利用无线信道的广播特性，机会地传输数据，进而可以提供网络传输性能，如提供传输可靠性、减少传输次数等。在机会路由中，节点广播信息至其候选集节点，然后其候选集节点都有机会被选中用以传输数据，它们是合作地传输数据。由于认知社会物联网特性，机会路由这种不需要提前决定好端到端路径的路由机制非常适合。

针对认知无线网络机会路由中，研究者已经提出了一些方案。Pan等[7]给出了一种基于包传输率的优先级确定规则及最优候选集选择算法。文献[8-9]主要利用频谱资源的可用时间优化路由设计问题。Lin等[10]为了保障单信道认知物联网中的吞吐量，提出了一种频谱感知的机会路由协议。同时，针对多信道环境问题，文献[11]进一步完善了频谱感知的机会路由机制问题。通过利用基于局部信息构建的频谱信息图来设计机会路由。同时考虑链路质量及随机几何以设计地理位置机会路由。Liu等[12-13]基于异质信道占用模型，利用统计信道使用率及无线信道的物理容量作为路由决策标准，同时给出了最优候选集选择算法。文献[14]提出了一种联合信道分配与编码机会路由优化模型及一种启发式候选集及信道分配算法。同样地，Zheng等[15]提出了一种编码与频谱感知的机会路由协议。Cui等[16]基于接入机会和传输时延设计新的机会路由协议，同时为了改善频谱可利用性，还提出了一种双阶段合作频谱感知策略。Tang等[17]提出了一种基于网络编码和地理位置的机会路由协议，其主要目的是最小化平均传输次数。Barve等[18]提出一种联合考虑信道分配与增强学习的机会路由协议。在所提协议中，采用了一种在线更新路由信息的方法以更加准确地发现传输机会。Cai等[19]基于信道感知，候选集选择及包分发等目标，提出了一种跨层的最小化时延优化机会路由协议。Dai等[20]提出了一种双层的候选集选择算法，用以更加可靠地传输数据，它可以在一定程度上解决通信信道上由于PU突然到来引起的中断问题。Lin等从机会路由的角度提出了一种保障QoS的控制机制，实现了虚拟会话级别的MIMO通信。同时，为了解决衰减干扰和候选集选择问题，Lin等[22]进一步研究了机会路由协议并提出了一种认知与机会式的候选集选择算法。然而，上述所有的研究工作都没有考虑区分服务问题，针对此问题，How等[23]提出了一种面向区分服务的机会路由协议，联合考虑信道的可用性和时延特性以优化数据机会传输及功率控制。但文中并没有考虑到社会属性对机会传输的影响以及重传次数问题。受此问题启发，本文提出了一种面向多业务流的社会感知的编码机会路由ECOR(energyaware coded opportunistic routing)，同时考虑了信道分配问题。表1给出了不同机会路由的特性。

表1 认知无线网络中机会路由协议对比

续表1

本文的创新点可以归纳为：

1) 综述了近年来认知物联网中关于机会路由研究现状并给出了本文研究的动机，提出了一种面向多业务流的联合社会感知的编码机会路由和基于博弈论的信道分配策略。

2) 本文证明机会路由中候选集的选择是一个NP-hard问题。因而，我们采用了一直近似算法来解决此问题。提出了联合考虑社会属性与能耗问题的路由度量标准，进而提出一种新的基于拍卖模型的候选集选择算法，并求出其最优解。

3) 为了提高数据传输高效可靠性，在数据传输过程中，我们采用网络编码技术进行传输数据，加快数据高效可靠传输进程。同时给出了一种基于流优先级确定算法和基于干扰图的博弈信道分配算法。

4) 通过实验仿真验证了所提策略的有效性，主要从包投递率、平均时延和跳数三方面与现有工作进行对比。

1 能量感知的编码机会路由协议

在本节中，我们对所提机会路由协议进行详细的描述。我们给出了网络模型及路由度量标准的构建，基于此，提出了基于拍卖模型的候选集选择算法，同时给出了一种基于博弈论的信道分配算法。为了加快数据可靠快速传输，在数据传输过程中，采用了网络编码技术。

1.1 网络模型

本文的网络拓扑结构如图1所示，它由主用户系统(Primary System)和次用户系统组成。其中，在次用户系统中，次用户之间的通信受它们之间的社会关系和主用(primary users,PUs)的影响。SU机会式使用当前PU未使用的信道。如在数据传输(SU2->SU8)中，因为社会属性，在同等条件下它会选择SU7为中继节点进行数据传输，而不考虑SU6。

图1 认知社会物联网

在ECOR中，我们采用interweave模型[14]，在此模型中，信道采用的是时分复用技术，固定的时隙长为T，包括数据传输时长Tt和感知时长Ts，并且有(Tt=T-Ts)。此模型中有C个信道，nums个SUs和nump个PUs。每个节点都配置相同的射频数R，并工作于半双工模式。信道的使用模型为独立ON/OFF模型，并满足指数分布，速率参数分别为λbusy和λidle。

1.2 基于拍卖模型的候选集选择算法

在本小节中，我们将介绍所提机会路由协议中的候选集选择算法，主要包括基于社会属性，能量与期望传输次数的路由度量标准，拍卖模型构建。

1.2.1社会关系刻画

在现实生活中，携带智能设备(即本文中的SU)通常拥有一定的社会关系，如拥有相同的兴趣，家庭关系等。我们通过历史信息来刻画节点间的社会关系，比如相遇频繁率、社会相似度等。本文采用以下社会关系(social ties，ST)来描述节点间的社会属性，进而用以加快数据传输进程。

STi,j(T)=χSPMi,j(T)+(1-χ)socsimi,j(T)

(1)

式中：SPMi,j(T)为节点i和j之间在时间段T内的社会关系度量标准[24]χ(∈[0,1])为权重因子，在仿真实验中设置为0.5。socsimi,j(T)为节点i和j之间在时间段T内社会相似度，它可以通过以下公式计算：

socsimi,j(T)=comi,j(T)/(ni(T)+nj(T))

(2)

式中：comi,j(T)为节点i和j之间在时间段T内相同的邻居节点数目,ni(T)和nj(T)分别为节点i和j在时间段T内的一跳邻居节点数目。

1.2.2能 耗

假设EiC(T)为节点i在时间段T内成功传输一个数据包至其下游节点消耗的能量，主要包括三部分：转发数据包能耗EiF(T),收到/监听一个数据包的能耗EiR(T)，发送一个ACK包的能耗EiACK(T)，则有：

EiC(T)=EiF(T)+Nc×EiR(T)+EiACK(T)

(3)

式中：Nc节点i在时间段T内的一跳邻居节点数目。同时，假设能量消耗满足(0,1)均匀分布。

1.2.3拍卖模型

(4)

在候选集中CFS选择一组节点CFS′使得u0(CFS′)为所有节点子集中最大化，我们称之为候选集选择问题，其是一个NP-hard问题，接下来我们给出了证明过程。

定理1在ECOR中，候选集选择问题是一个NP-hard问题。

证明：如我们所知集合覆盖问题是NP-hard问题。因而只要证明候选集选择问题为集合覆盖问题即可证明定理1。假设在集合覆盖问题的一个实例中：集合U={u1,u2,…,um}，CFS={CFS1,CFS2,…,CFSn}为U的子集和一个正整数d。那么是否存在元素为d的任何子集CFS′⊆CFS使得任何U的一个元素至少属于CFS′？接下来我们证明其充要条件。

充分条件：假设CFS′为集合覆盖问题的一个实例，那么我们可以选择对应候选集CFS′为集合覆盖问题的实例，且易得到u0(CFS′)=mn-|CFS′|≥nm-d。

必要条件：假设CFS′为候选集选择问题的一个实例，则有u0(CFS′)=mn-|CFS′|≥nm-d。要得到这个值，只有一种可能性：所选的候选集覆盖在d≤m条件下的所有候选集。因此，可以看出CFS′是一个集合覆盖问题的实例。

综述所述，定理1证明完毕。

由定理1可知，在所提机会路由中，选择最优候选集问题是一个NP-hard,因此，我们必须采用近似或者启发式的算法求解。接下来，我们提出一种启发式的候选集算法，包括路由度量标准及候选集选择算法。

在所提机会路由中，路由度量标准主要考虑社会属性，能耗及期望传输次数，我们通过以下公式计算其值。

ECORi,j(T)=φ1ETXi,j(T)+φ2EiC(T)+φ3/STi,j(T)

(5)

式中：ETXi,j(T)为节点i和j之间在时间段T内的期望传输次数ETX(Expected Transmission Count)，φ1、φ2、φ3为权重参数，并且有φ1+φ2+φ3=1。

算法1候选集选择算法

1:CFSv,1←∅,CFSv,2←∅,CFSv←∅

2:for所有节点j∈N(v)do

3: 根据式(5)-式(6)计算路由度量值和阈值

4:if(ETORi(T)≤ETORthreshold(T))&&

(Ch(v)∩Ch(j)≠∅)

&&(Ch(j)∩Ch(N(j))≠∅)then

5:CFSv←CFSv∪j

6:endif

7:endfor

8: 对CFSv进行划分，其中一半候选节点存于CFSv,1,另一半存于CFSv,2

9:returnCFSv,1,CFSv,2

在选择候选集时，我们根据以下路由度量标准阈值来保证所选的候选集为可靠通信节点，即ECORi(T)≤ECORthreshold(T)。在实际中，ECORthreshold(T)可表示为：

(6)

式中：N(i)为节点i一跳候选集。

为了传输可靠性及网络负载均衡，在所选的候选集中，我们对其进行一分为二，其中前半部分为CFSi,1，另外一半为CFSi,2。

在候选集选择算法中，s为任何一个节点(除源节点和目的节点)，N(v)节点v的一跳节点集，Ch(v)为v的可用信道，CFSv为v候选集。

因此，根据上述建立的博弈模型，节点i的平均转发代价可表示为:

(7)

式中：ETXi为节点i至目的节点D的ETX。

根据上述假设EiC为(0,1)均匀分布，可得：

(8)

式中：ETXs为源节点s至目的节点D的ETX，Einitial为初始能量。同时易知vi为(0,1)均匀分布。

根据贝叶斯纳什均衡可得节点i的期望利润：

(9)

式中：P(bi<(b(vj))节点i出最低价格的概率，b(v)为策略函数，且为关于v的严格单调递增函数。

根据vi的特性，可得：

P(bi<(b(vj))=P(Φ(bi)

(10)

和

(11)

式中：Φ(b)为b(v)的反函数。

因此，我们有：

maxui=maxbi((bi-vi)[1-Φ(bi)]|CFSi|-1)

(12)

故可以求得最优出价：

(13)

同时，可以依据这个价格来确定转发优先级。拥有低价格的节点具有较高转发优先级。

1.3 基于博弈的信道分配

在机会路由中，候选集选择必须考虑信道分配以提高数据传输效率及信道使用率。因此，在本文中我们提出了一种基于博弈的信道分配算法：某段时间T内最小化信道干扰。假设信道ci和cj的干扰函数为ISci,Scj(T)。参与人集P={P1,P2，…,Pn}和参与人所选策略Sci。

(14)

因此，效用函数可表示为：

(15)

式中：Nij为ci与cj间的射频对。

根据纳什均衡[25]可得：

(16)

定理2在所提博弈模型中，至少存在一个纳什均衡解。

综上所述，定理2证明完毕。

接下来，我们给出了基于博弈论的信道分配算法，如算法2所示。在算法2中，假设信道一旦被分配则立即传输数据，当PU出现在所分配的信道上，则更新节点拥有的信道信息。

算法2基于博弈论的信道分配算法

i为网络中运行算法2的节点，Ch(i)为节点i的可用信道集合，C(R)为分配给射频R的信道集合。

1:Input:i,Ch(i)

2:whileCh(i)≠∅do

3: 根据式(15)计算效率值并且存入A中

4:endwhile

5: 根据A中元素值按递增次序对其元素进行排序

6: 根据进行U(·)分配信道

7: 把分配完的信道存入C(R)中

8:OutputC(R)

1.4 基于网络编码的数据传输

在ECOR中,在所选节点之间我们采用网络编码[26]技术用以加快数据传输进程。源节点把需要传输数据分成小块，每块含有k个数据包形如：PKT1,PKT2,…,PKTk，我们称之为原始包。然后源节点对k个数据包进行线性组合并进行发送。中间节点收到后进行判断，如果线性无关则编码后进行传输，目的节点收到足够多(大于等于k)时，进行解码操作，恢复出k个原始数据包。在ECOR，k的值设置为10。与文献[27]相似，我们采用信用计数器作为是否编码和转发的条件。每个信道对应一个信用计数器。因而，一个节点有|C|个信用计数器。信用计数的值可通过下式来计算：

(17)

式中：u(c)为信道可用概率，ρji(c)为节点j和i在信道c上的丢包率，zi(c)为期望传输次数。如果crediti(c)为正数，则节点产生一个编码包，并在信道c广播，然后计数器减1。否则不执行编码及转发操作。

在认知社会物联网中，存在多种类型业务流，因此，在所提机会路由中，我们在基于网络编码技术的数据传输中考虑了业务多样化特性。假设在中继节点中，存在多种业务流，那么转发的规则如下：

1) 对于不同的业务流，转发优先级按照事先约定好的进行转发。

2) 对相同的业务流，根据ζfi值大小进行转发，值越大转发优先级越高。

ζfi=δ1nfi(pkt)+δ2nfi(times)

(18)

式中：δ1和δ2为权重因子，并且有δ1,δ2∈[0,1]，在仿真实验中两者都设置为0.5，nfi(pkt)为当前节点i中流fi所有包数，nfi(times)为流fi经过当前节点i的次数。

2 性能评估

在本节中，我们对所提的机会路由ECOR进行性能评估，主要仿真环境为NS2[28]，CRCN模块[29]和MIT真实数据集[30]。仿真参数设置如下：

SUs的移动模型为random waypoint模型，其所在一个节点密度为400 nodes/km2的区域，SUs的传输范围为120 m，PUs为固定位置，且传输范围为300 m，PU数目为10。信道数目为10，且工作于IEEE 802.11b传播模型为Two-Ray Ground。CBR包大小为1 000字节。SU产生业务流即刻随机选择一个目的节点。射频数目为2。带宽为5.4 MB/s。仿真时间为1 000 s。业务流产生的时间间隔为[60 s,1 000 s]，路由度量标准的参数分别设置为0.4，0.3和0.3。对仿真实验我们执行100次并对下面考核性能指标求平均值：包投递率、跳数和平均端到端时延。能量模型中的参数设置EiF(T)、EiR(T)、EiACK(T)分别为3.6e-3 eu、1.8e-3 eu、0.16e-3 eu。节点的初始能量为300 eu。假设网络中存有三种类型的业务流，每种业务流数目为5，它们的优先级如表2所示。仿真实验参数设置如表3所示。在仿真实验结果中，我们对比了以下四种路由协议：MOR[20](基于双层候选集选择的机会路由协议)、OSDRP[23](面向不同业务流的机会路由协议)、CAODV[31](面向认知无线网络的AODV协议)和SoRoute[32](认知无线网络中基于社会属性的路由协议)。

表2 三种业务流的MAC参数设置

表3 仿真参数设置

1) 信道数目对性能的影响。在本组实验中，我们评估了信道数目对平均时延，跳数及包投递率等性能的影响。PUs、SUs数目分别设为10和50，PU的活动参数设为200 s。

从图2，图3可以看出，随着信道数目的增加，平均时延和跳数先从开始增加，然后趋于平稳。这是因为如果信道更多的话，那么数据得以传输的机会就越多。由于ECOR设计中考虑了社交属性与能量特性，进而比其他几种协议取得更少的时延和跳数。

图2 时延与信道数目的关系

图3 跳数与信道数目的关系

从图4中，我们可以看到随着信道数目的增加，PDR也随之增加，但是当增加到一定值时，其增加变得缓慢。这是因为信道数目更多，参与通信的机会就越大，数据传输也越快。CAODV的PDR值最小，ECOR和OSDRP的PDR值差不多，但是当信道数大时，ECOR的优势更明显。

图4 包投递率与信道数目的关系

2) SU数目对性能的影响。在本组实验中，我们评估了SU数目对平均时延，跳数及包投递率等性能的影响。信道数目为10。从图5可以看到，随着SU的增加，平均时延随之降低，这是因为越多的SU参与通信，数据的传输进程将会加快。同时，我们也发现随着SU数目的增加，ECOR的时延最小。

在图6、图7中，我们分析了SU数目对投递率和跳数的影响。结果呈现：随着SU数目的增加，投递率和跳数明显增加。由于受到PU通信的影响，当SU数目比较小时，所评估的两项性能指标都比较低，这是因为此时数据传输的机会比较小。但是在所有的路由协议中，所提的ECOR具有更好的性能，这是因为在ECOR中，联合考虑了网络编码技术并应用于数据传输过程中和基于社会属性和能量的候选集选择拍卖模型。

图5 时延与SU数目的关系

图6 跳数与SU数目的关系

图7 包投递率与SU数目的关系

3 结 语

针对认知社会物联网数据传输问题，本文提出了一种新的能量感知的编码机会路由ECOR。在ECOR中，证明了候选集的选择是一个NP-hard问题，然后提出了一种基于社会属性与能量的候选集拍卖模型，用以选择更合适的节点传输数据。同时，在选择候选集时考虑了信道分配问题，提出了一种基于博弈论的信道分配算法。另外，为了加快数据传输进程，我们采用网络编码技术，并对多种业务流提出一种新型的转发优先级确定方法。最后通过仿真实验验证了所提机会路由在时延、包投递率及跳数方面的优越性。由于在认知社会物联网中存在大量异质的物联设备，节点易受恶意节点的攻击，下一步研究工作将引入信任管理及密码学技术至安全路由设计中。