一种多传感器信息融合的缓存替换策略

一种多传感器信息融合的缓存替换策略

在过去两年中，基于人类载体的通用网络已成为普通算计领域最受关注的焦点之一，因为它覆盖了不同的元素（如房屋、车辆、行人、各种传感器和相应的人类行为）。特别是在一般网络背景下，大量相关数据被节点感知、移动、通信、存储，并利用所需的地理位置、连接模式和可能的运动方向进行流动通信。对于各种不同类型的数据流传方式，节点实体面临着如何缓慢更新最具价值的数据问题，以及如何设计相应的缓存数据转换率是一个重要的研究主题。研究人员在无线网络的背景下进行了大量的研究工作，并根据数据输入成本和延迟访问目标设计了替换数据的成本计算策略。为了降低单节点间的访问有限的缺点，研究人员使用节点间的合作关系设计了一种aca缓冲器替换算法。在文献中，flood泵是一种用于计算和延迟数据访问延迟的多媒体协议策略。该策略使用更高的通信成本来减少数据延迟。为了确定大约需要的数据单位是否在相邻的节点上存储，以避免频繁访问。在文献中，我们提出了标准验证缓冲区的设计方法，并根据最小下载成本目标设计了边坡缓冲器的优化方案。对于移动社会应用的背景下，本文分析并讨论了基于共同因素的系统缓解策略，并提出了基于此的系统缓解优化方案。例如，文献使用通常接近紧密的群体具有类似于移动和数据访问模式的堆栈策略，以降低服务请求的数量和数据访问的损失率。在此基础上，建立了基于网络的移动社区协议模型。然而，在目前的软系统层面上的研究方法基于相关数据的访问信息，如访问时间最终访问时间数据元素的大小作为参考，然后设计了数据元素的替换策略。事实上，同一组数据可以具有完全不同的价值。因此，我们需要探讨如何使用合作关系机制来设计相应的数据有效性成本估算函数和缓冲盘状态化策略。基于上述分析，本文提出了节点合作协议策略：ctrp。该策略充分考虑了移动规律对数据元素的“有用性”，并将数据的访问频率作为影响缓存数据有效性的重要因素。本文组织结构如下:第二节对缓存替换策略设计所涉及的相关问题进行讨论,并说明CTRP的设计思路;第三节给出了CTRP与其他同类策略比较的性能评估与实验结果并进行相应分析;第四节总结全文并提出下一步工作的方向.1ctrp的基本原理节点缓存数据替换流程如图1所示,为方便描述,图中符号定义如下:Si:数据项i的大小;V:节点已缓存数据项集合;Phit:缓存区中数据项i的缓存命中率;基于图1流程,CTRP在选择缓存数据项替换时的目标是使得替换后的数据项集合满足如下表达式:Val(i)为CTRP用于评价数据项i“价值性”大小的函数,CTRP对数据项价值性高低是通过特定数据项与特定节点的相关度标准进行判断.该标准是基于我们之前的工作来进行设计的,其基本思想是若数据项与节点相关度越高,则说明数据项对该节点而言其价值性越高;在相关度判定的基础上CTRP通过访问频率与更新频率的比值大小来进一步对要替换的数据项集合进行筛选.下面具体说明这两部分选择数据项替换标准的设计思路.1.1频繁往来节点设置本文的节点与数据相关度通过目标地址匹配标志(DM,Destination-Matching)和节点信任度(NTD,Node-trustDegree)来进行判定.NTD和DM值越高,则该数据与节点相关度越高,说明如下:在以人为载体的普适网络中,数据缓存在节点内,主要依靠节点移动来协助传输数据,若中继节点移动过程中缓存数据项目的地与节点自身频繁往返地点记录匹配,则表明该节点经过该数据项目的地的几率较高,从而有利于协助数据较快到达目的地,降低网络延迟.本文假设在以人为载体的普适网络中每个节点可以获取当前自身的位置坐标(利用GPS等技术),每个节点可以维护一张自身频繁往返的地点位置记录的数据表.考虑到现实情况,与目的地的交互匹配机率直接分为两种情况,若该节点的频繁往返地点记录表中有数据目标坐标地址,则设置其值为1,否则为0,并用目标地址匹配因素DM进行标识.本文将每个节点频繁往返地点的数目设置为4;整个数据记录可放在一个数据包内完成,因此造成的查询性能开销非常小,通过上述设定后,CTRP按照DM标志将节点的缓存区划分为Mt与Mf两个部分,Mt部分用于存放目标地址匹配数据项集合,Mf部分用于储存目标地址不匹配数据项集合,在实现中,考虑到每个节点的频繁往返地点数目有限,因此匹配成功的数据项较少,缓存区的空间比例初始划分大致为1:4左右,并根据节点实际情况动态调整.当进行缓存数据项替换时,CTRP将先替换Mf区的数据项.在同一区内的数据项,CTRP按照数据NTD值进行队列的降序排序.对于节点信任度NTD值具体设置,CTRP采用一个权重连通图T来描述人类的社会交互网络,其中T的顶点集U由用户组成,顶点之间的边集H{h12,h23,h34,…,hnn}表示各用户之间的社会联系紧密程度.而NTD是一个实数,取值范围在[0,1]之间.CTRP用特定两个用户间的边权重来表示,边权重越大表示两个用户之间信任与交互度越高,当值为0时说明两者为陌生人.NTD参数值的设置取决于两个节点间的社会接触度.社会接触度越高,NTD值则越高.为便于设计,在具体的实现中,CTRP参照现实社会关系中的陌生人,同事,朋友,亲人等关系将接触度分为为没有﹑较少﹑平均﹑频繁﹑亲密5个级别.与其相对应的NTD值划分为{0,0.4,0.6,0.8,1}.CTRP设置每个用户只需维护自己的NTD记录表(类似于手机中的通讯簿),NTD记录的更新维护在用户间的社会关系发生变化时进行.由于人与人之间的社会关系一般较为稳定,并且每个人的社交网络由有限个用户组成,因而维护NTD记录表的开销可以接受.当节点在缓存相邻节点发送来的数据时,会相应地将发送节点的NTD值作为一个附加属性赋予给数据.若有多个节点发送了同一数据,则该数据的NTD值设置取发送节点集中的最高值.1.2节点sda的运行如前所述,以人为载体的普适网络中,数据项的有效性是缓存替换策略要考虑的关键因素.在判定节点与数据相关度基础上,本文用数据项访问与更新频率比值来衡量确定数据有效性的大小;其中数据项访问频率是一个局部数据,由缓存该数据项的单个节点独立确定,而数据项更新频率是一个全局数据,由数据生成节点或者服务器来进行统一设置.若节点所缓存数据项i的更新频率用φi表示,则有如下两种边界情况:1)limφi→∞,此时表示数据项i实时性极高,持续有效性时间极短.此时则表明该数据缓存价值很小(如股票波动实时价格),可以选择直接替换.2)limφi→0,此时表示数据项i无需更新,永久有效;在CTRP中,表明该数据项缓存价值较高;然而直接属于这两种边界情况的应用极少,绝大多数应用处于这两者区间之内.此时,节点缓存区内数据访问与更新频率比值与节点缓存命中率紧密相关.具体而言总共有如下三种情况:(1)数据项i在两次更新间隔周期内访问次数为0;由于数据项i没有访问次数,这种情况对计算缓存有效命中率没有影响;(2)数据项i在两次更新间隔周期内只有一次访问次数;由于只有一次访问次数,说明该次访问是两次更新间隔时间内的第一次访问,而在计算缓存命中率时,数据项i经过首次访问后才有可能被节点缓存,在这种情况下后续的访问次数才能看作数据项i的有效命中次数.因此这种情况对计算缓存命中率也没有影响;(3)数据项i在两次更新间隔周期内有n次的数据访问,其中n值大于等于2.这种情况下表明数据项i已被节点缓存,其至多会有n-1次有效命中次数;在这三种情况下,若令δi表示单位时间内缓存区某数据项i的访问频率,fi表示缓冲区内数据项i在连续两次更新间隔时间内访问次数,则有下式成立:进一步,若令P(fi=n)表示连续两次更新间隔时间内i的访问次数为n的概率,Uhit表示两次访问间隔时间内i的有效命中次数,则Uhit上界为:通过上式,可以看出fi(即δi/φi)成为影响缓存数据项有效命中率的关键因素,若令Sr表示节点缓存数据项需要的空间大小,则CTRP将基于上节判断节点与数据项相关性条件下替换掉V的子集VR,其中VR满足如下条件:2性能与模拟结果的分析2.1实验环境设置我们对CTRP、OPT、LRU(leastrecentlyused)、ON-CRP进行了仿真结果分析比较.考虑到目前应用普及率,本文采用蓝牙作为无线MAC通讯协议,仿真实验平台为UCBT,UCBT是一个开源的蓝牙模拟器,在NS2上经过编译安装后可以仿真蓝牙的关键协议层,包括BaseBand、L2CAP、LMP和BNEP.实验环境:本文在300m×300m的矩形区域内随机放置200个移动节点,区域两端放置两个固定的基站Sevr0与Sevr1.实验数据规模为2000个数据项.每种算法查询数据项请求为[200,800]个.其中数据项分配方法为Sevr0放置id号为偶数的数据项,Sevr1内放置id号为奇数的数据项.查询数据项请求由节点生成,其间隔时间段值为0.5秒,服从泊松分布.数据项的TTL值由基站在其Timestamp字段内设置.每次仿真均进行20次,取其平均值作为结果.2.2不同存储容量的缓冲系统的缓冲系统的缓冲系统的缓冲系统的缓冲系统的性能比较本节通过缓存命中率,平均数据访问延迟对算法进行比较分析.其中平均数据访问延迟定义为从节点发出请求到收到该数据的时间间隔.实验分别基于节点缓存大小为0.5MB、1.0MB、1.5MB、2MB、2.5MB、3MB的情况对性能指标进行考察.实验结果数据均为运行20次得到的平均值.图2显示了四种算法的平均数据访问延迟,可以看出缓存容量增加各种算法的平均延迟均趋向一个较小的值,即缓存容量与数据访问延迟呈现出一个反比关系,主要原因是缓存容量增加,可存放的数据项增多,使得数据项访问时本地命中率有所上升,远程数据查询访问次数降低,因而访问延迟有效减少.其中LRU算法主要针对数据访问次数和频率这一单项指标来进行数据选择替换,因此在移动环境下性能一般.而CTRP在数据替换过程中考虑了机会网络数据传输特点,并采用特定节点与数据的相关度进行数据项替换选择,保留了有可能较快到达目的地数据.因此其平均延迟相应处于一个较小值的区间内.缓存命中率代表了缓存替换算法的关键性能,我们分别在不同缓存容量和不同数据项尺寸情况下进行了各种算法性能的比较.图3(上)为不同缓存容量条件下算法的缓存命中率性能.为了与实际情况相符合,在实验中设置缓存了的数据项在缓存空间所占比重上限为80%,在这个比例之上继续增加缓存空间的大小对于提高性能来说效果不再明显.从图可以看出在缓存空间充足的情况下,四种算法缓存命中率基本上是随缓存容量的增大而增加的,然而可以看到缓存容量空间增加到一定幅度(大于2.5M)后,所有算法缓存命中率增加幅度放缓.总体而言,CTRP结合考虑了节点信任度与频繁往返目标匹配这两个关键因素的影响,并且对已过有效期的数据项采取及时替换的措施,因而其缓存命中率处于一个较优的值范围内.图3(下)比较了不同数据项大小的情况下各种算法的缓冲命中率.为比较各个算法真实表现,我们在系统趋于稳定的状态下(即节点缓存已达到80%,开始运行替换算法时)开始收集实验数据;从图中可以看出在小尺寸的数据项情况下各种算法缓存命中率表现较为优异.CTRP缓存命中率始终要略优于其他算法,随着数据项尺寸的变大,不同算法的缓存命中率呈现出一个下降的趋势.但总体来看,由于考虑了数据项替换是从目标地址匹配和节点协作关系角度出发,因而CTRP算法下降趋势比其他算法要缓慢,如在250K尺寸的数据项中,CTRP与OPT和LRU相比其命中率仍约有15%左右的提升.3节点信任度判定目前普适计算网络研究成为当前的