无线传感器网络的数据收集时隙分配算法.doc

无线传感器网络的数据收集时隙分配算法 传感器与微系统(Transducer andMicrosystem Technologies)2019年第38卷第4期DOI:1013873/J10009787 (2019)04014603无线传感器网络的数据收集时隙分配算法*白秋产1，王亮明2(1淮阴工学院自动化学院，江苏淮安223003;2华南理工大学计算机学院，广东广州510006)摘要:对数据收集时延进行研究，先将最小收集时延问题进行形式化表述，并建立目标函数;依据节点剩余能量，并结合克鲁斯卡尔(Kruskal)算法构成最小生成树;依据最小生成树分配数据收集时隙。 实验数据表明:提出的时隙分配算法能够有效地降低收集时延，并降低了能耗。 关键词:无线传感器网络;数据收集;最小生成树;能耗;分配时隙:TP212;TN9295:A:10009787 (2019)04014603Study ondata collectiondelay in WSNs*BAI Qiu-chan1，WANG Liang-ming2(1College ofAutomation，Huaiyin Instituteof Technology，Huaian，223003China;2School ofComputer ScienceEngineering，South ChinaUniversity ofTechnology，Guangzhou510006，China)Abstract:Study ondata collectiondelayThe minimaldata collectiondelay issueis formallyrepresented，and theobjectivefunction isconstructedAording toresidual energyof node，the spanning tree isconstructed byKruskalalgorithmThe timeslots ofcollecting dataare allocatedby thespanningtreeExperimental resultsshow thattheproposed timeslot allocationalgorithm caneffectively reducedata collectiondelay andreduce energyconsumptionKeywords:wireless sensor works(WSNs);data collection;minimum spanningtree;energy consumptiontimeslot allocation0引言收集数据是无线传感器网络(wireless sensor works，WSNs)最基础的任务1，2。 针对数据收集的WSNs，常将网络内所有传感节点构建为以基站为根的树结构(tree struc-ture)3，4，也称为基于树的数据收集问题。 根据节点融合数据，该问题可分为非融合数据收集和融合数据收集。 在非融合数据收集中，基站直接接收所有节点发送的数据，并不采集任何融合措施。 数据收集树(data collectiontree，DCT)的中间节点比其后裔节点(descendants)需要更多传输时隙。 原因在于，中间节点不仅要传输自己的数据，还要给其后裔节点转发数据。 而在融合数据收集方案中，传感节点将其后裔节点的数据与自己的数据进行融合，再将这些融合数据传输至其父节点5，6。 本文以WSNs内的非融合数据收集问题为研究内容。 针对非融合数据收集问题，现存的分配算法主要关注于依据树结构，如何快速地将传感节点数据传输至基站，即以少的时隙数完成数据收集。 如Zhao W7提出基于Colouring的分配算法，已用的Colour数据等于用于数据收集的时隙数。 文献7分析多个算法，如时隙分配、信道分配以及树构建。 类似地，文献8，9研究数据收集的最低时延。 为此，本文提出有效数据收集时隙分配算法。 实验数据表明，提出的时隙分配算法能够有效地降低数据收集时延，并降低了能耗。 1约束条件及问题描述11约束条件用图G=(V，E)表述传感网络，其中，V为顶点集，E为边。 若两节点在彼此的通信范围内，则这两个节点的通信链路就存在。 假定网络内只有一个基站，并由此基站在每个抽样间隔内收集传感节点的数据。 类似于文献3，4，网络内节点以数据收集树DCT进行管理，即Tree=(V T，E T)，并以基站为根。 其中，V T=V，E TE。 在每个抽样间隔内，假定传感节点以概率p产生一个传感节点数据包，然后再以多跳方式将数据包传输至基站。 将时间划分为m个时隙，即t=TS1，TS2，TS m。 其中TS m表示最后一个时隙，在这个时隙内，基站可能从其后裔节点接收数据包。 显然，m是要求收集所有数据的总的时:20180206*基金项目:江苏省自然科学基金青年科学基金资助项目(BKxx0457)641第4期白秋产，等:无线传感器网络的数据收集时隙分配算法隙数，其反映了数据收集过程的时延。 此外，每个节点有足够大的缓存区，在转发数据前，能够缓存所接收的数据包。 12问题描述本文对要解决的问题进行形式化表述。 对于给定的树T，每个节点v要求多个发送时隙，用于传输自身的数据和转发其后裔节点数据。 为了能够成功接收数据，所分配给节点的时隙要满足两个条件:1)所分配的时隙能够完成数据的传输;2)所分配的传输时隙无碰撞。 具体而言，假定节点v所分配的时隙表示为ST(v)，ST(v)需满足的两个条件为|ST(v)|xCh(v)|ST(x)|，vV (1)ST(v)ST(k)=，vV，kCs(v) (2)式中Ch(v)为节点v的孩子节点。 式 (1)规定ST(v)内时隙个数应大于其所有孩子节点所分配的时隙数之和。 而式 (2)规定，给节点v所分配的时隙就与其二跳邻居节点所分配的时隙没有交集，即无碰撞，其中，Cs(v)表示节点v的二跳邻居节点所分配的时隙数。 本文要解决的问题就是给DCT内每个节点分配时隙，并减少数据收集时隙。 假定，在每个抽样间隔内，每个节点均有感测数据要传输，为此，需要给每个节点分配时隙。 而对于每个叶节点，只需要分配一个时隙用于传输自身数据。 所谓叶节点就是指其无孩子节点，即|ST(v)|=1，vVCh(v)= (3)依据式 (1)式 (3)，可建立目标函数min maxvV(ST(v) (4)|ST(v)|xCh(v)|ST(x)|，vV (5)ST(v)ST(k)=，vV，kCs(v) (6)|ST(v)|=1，vVCh(v)= (7)2时隙分配用ti(v)表示节点v时隙集ST(v)内第i个时隙，且ST(v)内时隙以升序排列，t i(v)ST(v)，1i|ST(v)|。 由于每个节点均有数据包会传输，需要给网络内每个节点分配时隙。 因此，以迭代方式工作，直到每个节点被分配了足够传输时延，即满足式 (1)。 在每次迭代，时隙分配以准备就序节点(ready node，N)开始。 所谓N就是指它的后裔节点已全部分配了时隙。 21两类时隙节点除了传输自己的数据外，还需转发孩子节点的数据。 这两类数据均需要分配时隙。 因此，可将时隙分为两类:1)用于节点传输自身数据的时隙，称为传输时隙。 因此，在每个间隔，只需给节点分配一个时隙。 据此，可在无碰撞条件下，尽可能早地给节点分配传输时隙。 假定在第k次迭代，节点v的传输时隙st k(v)满足st k(v)mint|t0，CtST(v)，t(UyCs(v)ST(y) (8)式 (8)可知，分配给节点v的时隙不能与其二跳邻居节点所分配的时隙重复(t(UyCs(v)ST(y)。 并且是在ST(v)内选择一个最靠前的时隙作为传输时隙。 2)转发时隙，用于转发后裔节点的数据。 由于节点需要负责转发它的所有后裔节点数据，给节点分配的转发时隙就等于其后裔节点数。 在每次迭代中，只给一个节点分配一个时隙，节点v所分配的时隙要在它的所有孩子节点分配完时隙后。 假定它的所有孩子节点在k次迭代之前已分配了时隙，那节点v应在ik次迭代分配转发时隙。 因此，给节点v分配的转发时隙为st k(v)mint|tmaxst k(x)，xCh(v)tST(v)，t(UyCs(v)ST(y) (9)式中tmaxst k(x)，xCh(v)为所分配的时隙要在其孩子节点时隙后。 先从子树开始分配时隙，先给叶节点分配，然后是此叶节点的父节点。 以图1为例，假定节点u有3三个孩子节点1，2，3)，且每孩子节点以自己构建子树，且分别表示为T(1)，T(2)，T(3)。 图1分配时隙示例22基于节点剩余能量的最小生成树本文利用节点剩余能量作为边权重，再利用克鲁斯卡尔(Kruskal)算法10构建最小生成树。 Kruskal算法是构建最小生成树的常用算法，是通过边权重产生最小连通图。 其思路简述如下:先从E中选择权重最小的边，若该边的顶点在中不同的连通分量上，则该边加入中，否则丢弃。 然后，再从E中选择权重最小的边，依次类推，直到所有顶点均连通在同一个拓扑图内。 以图2为例，描述构建最小生成树的原理。 图中标的数字表述节点剩余能量。 如节点2的剩余能量为30。 依据节点剩余能量计算边权重，每条边权重等于边的两端节点剩余能量之和。 如由节点5和节点2构成的边，其边权重为20与30的和，即50。 先从找到最大权重的边，即从它的一跳邻居节点选择剩余能量最大的节点作为父节点，然后构成一个最小生成树。 此外，基站的剩余能量无限大，因此，节点1，2，3都将741传感器与微系统第38卷图2最小生成树基站作为父节点。 实际上，其为树的根节点。 23分配时隙的流程先利用Kruskal算法构成生成树，然后给树中的每个节点分配时隙，分配过程的伪代码如下1)Input:TrOutput:ST(v)，vTr2)While Tr0do3)for eachvTr do4)slotmint|t0，tST(v)，t(UyCs(v)ST(y)5)slotmint|tmaxst k(x)，xCh(v)tST(v)，t(UyCs(v)ST(y)6)TrTrv7)ST(v)ST(v)Uslot8)End while3性能仿真31仿真参数引用NS311网络仿真器建立仿真平台。 考虑100个随机在分布于100m100m区域。 每个节点的通信半径为15m。 100个节点内只有部分节点在每轮产生数据包，即产生数据包的概率p从01变化。 同时，为了更好地分析本文所提出的时隙分配算法性能，选择TPO7作为参照，每次实验独立重复200次，并取平均值作为最终的仿真数据。 32数据分析首先分析数据收集时延，实验数据如图3所示。 其中，数据收集时延是指总共需要的时隙数。 可知，提出的时隙分配算法的数据收集时延低于其他各算法。 与TPO算法相比，提出的时隙分配算法的时延数平均降低了324%。 原因在于，时隙分配算法能够依据Kruskal算法构建最小生成树，再依据此树分配时隙，减少了所分配的时隙数。 接下来，分析节点能耗。 引用文献12的Bluetooth41标准的能量模型，并假定每个节点中的初始能量为3J。 能耗数据如图4所示。 可知，提出时隙分配算法有效地降低了总体能量，原因在于分配算法利用节点剩余能量构建最小生成树，再依据最小生成树合理分配时隙，进而降低了能耗。 与TPO算法图3数据收集时延图4总体能耗相比，提出的时隙分配算法的能耗平均降低了约54%。 4结论本文针对无线传感网络的数据收集时延问题，展开研究，并提出新的时隙分配算法，进而降低数据收集时延，同时减少节点能耗。 利用克鲁斯卡尔算法建立最小生成树，再依据最小生成树分配时隙。 实验数据表明，提出的分配算法能够合理地给节点分配时隙，并减少了节点能耗。 参考文献:1郭立泉，王计平，熊大曦平衡评估压力传感阵列的高速数据采集系统设计J传感器与微系统，xx，36 (11):75772孙毅，孙跃，曾璐，陆俊基于最优连通功率控制的WSNs跨层路由优化算法J传感器与微系统，xx，33 (11):1351393Yu B，Li J，Li YDistributed dataaggregation scheduling in wire-less sensor worksCProc ofIEEE INFO，xx:215921674Li Y，Guo L，Prasad SAn energy-efficient distributedalgorithmfor minimum-latency aggregationschedulinginwireless sensorworksCProc ofIEEE ICDCS，xx:56635Ghosh A，Durmaz Incel O，Kumar VA，et alMulti-chanelscheduling algorithmsfor fastaggregated convergecastin sensorworksCProc ofIEEE Intl Confon MobileAd HocandSensor Systems，xx:3633726Lee E，Park S，Yu F，et alOn selectionof energy-efficient dataaggregationnode inwireless sensorworksJIEICE Transac-tions onCommunications，xx，93 (11):303530477Zhao W，Tang XScheduling sensordata collection with dynamictrafficpatternsJIEEE Transactionson Paralleland DistributedSystems，xx，24 (7):7898028IncelO，Ghosh A，Krishnamachari B，et alFast data collection intree-based wirelesssensorworksJIEEE TransactiononMobile Computing，xx，11 (6):8689(下转第153页)841第4期王小芳，等:视频中非特定人的面部表情分析算法级分别为、和。 图6不同程度的惊讶视频帧经过实验分析，参照表1中EIS的区间取值可知，图6中的这三段表情的表情强度分别落在了三个不同的强度区间，且EIS的值越大表示表情表达越强烈。 实验结果证明本文提出的表情强度指数可以比较清晰的表达出人物表情的程度，从而可以进一步分析人物表达情感的强烈程度，对人物内心活动可以进行揣摩预测。 5结束语本文实现了对任意长度的视频中非特定人物表情的识别和分析。 并实验对比验证本文算法的正确性，目前视频中表情识别仍然是在6种基本表情基础上进行的，人物的表情要比基本的6种表情复杂的多，对复杂表情以及多种表情融合的情况的研究仍存在巨大的挑战，这也将是下一步进行研究的重点。 参考文献:1Valstar MF，Mehu M，Jiang B，et alMeta-analysis ofthe firstfacialexpression recognitionchallengeJIEEE TransactionsonSystems ManCyberics PartB:Cyberics APublication oftheIEEE SystemsManCyberics Society，xx，42 (4):9669792刘清泉，张亚飞，李华锋，等基于协作低秩分层稀疏和LC-KSVD的人脸表情识别J传感器与微系统，xx，36 (11):56593梅英，谭冠政，刘振焘基于视频图像的面部表情识别研究综述J湖南文理学院学报:自然科学版，xx，28 (3):19254Ekman P，Friesen WVConstants acrosscultures inthe faceandemotionJJournal ofPersonality andSocial Psychology，1971，17 (2):1245Cootes T，Edwards GJ，Taylor CJActive appearancemodelsCThe5th EuropeanConference onComputer Vision，Freiburg，Germany，1998:4844986Jin Q，Zhao J，Zhang YFacial feature extraction witha depthAAMalgorithmCInternational Conferenceon FuzzySystemsand KnowledgeDiscovery，IEEE，xx:179217967Huang FC，Huang SY，KEJ W，et alHigh-performance SIFThardwareaelerator forreal-time imagefeatureextractionJIEEE Transactionson CircuitsSystems forVideo Technology，xx，22 (3):3403518杨瑞，张云伟，苟爽，等Gabor特征与深度信念网络结合的人脸识别方法J传感器与微系统，xx，36 (5):68709Khorsheed JA，Yurtkan KAnalysis oflocal binarypatterns forfacerecognition undervarying facial expressionsCSignalProcessing andCommunication ApplicationConference，IEEE，xx:2085208810Guo Z，Zhang L，Zhang DA pletedmodeling oflocal binarypatternoperator fortexture classificationJIEEE TransactionsonImage Processing，xx，19 (6):1657166311胡敏，许艳侠，王晓华，等自适应加权完全局部二值模式的表情识别J中国图象图形学报，xx，18 (10):1279128412Banu SM，Danciu GM，BobocG，et alA novelapproach forfaceexpressions recognitionCIEEE JubileeInternationalSymposium onIntelligent Systemsand Informatics，IEEE，xx:53754113易积政，毛峡，Ishizuka Mitsuru，等基于特征点矢量与纹理形变能量参数融合的人脸表情识别J电子与信息学报，xx，35 (10):2403241014Hamester D，Barros P，Wermter SFace expressionrecognitionwith a2-channel convolutionalneural workCInternationalJoint Conferenceon NeuralNetworks，IEEE，xx:1815Zhao GY，Pietikainen MDyna