Efficient Search Method for IoT Entities with Similarity Adaptive Estimation
-
摘要:
针对现有相似实体搜索方法缺乏对于观测序列长度的自适应性,且搜索过程数据存储开销过大,搜索结果准确性较低的问题,该文提出相似度自适应估计的物联网实体高效搜索方法(SAEES)。首先,设计了轻量级观测序列分段表示方法,对传感器采集的实体原始观测序列进行轻量级分段压缩表示,以降低实体观测序列的存储开销。然后,提出了观测序列相似度自适应估计方法,实现对不同观测序列长度的实体相似性的准确估计。最后,设计了高效的相似实体搜索匹配方法,依据所估计的实体相似度进行实体的准确搜索匹配。仿真结果表明,所提方法可大幅提高相似实体搜索的效率。
Abstract:The existing similar entity search method has poor adaptability to the length of the observed sequence, and the data storage overhead in the search process is too large, and the accuracy of the search result is insufficient. To this end, an efficient search method is proposed for the IoT Entity Search with Similarity Adaptive Estimation (SAEES). Firstly, in order to reduce the storage overhead of the entity observation sequence, a lightweight method of segmentation representation of the observation sequence is designed to perform a lightweight segmentation compression representation of the original observation sequence of the entity collected by the sensor. Then, in order to achieve an accurate estimation of the similarity of entities with different observation sequence lengths, an adaptive estimation method for observation sequence similarity is proposed. Finally, by exploiting the designed efficient similar entity search matching method, the exact search matching of the entity is completed according to the estimated entity similarity. The simulation results show that the proposed method can greatly improve the efficiency of similar entity search.
-
Key words:
- Internet of Things (IoT) /
- Entity search /
- Similarity /
- Adaptive estimation
-
1. 引言
无人机蜂群是由若干配备多种任务载荷的低成本小型无人机组成,参照蜜蜂等昆虫的集体行动模式,在人类指挥或监督下共同完成特定作战任务[1]。无人机蜂群能够极大增强无人机的通信能力和抗毁伤能力,扩展无人机对战场信息的感知获取能力,提高无人机协同执行任务的能力,以适应未来空战的需求[2]。
自无人机应用以来,安全问题就一直伴随而生,传统的无线电通信在实际运用中的无线电静默、无线电监听、电子干扰等情况将影响无人机间链路的正常通信[3],导致产生错误的控制指令,致使无法执行任务。而无线“日盲”紫外光通信主要是采用200~280 nm的紫外波段光波作为传输介质,利用大气中的粒子、气溶胶、灰尘等微粒对“日盲”紫外光的散射进行信息传输的一种新型通信方式。由于紫外光通信具有低窃听率、低位辩率、全方位性、抗干扰能力强、可用于非直视(Non-Line-Of-Sight, NLOS)通信、全天候工作、无需捕获、对准和跟踪(APT)等优点[4],能够满足复杂的战场环境中无人机的可靠隐秘通信需求。
在军用领域,无人机蜂群可用来进行情报侦察和战场监视[5],文献[6]提出了一种基于动态预测的无人机自组织网络分簇算法,能有效提高簇结构的稳定性,但未考虑节点能耗对网络生存周期的影响;文献[7]中结果表明,选择合适的簇首选举方案对提高多无人机系统的能源效率是至关重要的;文献[8]提出了合理的任务分簇优化指标,从而提高多无人机协同侦察能力,但文中未考虑节点能量耗尽对任务执行效率的影响。基于以上分析,为平衡无人机间信息传输能耗,延长无人机蜂群的侦查时间,本文提出一种基于无线紫外光隐秘通信的侦察无人机蜂群分簇算法。首先建立无人机蜂群分簇模型,并通过推导获得无线紫外光NLOS(c)通信方式下无人机节点能量消耗的理论表达式,其次从簇首选举及簇的建立两方面对经典LEACH(Low-Energy Adaptive Clustering Hierarchy)分簇算法进行改进。
2. 紫外光非直视通信模型分析
通常,无人机间进行紫外光非直视通信时,主要以低空大气为传输介质,光波在大气中传播时,大气气体分子及气溶胶的吸收和散射会引起光束能量衰减[9]。非直视无线紫外光散射通信中最终到达接收端的紫外光以单次散射为主[10],所以本文以单次散射链路模型作为研究对象。
2.1 非直视单次散射通信模型
紫外光单次散射链路模型的分析以椭球坐标系为基础,将紫外光发射装置与接收装置分别安放在椭球坐标系的两个焦点上,得到基于椭球坐标系的紫外光单次散射链路模型如图1所示。
在
t=0 时刻,能量为Et 的脉冲经TX 以发散半角θt 发射后,沿着发射角为βt 的方向,经各向同性介质散射和吸收后到达距发射机距离为r1 的V 内一点P 。将微分体积元δV 包围点P 看作一个2级光源,其单位圆锥角发射的能量是散射角θs 的函数,表达式为δRP=δQPP(μ)/4π ,其中,δQP=ksHPδV ,HP 为点P 处能量,μ=cosθs ,P(μ) 为单散射相位函数。由于紫外光散射过程中分子的散射作用多强于悬浮颗粒的散射,因此在理论计算中,通常只考虑瑞利散射,而忽略悬浮颗粒的米氏散射作用[11]。光脉冲到达探测器的时间为
t=(r1+r2)/c ,ξ=ct/r ,δξ=cδt/r ,c为光速,则接收机探测器接收到的能量为Er=EtcksP(μ)ArΩtr∫ξmaxξmin∫η2(ξ)η1(ξ)∫ϕ2(ξ,η)ϕ1(ξ,η)2exp(−kerξ)cos(ζ)ξ2−η2dξdηdϕ (1) 其中,
ζ 是接收机、微分体积元连线矢量与接收轴的夹角;cos(ζ) 用来求接收机探测到的有效面积。由式(1)可看出,非直视单次散射模型下接收机探测器接收到的能量公式复杂,计算量大,因此选用简化非直视通信模型对能量损耗进行分析计算。2.2 非直视通信光链路模型
根据接收端与发送端仰角可将紫外光非直视通信分为NLOS(a), NLOS(b)和NLOS(c)3种通信方式[12],其中,NLOS(c)通信方式下发射仰角和接收仰角均小于90°,属于定向发送、定向接收方式,传输链路损耗最小,通信距离最长,通信带宽最宽[13],更能满足无人机蜂群在飞行时的通信需求。由于该模式下发射圆锥和接受圆锥的相交体积相对较小,可采用文献[14]中的信道模型,将相交部分近似为一个圆锥台,通过大圆锥体积
Vmax 和小圆锥Vmin 做差求得,则能量衰减公式简化为L=EtEr≈[24rsinβtsin2βr(1−cosθt)⋅exp(ker(sinβt+sinβr)sinθs)]/[ksP(μ)Arβ2tβrsinθs⋅(3sin2βr+θ2rsin2βt)] (2) 3. 无人机蜂群分簇算法
3.1 分簇模型
无人机蜂群采用“长机—僚机”飞行模式[15],有统一的飞行方向速度,每架无人机上均挂载紫外光通信发收装置,并且假设各无人机间通信时数据的接收方向彼此可知。所有僚机节点都是同构的并且地位平等,都能充当簇首节点或成员节点,每个节点都有一个唯一的标识(ID)。
如图2所示,在分簇的拓扑管理机制下,根据一定的机制算法在每个簇内选取某个僚机节点作为簇首,用于管理或控制整个簇内成员节点,协调成员节点之间的工作,负责簇内信息收集、数据融合以及簇间转发,最后由簇首僚机将融合后的数据传输给长机。成员僚机的功能比较简单,不工作的节点可以处于休眠状态,在持续工作一段时间之后,网络重新进入启动阶段,进行下一轮的簇首僚机选取并重新建立簇。
3.2 能耗模型
无人机蜂群在飞行中采用无线紫外光通信能量消耗模型,主要包括以下3部分:发送数据能耗
ETx 、接收数据能耗ERx 、数据融合能耗Ec 。由式(2)可知紫外光NLOS(c)通信方式下的能量衰减L ,当发射脉冲能量ET 确定时,可得传输损耗能量为EL=ET(1−1/L) (3) 为了获得可接受的信噪比,无人机节点发射
k bit的数据到距离为d 的位置,消耗的能量由发射数据损耗和能量衰减损耗两部分组成,即ETx(k)=k(ET+EL) (4) 无人机节点接收
k bit数据消耗的能量为ERx(k)=kER (5) 其中,
ER 表示接收比特数据消耗的能量。此外,数据融合也消耗一定的能量,假设邻近无人机节点侦查采集的数据具有一定的冗余度,簇首可将其成员的数据和自身的数据融合成一个长度固定的数据包,然后发送给长机。融合过程中消耗的能量
Ec 为Ec(M,k)=(M+1)kEDA (6) 其中,
EDA 表示融合比特数据消耗的能量,M 为簇内成员的个数。3.3 算法思想
无人机蜂群分簇算法的执行过程是周期性的,每轮循环可分为簇首选举、簇的建立和稳定数据传输3个阶段。
(1) 簇首选举:LEACH分簇算法[16]中的簇首选举算法是分布式的算法,每个僚机节点独立自主地决定是否为簇首。选举时,僚机节点产生一个0~1之间的随机数,若该随机数小于阈值
T(n) ,则发布自己是簇首的公告信息,其中,T(n) 中popt 设为常数,表示簇首节点在无人机蜂群僚机节点中所占百分比的期望值。由于LEACH算法中簇首是随机选取的,不能保证簇首在网络中的分布,而簇首的分布将决定该轮中网络的能量损耗状况。因此,改进算法中簇首选举基于僚机节点的剩余能量和网络中僚机节点的平均能量的比值,剩余能量高的僚机节点可以优先选举成为簇首节点,使簇首的选择能够适应能量的变化。然而在计算网络平均剩余能量时需要知道网络中所有僚机节点的剩余能量,实现起来比较困难,并且会额外增加网络中的能量消耗,因此考虑采用平均剩余能量的估计值代替实际网络中平均剩余能量来计算节点的簇首选举概率。假设在每一轮中僚机节点平均消耗能量,
r 为当前选举的轮数,且网络生存时间为rmax ,网络的初始总能量为Ea ,则第r 轮中僚机节点的平均能量为¯E(r)=1nEa(1−rrmax) (7) 估算出每轮僚机节点的平均能量后,将其作为参考值与僚机节点的剩余能量进行比较,大于平均节点剩余能量的节点选择概率增加相应的值,剩余能量小的节点选择概率减少相应的比例,则每个僚机节点的簇首选举概率
pi 为pi=popt[1−¯E(r)−Ei(r)¯E(r)]=poptEi(r)¯E(r) (8) 此时网络中簇首的选举门限定义为
T(n)={pi1−pi(rod1pi),n∈G0,其他 (9) 其中,
G 是在最近1/pi 轮中没有当选过簇首的节点集合。通过该簇首选举算法,每个僚机节点都会在1/pi 轮中当选一次簇首节点。(2) 簇的建立:簇首被选择出来后,每个簇首节点广播当选消息到周围僚机节点,LEACH算法中其他成员节点根据接收到的信号强度选择距离
dC 最小的簇首并加入,同时通知相应的簇首。然而若簇首位置过偏会导致部分簇内节点通信半径过大,网络能耗不均匀,因此,考虑同时计算与长机之间的距离dL 。若dC <dL ,则该成员节点决定加入这个簇,并发送请求消息到对应簇首;若dC >dL ,则该成员节点不加入任何簇,直接发送数据至长机。(3) 数据传输:在稳定数据传输阶段,簇首节点采用时分复用方式为簇中每个僚机节点分配向其传递数据的时间点,簇内节点将数据发送给簇首,簇首进行数据融合并把结果发送给长机。簇首需要完成数据融合、与长机通信等任务,能量消耗较大。因此,每一轮结束要按照上述方法重新选择簇首,以平均分担中继通信业务来均衡能量消耗。
4. 仿真分析
4.1 实验参数设置
仿真实验均基于同一场景,在仿真区域内部署100个无人机节点,长机节点位于区域的中心处,所有无人机节点设有统一的飞行方向速度,信息传输速率为10 kbps,为提高通信距离部署4×4 LED阵列且采用OOK调制。仿真实验的具体参数见表1。
表 1 实验参数参数 取值 节点数 100 节点通信能量 300 J ET 8.0 μJ ER 8.0 μJ EDA 0.8 μJ 波长λ 266 nm 吸收系数ka 0.740×10−3 m–1 散射系数ks 0.515×10−3 m–1 接收孔径面积Ar 1.92 cm2 瑞利散射相函数参数γ 0.017 斜发收βt, βr 60° 斜发收θt, θr 15° 4.2 算法对比分析
仿真中LEACH表示采用经典LEACH分簇算法所得结果,ICHE-LEACH(Improvement of Cluster Header Election in LEACH)表示采用改进簇首选举算法后所得结果,ICE-LEACH(Improvement of Cluster Establishment in LEACH)表示采用改进簇建立过程后所得结果,ILEACH(Improvement of LEACH)表示簇首选举及簇的建立两方面均改进后所得结果。仿真区域大小为100×100 m2,数据包长度选取1000 Byte,对不同算法下网络死亡节点数、数据传输量及剩余能量的对比情况如图3—图5所示。
从图3、图5可以看出,改进簇首选举算法及簇建立过程可达到延长网络生存时间,减缓网络能量消耗的目的,并且改进簇建立过程可更有效地提高网络生存周期,均衡网络能耗。分析可知,对簇建立过程进行改进后,部分成员节点根据距离判定后选择不加入任何簇,而是直接发送数据到长机,一方面降低了成员节点的数据传输距离,减少了紫外光通信时的能量衰减,另一方面簇内的成员节点数目降低,减少了簇首节点数据融合消耗的能量。图4表明不同改进下长机的数据传输量,由图可知,簇首选举及簇建立过程的改进均对数据传输量有一定的改善,并且改进簇建立过程后的改善效果更明显。分析可知,簇首选举算法的改进使簇首选择能够适应能量的变化,剩余能量高的僚机节点则优先选举成为簇首节点,从而有效延长网络生存时间,增大长机接收到的数据量。改进簇建立过程一方面降低了部分成员节点通信时的能量衰减,另一方面部分成员节点直接发送数据到长机,一定程度上提高了数据的传输成功率。
4.3 算法性能分析
本文从不同数据包长度及不同节点密度两方面对网络死亡节点数、数据传输量及剩余能量进行了对比分析。图6显示了仿真区域为100×100 m2时不同数据包长度下节点的死亡速度,由图可知,较小的坡度显示较慢的节点死亡速度,随着数据包长度的增大,节点的死亡速度也随之增大,并且数据包长度越大,该趋势越明显。图7表明仿真区域为100×100 m2时不同数据包长度下所有节点的总剩余能量,由图可知数据包长度的增大使得剩余能量快速衰减,并且数据包长度越大衰减速度越快。分析可知,数据包长度的增大会使得节点在数据传输和簇首节点进行数据融合时消耗更多的能量,从而导致节点能量加速耗尽后死亡。
图8显示了在数据包长度为1000 Byte时不同节点密度下节点的死亡速度,仿真区域分别为100×100, 300×300, 500×500及700×700,单位为m2。由图8可知,节点密度越小,节点的死亡速度越快,并且出现第1个死亡节点及全部节点死亡的轮数越早。图9表示不同节点密度下的数据传输量,由图9可知,节点密度越大,长机节点接收到的数据包总量越大。图10为数据包长度为1000 Byte时不同节点密度下所有节点的总剩余能量,由图10可知在区域为100×100 m2时,节点在轮数为1950时能量全部耗尽,而区域为700×700 m2时在轮数为1850时能量已全部耗尽,表明节点密度的减小使得剩余能量耗尽轮数越早。分析可知,节点密度越小则分布越分散,节点间的通信距离越大,在进行紫外光通信时会产生更大的能量衰减,为了获得可接受的信噪比,节点需要提高发射功率来补偿信道中的能量衰减,从而加快节点的能量消耗速度。
5. 总结
在复杂战场环境下,利用无人机蜂群对敌方进行渗透侦察既可以大幅降低作战成本,又可以减少大型作战平台及战斗人员的伤亡,因此延长无人机蜂群的生存时间,获得更多的采集信息,可为作战提供可靠的情报保障。本文提出一种基于无线紫外光隐秘通信的侦察无人机蜂群分簇算法,结合无线紫外光通信的优势,通过蜂群中无人机的能量感知,以分簇的方式优化能量分配,减少各架无人机的平均能量消耗,以达到平衡能耗,节约能量的目的。
-
WU Dapeng, SHI Hang, WANG Honggang, et al. A feature-based learning system for internet of things applications[J]. IEEE Internet of Things Journal, 2019, 6(2): 1928–1937. doi: 10.1109/JIOT.2018.2884485 ZHANG Puning and MA Jie. Channel characteristic aware privacy protection mechanism in WBAN[J]. Sensors, 2018, 18(8): 2403. doi: 10.3390/s18082403 ZHANG Puning, KANG Xuyuan, WU Dapeng, et al. High-accuracy entity state prediction method based on deep belief network toward IoT search[J]. IEEE Wireless Communications Letters, 2019, 8(2): 492–495. doi: 10.1109/LWC.2018.2877639 ZHANG Puning, KANG Xuyuan, LIU Yuzhe, et al. Cooperative willingness aware collaborative caching mechanism towards cellular D2D communication[J]. IEEE Access, 2018, 6: 67046–67056. doi: 10.1109/ACCESS.2018.2873662 WU Dapeng, LIU Bingxu, YANG Qing, et al. Social-aware cooperative caching mechanism in mobile social networks[J]. Journal of Network and Computer Applications, 2020, 149: 102457. doi: 10.1016/j.jnca.2019.102457 高云全, 李小勇, 方滨兴. 物联网搜索技术综述[J]. 通信学报, 2015, 36(12): 57–76. doi: 10.11959/j.issn.1000-436x.2015315GAO Yunquan, LI Xiaoyong, and FANG Binxing. Survey on the search of internet of things[J]. Journal on Communications, 2015, 36(12): 57–76. doi: 10.11959/j.issn.1000-436x.2015315 张普宁, 刘元安, 吴帆, 等. 物联网中适用于内容搜索的实体状态匹配预测方法[J]. 电子与信息学报, 2015, 37(12): 2815–2820. doi: 10.11999/JEIT150191ZHANG Puning, LIU Yuan’an, WU Fan, et al. An entity state matching prediction method for content-based search in the internet of things[J]. Journal of Electronics &Information Technology, 2015, 37(12): 2815–2820. doi: 10.11999/JEIT150191 邹宇驰, 刘松, 于楠, 等. 基于搜索的物联网设备识别框架[J]. 信息安全学报, 2018, 3(4): 25–40. doi: 10.19363/J.cnki.cn10-1380/tn.2018.07.03ZOU Yuchi, LIU Song, YU Nan, et al. IoT device recognition framework based on Web search[J]. Journal of Cyber Security, 2018, 3(4): 25–40. doi: 10.19363/J.cnki.cn10-1380/tn.2018.07.03 李强, 贾煜璇, 宋金珂, 等. 网络空间物联网信息搜索[J]. 信息安全学报, 2018, 3(5): 38–53.LI Qiang, JIA Yuxuan, SONG Jinke, et al. Search of internet of thing information in the cyberspace[J]. Journal of Cyber Security, 2018, 3(5): 38–53. MA Huadong and LIU Wu. A progressive search paradigm for the internet of things[J]. IEEE MultiMedia, 2018, 25(1): 76–86. doi: 10.1109/MMUL.2017.265091429 YAP K K, SRINIVASAN V, and MOTANI M. Max: Wide area human-centric search of the physical world[J]. ACM Transactions on Sensor Networks, 2008, 4(4): 26. doi: 10.1145/1387663.1387672 WANG Haodong, TAN C C, and LI Qun. Snoogle: A search engine for pervasive environments[J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(8): 1188–1202. doi: 10.1109/TPDS.2009.145 TAN C C, SHENG Bo, WANG Haodong, et al. Microsearch: A search engine for embedded devices used in pervasive computing[J]. ACM Transactions on Embedded Computing Systems, 2010, 9(4): 43. doi: 10.1145/1721695.1721709 FATHY Y, BARNAGHI P, and TAFAZOLLI R. Large-scale indexing, discovery, and ranking for the Internet of Things (IoT)[J]. ACM Computing Surveys, 2018, 51(2): 29. doi: 10.1145/3154525 刘强强, 余黎青, 赵鹏, 等. 基于移动平台的图像检索系统[J]. 计算机技术与发展, 2016, 26(11): 10–13.LIU Qiangqiang, YU Liqing, ZHAO Peng, et al. A novel image retrieval system based on mobile platform[J]. Computer Technology and Development, 2016, 26(11): 10–13. TRUONG C, RÖMER K, and CHEN Kai. Fuzzy-based sensor search in the web of things[C]. The 3rd IEEE International Conference on the Internet of Things, Wuxi, China, 2012: 127–134. doi: 10.1109/IOT.2012.6402314. 刘素艳, 刘元安, 吴帆, 等. 物联网中基于相似性计算的传感器搜索[J]. 电子与信息学报, 2018, 40(12): 3020–3027.LIU Suyan, LIU Yuanan, WU Fan, et al. Sensor search based on sensor similarity computing in the internet of things[J]. Journal of Electronics &Information Technology, 2018, 40(12): 3020–3027. LI Zhidu, JIANG Yuming, GAO Yuehong, et al. On buffer-constrained throughput of a wireless-powered communication system[J]. IEEE Journal on Selected Areas in Communications, 2019, 37(2): 283–297. doi: 10.1109/JSAC.2018.2872374 PATTAR S, BUYYA R, VENUGOPAL K R, et al. Searching for the IoT resources: Fundamentals, requirements, comprehensive review, and future directions[J]. IEEE Communications Surveys & Tutorials, 2018, 20(3): 2101–2132. doi: 10.1109/COMST.2018.2825231 ZHANG Zufan, ZENG Tian, YU Xiulan, et al. Social-aware D2D pairing for cooperative video transmission using matching theory[J]. Mobile Networks and Applications, 2018, 23(3): 639–649. doi: 10.1007/s11036-017-0973-z Intel Berkeley Research Lab. Intel berkeley research lab sensors data[EB/OL]. http://db.csail.mit.edu/labdata/labdata.html, 2004. 期刊类型引用(0)
其他类型引用(1)
-