技术领域
本发明涉及无线传感技术领域,具体为一种基于内存分配的多跳无线传感器网络数据路径优化方法。
背景技术
信息-物理数控机床系统作为无线传感技术领域中的重要方向能够实现物理部件与感知层信息的高度集成和实时交互。多跳无线传感器网络是信息-物理数控系统的重要组成部分,负责数据采集/传输以及协助故障信息的诊断。在数据传输过程中,由于内存、带宽的限制,不合理的数据路径会降低数据传输的准确性与系统的实时性,这对高度依赖数据精度的信息-物理数控机床系统是十分不利的,其功能将受到极大限制。因此,优化数据传输路径保证数据的准确与传输过程的快速是十分必要的
无线传感器因其具备较高的灵活性可以满足信息-物理数控系统的性能扩展要求,克服传统有线传感器安装不变、布线困难的问题。随着数控系统搭载智能算法的增多,所适配的传感器数量也将增多,有线传感器因其自身缺陷极大地限制了其性能。相反,无线传感器能够轻松地解决安装条件受限的信息-物理数控机床对传感器种类、数量的要求。
多跳网络可以实现数据的远距离低损耗传输,以及多个制造单元的信息互联与集成,从而达到生产数据的集中管理和提高无线传感器网络工作效率的目的。
现有的数据路径配置方法,并未考虑各中继节点内存的使用情况和数据是否被正确分配,从而在数据传输的过程中会产生较多的丢包数据与错误数据,降低数据传输的准确性,从而影响加工过程。与此同时,内存使用率过高会增加无线网络系统负担,导致数据传输延迟增高,系统的实时性也会受到影响。
发明内容
本发明的目的是:针对现有的数据路径配置方法,并未考虑各中继节点内存的使用情况和数据是否被正确分配,从而在数据传输的过程中会产生较多的丢包数据与错误数据,降低数据传输准确性的问题,提出一种基于内存分配的多跳无线传感器网络数据路径优化方法。
本发明为了解决上述技术问题采取的技术方案是:基于内存分配的多跳无线传感器网络数据路径优化方法,包括以下步骤:
步骤一:构建多跳无线传感器网络,所述多跳无线传感器网络包括共享内存、逻辑存储器和处理器;
步骤二:将多跳无线传感器网络中各元件所属关系用模糊图进行表示;
步骤三:建立用于描述多跳无线传感器网络数据流动的五元组,所述五元组包括处理器标识、带宽需求、内存需求以及数据流动起始与结束时间元素;
步骤四:基于全时间谱理论并结合模糊图及五元组建立满足多跳无线传感器网络数据流动的带宽边界条件、内存边界条件和数据重叠条件,然后根据建立好的带宽边界条件、内存边界条件和数据重叠条件构建MILP问题;
步骤五:通过MATLAB求解MILP问题获得基于内存分配的多跳无线传感器网络数据路径最优解,即优化后的多跳无线传感器网络数据路径。
进一步的,所述满足多跳无线传感器网络数据流动的带宽边界条件为:
若多跳网络中不存在中继站节点,则带宽边界条件为
其中T
若多跳网络存在中继站对数据进行二次传输,则带宽边界条件应为
其中d
进一步的,所述满足多跳无线传感器网络数据流动的内存边界条件通过逻辑缓存区向共享内存映射条件进行,所述逻辑缓存区向共享内存映射条件包括:
若多跳网络不存在中继站节点,则表示为
其中,二进制变量A
若多跳网络存在中继站对数据进行二次传输,则表示为
其中,MID
进一步的,所述满足多跳无线传感器网络数据流动的内存边界条件为:
其中,size(b
进一步的,所述满足多跳无线传感器网络数据流动的数据重叠条件表示为:
其中M
进一步的,所述步骤五的具体过程为:
建立带宽边界条件权因子c
进一步的,所述模糊图表示为:G=(V,E)
其中,V=LB∪P∪M,M为共享内存、LB为逻辑存储器、P为处理器,集合E表示模糊图中逻辑缓存与处理器元素间、共享内存与处理器元素间的带宽需求。
进一步的,所述五元组表示为:
f
f
ft(p,lb)=(p,v’
ft(p,m)=(p,v’
其中,p
本发明的有益效果是:
1.采用本发明方法,充分考虑了内存、带宽使用率和数据重叠对多跳无线传感器网络的影响,建立基于内存分配的数据传输边界条件,可以有效地保证数据传输的准确性,比现有的路径规划方法数据传输准确性有明显提高。
2.采用本发明方法,在保证数据能够准确传输的条件下,对MILP非劣解进行加权优化,合理的平衡多跳无线传感器网络数据传输节点的内存、带宽使用率对数据传输效率的影响,达到降低数据传输延迟的目的,比现有方法数据传输平均延迟低60%左右。
附图说明
图1为本申请验证实施例图;
图2为本申请与传统路径和非劣路径问题数据的实验结果对比图;
图3为本申请与传统路径和非劣路径平均延迟的实验结果对比图。
具体实施方式
具体实施方式一:参照图具体说明本实施方式,本实施方式所述的基于内存分配的多跳无线传感器网络数据路径优化方法,包括以下步骤:
步骤一:构建多跳无线传感器网络,所述多跳无线传感器网络包括共享内存、逻辑存储器和处理器;
步骤二:将多跳无线传感器网络中各元件所属关系用模糊图进行表示;
步骤三:建立用于描述多跳无线传感器网络数据流动的五元组,所述五元组包括处理器标识、带宽需求、内存需求以及数据流动起始与结束时间元素;
步骤四:基于全时间谱理论并结合模糊图及五元组建立满足多跳无线传感器网络数据流动的带宽边界条件、内存边界条件和数据重叠条件,然后根据建立好的带宽边界条件、内存边界条件和数据重叠条件构建MILP问题;
步骤五:通过MATLAB求解MILP问题获得基于内存分配的多跳无线传感器网络数据路径最优解,即优化后的多跳无线传感器网络数据路径。
步骤1:将无线传感器多跳网络简化为由共享内存M、逻辑存储器LB和处理器元件P组成的的基本硬件结构,并由模糊图G=(V,E)表示;集合M、LB和P中的元素分别表示模糊图中的共享内存元素、逻辑缓存元素与处理器元素,其中,V=LB∪P∪M;
集合E表示模糊图中逻辑缓存与处理器元素间、共享内存与处理器元素间的带宽需求。其中,相邻节点之间的带宽以千字节每秒(KBps)表示;
步骤2:建立五元组fi=(pi,lbi,di,(t1)i,(t2)i)表示在一定带宽需求下,传感器的处理单元到逻辑缓冲区的读写访问。其中,pi表示对应传感器的处理单元,lbi表示访问的逻辑缓存区,di表示带宽需求,t1和t2表示读写访问的起始与结束时间;逻辑缓存区的大小用size(lbi)表示,其中,lbi∈LB;同理fi=(pi,mi,di,(t1)i,(t2)i)表示在一定带宽需求下,处理单元到共享内存的读写访问;
ft(p,lb)=(p,v’0)∪(v’0,v’1),...,(v’k,lb)表示由传感器处理单元p到逻辑缓存区所经历的数据流路径;同理,ft(p,m)=(p,v’0)∪(v’0,v’1),...,(v’k,m)表示由处理单元p到共享内存所经历的数据流路径;建立集合π,表示模糊图G中的所有路径,即ft∈π。二进制变量Pf,π={0,1}表示数据流fi与路径ft的对应关系;
步骤3:建立时间算子
任意时刻中数据流的边界条件包括:
带宽边界条件,为了保证数据流是有效的,在任意时间点,传输数据的总量不得超过带宽上限bw(e),基于此可能出现两种情况:
若多跳网络中不存在中继站节点,此时带宽边界条件为,
若多跳网络存在中继站对数据进行二次传输,则边界条件应为
逻辑缓存区与共享内存映射条件,为了保证每一个逻辑缓存区的内容都能分配到相应的共享内存当中,若多跳网络不存在中继站节点,则
内存边界条件,逻辑缓存区内的数据总量不应超过共享内存容量,即
数据重叠边界条件,为了保证数据的准确性,在内存分配中不允许两个逻辑缓冲区的数据在共享内存中出现重叠,即Db1+size(b1)≤Db2,其中Db1,Db2为两个逻辑缓冲区所传递数据的首地址。与此同时,为了保证逻辑缓存区的数据可以有效地传递至共享内存中,逻辑缓存区数据的首地址应被分配在共享内存有效首地址之后,即:
步骤4:根据边界条件建立MILP问题,并将其导入MATLAB求出非劣解;
建立带宽边界条件权因子c1、内存边界权因子c2,对非劣解进行加权优化,求解W=c1bw(ei)·c2(∑bi)的最小值为多跳无线传感器网络数据路径的最优解,其中c1,c2∈[0,1],c1+c2=1。
实施例:
参考附图1,以两台信息-物理数控机床组成的信息-物理系统为例,经简化后将其表示为:3个4MB的逻辑内存分别连接于对应的三个传感器处理器单元,传感器1和传感器2为机床1的感知元件,传感器3为机床2的感知元件,两台信息-物理机床的传感数据均可由基站1、基站2、基站3发送至512M的共享内存当中;附图内包含的对比路径为传统路径与非劣路径。
在t=0时刻,无线传感器1产生数据流于t=4时刻结束,无线传感器3产生数据流于t=6时刻结束,因此两条数据流可以表示为f1=(p1,lb1,260,0,4),f3=(p3,lb3,450,0,6);无线传感器2的数据流产生于t=2时刻并于t=4时刻结束,其数据流可以表示为f2=(p2,lb2,280,2,8)。在t=5时刻处理器P1和P2向共享内存写入数据产生的数据流为f4=(p1,m,260,5,8),f5=(p2,m,280,5,8);在在t=7时刻处理器P3向共享内存写入数据产生的数据流为f6=(p3,m,450,7,8);
实例中数据传输路径包含7条有效路径:
第一路径:ft1(p1,m)=(p1,v0)∪(v’0,s1)∪(s1,v1)∪(v1,s2)∪(s2,v3)∪(v3,m);
第二条路径:ft2(p2,m)=(p2,v’0)∪(v’0,s1)∪(s1,v1)∪(v1,s2)∪(s2,v3)∪(v3,m);
第三条路径:ft3(p3,m)=(p3,v”0)∪(v”0,s3)∪(s3,v4)∪(v4,m);
第四条路径:ft4(p3,m)=(p3,v”’0)∪(v”’0,s1)∪(s1,v1)∪(v1,s2)∪(s2,v3)∪(v3,m);
第五条路径:ft5(p1,lb1)=(p1,lb1);
第六条路径:ft6(p1,lb2))=(p2,lb2);
第七条路径:ft7(p1,lb3)=(p3,lb3);
以上七条路径可以满足Pfi,π=1,即存在三条有效路径使得传感器处理器可以访问相应的逻辑缓存区,以及四条有效路径可以使得逻辑缓存区的数据传递至共享内存;
时间算子T1,T2,
考虑到信息-物理数控机床1的数据传输路径较远,必包含中继站对数据进行二次传输,则带宽边界条件应为:
由于信息-物理数控机床1包含中继站对数据进行二次传输,逻辑缓存区与共享内存映射条件为:
在任意时刻,数据路径所传递的数据信息总量应小于共享内存总量,故内存边界条件为:
各个机床的传感数据应在共享内存中有序分配,在分配中不允许两个缓冲区之间的数据重叠,故Db1+size(b1)≤Db2;逻辑缓存区数据的首地址应被分配在共享内存有效首地址之后,即
根据边界条件建立MILP问题,通过将问题导入MATLAB求解得出两条路径,路径1:机床1的传感器数据经基站1与基站2传递至共享内存,机床2的传感器数据仅经历基站3传递至共享内存;路径2:机床1和机床2的传感器数据都经由基站1发送至基站2后,传递至共享内存;
置边界条件权因子c1=0.55、内存边界权因子c2=0.45,带入W=c1bw(ei)·c2(∑bi)得出W1,W2;多跳无线传感器网络数据路径最优解为min{W1,W2},求解后得出多跳网络数据路径的最优解为路径1,而路径2为非劣解;
图2为本发明方法与传统路径和非劣路径问题数据的实验结果对比图。其中,传统路径不包含基站2,与此同时,传统路径由于基站1距路由器较远,需要依靠基站3作为中继站传递数据。图中纵坐标为各个路径的数据总量、丢包数据数量与错误数据数量,横坐标为数据量。在120分钟内数据传输总量为166320B,可以看出采用本发明方法并未出现错误数据,丢包数据仅为14B,出现丢包数据是因为在数据传输过程中存在白噪音会影响数据传输的效果。采用非劣路径,由于未考虑到带宽与内存之间的权重,导致在某个时间节点数据量过大,使系统负荷增大,从而丢包数据数量与错误数据数量相比于本发明方法多。传统路径由于缺少边界条件的限制,在数据传输过程中,出现了数据溢出的情况导致所传输数据中存在大量的丢包数据与错误数据。可以看出,本发明提出的方法性能始终优于其他方法。
图3为本发明方法与传统路径和非劣路径平均延迟的实验结果对比图。横坐标为时间,纵坐标为平均延迟。可以看出,在数据传输的过程中本发明方法考虑到了各个中继站的内存、带宽使用率,使得平均延迟为25ms,相比于非劣路径平均延迟75ms与传统路径平均延时106ms,其降低延时效果明显。与此同时,随着数据负荷增加,本发明方法的延迟抖动次数也较其它路径较少,数据传递更加平稳。采用本发明提出的方法,比现有方法数据传输平均延迟低60%左右。
需要注意的是,具体实施方式仅仅是对本发明技术方案的解释和说明,不能以此限定权利保护范围。凡根据本发明权利要求书和说明书所做的仅仅是局部改变的,仍应落入本发明的保护范围内。
机译: 基于机会调度方案的多跳传输系统,并WPT提高无线传感器网络中物理层安全性
机译: 基于机会调度方案的多跳传输系统,并WPT提高无线传感器网络中物理层安全性
机译: 多处理器系统和内存分配优化方法