您现在的位置: 新晨范文网 >> 商务论文 >> 电子地图论文 >> 正文

电子地图无线传感器的估算

2013/04/28 阅读:

无线传感器网络地理位置路由算法研究

1地理位置路由算法

基于地理位置信息路由算法的核心思想是通过节点的地理位置信息来实现路由。在地理位置信息路由中,节点之间相互通信,通过有效的定位算法获取自身的地理位置信息。同时,每个节点在通信范围内,获取所有邻居节点的地理位置信息。数据包转发过程中,在当前节点的邻居节点内,利用每个邻居节点和目标节点的地理位置信息来选择下一跳。由于只需邻居节点的信息就可以实现数据包的传输,该路由机制具有很好的可扩展性和很强的适应网络的动态变化性。在数据传输过程中,只有部分节点参与路由的选择和数据的接收、发送,能有效减少网络能源消耗,对延长网络的生命周期有很大促进作用。同时,通过利用传感器节点的地理位置信息对算法进行优化,可实现其他无线传感器网络路由算法无法实现的功能。近年来,定位模式的研究取得了重大发展,无线传感网络中的未知节点可以通过低成本的方式获取到精确的地理位置信息。这表明,在无线传感器网络中,基于地理位置信息的路由很可能在所有路由方式中占据主体地位。

2地理位置路由算法的转发机制

无线传感器网络的地理位置路由算法中,每个节点和邻居节点进行hello包的通信,使每个节点都可以获取到所有邻居节点的地理位置信息,为选择下一跳提供信息。当前节点根据邻居节点的地理位置信息如何选择下一跳路由,是无线传感器网络基于地理位置路由算法的主要研究方向。常见的转发策略有MFR(ForwardwithinRadius)、GRS(GreedyRoutingScheme)、RPF(RandomProgress)、NFP(NearForwardProgress)以及CompassRouting等。其中,GRS即贪婪路由算法,是指在当前节点的邻居节点内,选择距离目标节点欧氏距离最近的节点作为下一跳。贪婪转发由于其原理简单、计算复杂度低,并且产生的路由路径接近理想的最优路径,成为在各种路由转发策略中最有效、最常用的算法之一。

伪三维的地理位置无线传感器网络路由算法

1问题的提出

在三维无线传感网络中,S为源节点,D为目的节点,在S的所有邻居节点内,节点C是距离节点D欧氏距离最近的节点。按照三维贪婪路由算法的转发策略,S将选择C作为数据发送的下一跳。这种基于欧氏距离的选路策略在三维空间内节点均匀分布的情况下,能够保证最终数据传输路径围绕源到目的节点连线上下浮动,从而保证得到源到目的地的最短路径。而实际应用中,传感器节点通常分布在高低不平的曲面上,我们称之为伪三维分布。取节点C到节点D的纵向剖面,如图1所示,虚线圈表示节点信号传输范围,节点C到节点D的欧氏距离CD由CA、AB和BD三部分组成,其中CA、BD为悬空,而AB穿越了地表。由于节点分布于地形表面,实际的传输路径应该如图1中虚线所示,只能沿起伏曲面进行传播而无法沿着连线CD附近波动,因此伪三维环境下,基于欧氏距离的选路参考标准并不适用。以上分析表明,虽然节点C到目标节点D的欧氏距离最短,但沿起伏地势表面的路径长度可能大于其他邻居节点到目标节点的沿起伏地势表面路径长度。为适应实际应用的需求,需提出在起伏地形环境下的新的距离计算方法,以获得更为优化的端到端最短路径长度

2起伏地势上的最短路径算法

2.1电子地图

电子地图是通过卫星遥感技术,对某一地区的地形信息以数字的形式存储在介质上,其精度能够达到厘米级。它包含的信息非常多,如道路、河流、建筑物标记、等高线等。在电子地图上,位置信息通过一串x、y、z坐标表示。假设点p是电子地图上的一个点,在x、y坐标已知的情况下,可以通过电子地图得到点p的z坐标。

2.2算法思想

针对3.1中描述的三维贪婪路由算法在起伏地势上利用欧氏距离作为节点下一跳选择的不合理现象,本文提出伪三维的地理位置无线传感器网络路由算法,该算法采用起伏地势上的近似最短路径来替换欧氏距离。算法中利用空间取点的方式,在电子地图表面选取离散点,这些离散点能整体反映电子地图表面的起伏趋势。计算相邻离散点之间的空间欧氏距离,将相邻关系映射到二维平面上,运用图论中最短路径计算方法,计算出电子地图表面的离散点之间沿起伏地势的近似最短路径。因为这条路径是在电子地图上选取的离散点中产生,所以能很好的逼近沿电子地图表面的最短路径。当传感器节点撒在电子地图描绘的区域时,节点根据自身的地理位置坐标找到与自身最近的那个离散点,根据离散点之间的最短距离来逼近在实际起伏地势上的最短路径,利用获取的最短路径进行下一跳的选择。

2.3算法步骤

起伏地势上最短路径的计算步骤如下:①建立网格,从电子地图上获取离散点。截取需要建立传感器网络区域的电子地图,根据获取的电子地图,在电子地图的垂直投影面上按照X方向和Y方向建立正方形网格。将这些网格交点沿垂直方向获取与电子地图的交点,每个交点的X坐标和Y坐标在建立网格时按照电子地图的长和宽等间隔获取。而Z坐标则由网格交点的垂线和电子地图相交时确定。如图2所示,这些与电子地图相交所得的离散点可以反映出电子地图的基本形状。

②确定电子地图上交点之间的相邻关系。电子地图上的交点投影到XY面是一些按正方形网格分布的离散点,如图3所示。在投影的平面图上,每个点只与周围的8个点为相邻点,而且规定每个点只计算与其相邻点之间的距离,例如投影点a只与投影点b、c、d、e、f、g、h、k存在相邻关系,那么在计算电子地图上的空间点''''a与其相邻点之间的距离时,只计算空间点a''''与空间点b''''、c''''、d''''、e''''、f''''、g''''、h''''、k''''之间的距离(空间欧氏距离)。

③将三维空间中的点映射到二维平面并根据各点的邻接关系建立邻接矩阵。在投影面上,每个相邻投影点之间记录对应空间相邻点之间的欧氏距离,把空间的各相邻点之间的距离问题转化为二维图上的点与点之间的距离以及邻接问题。建立邻接矩阵——矩阵的行数和列数都为空间中点的个数或者投影点个数,i和j为点的序号,矩阵元素ija表示投影点i到投影点j的距离,如果i与j相邻,则ija表示邻接距离;若不邻接,则ija为-1。以节点a为例,除了与之相邻的点b、c、d、e、f、g、h、k的邻接距离为L1、L2、L3、L4、L5、L6、L7、L8外,与其他点之间的邻接距离都为-1,如图3所示。

④利用图论方法寻找最短路径。对于已建立的邻接矩阵,运用图论中的Dijkstra最短路径算法来计算投影面上任意两点之间的最短路径,计算结果就是在电子地图上选取的对应两点之间在起伏地势上的近似最短路径。因此,通过转化到平面图中计算两点之间的最短路径,从本质上对空间中相应的两个点之间沿电子地图表面的最短路径进行了逼近。

⑤将实际传感器节点的地理位置映射到对应离散点并获取最短路径。实际的传感器节点已知自身的地理位置,可以依靠节点的X和Y坐标来定位到最相近的离散点上。知道了目标传感器节点对应的离散点和当前传感器节点对应的离散点,最短路径就可以用离散点之间的最短路径来逼近。

3传感器节点沿起伏地势下一跳的选择策略

以下将对三维贪婪路由算法的空间距离选择和本文提出的伪三维的地理位置无线传感器网络路由算法的沿起伏地势最短路径选择分别进行说明。

3.1空间距离选择下一跳

利用空间欧氏距离来选择下一跳的流程:源节点S向目标节点D转发数据时,首先获取当前节点的所有邻居节点的地理位置信息,然后判断目标节点是否在它的邻居节点内。如果目标节点在邻居节点内,直接将数据发送给目标节点;否则,根据邻居节点的地理位置信息,从邻居节点中选取离目标节点空间欧氏距离最近的那个节点作为下一跳,直到将数据分组传到目的节点。

3.2起伏地势上的最短路径选择下一跳

因为电子地图上的采样点是均匀、有规律分布的,所以当传感器节点在电子地图上均匀分布时,可以很好的定位到采样点上。但当传感器节点在起伏地势随机分部时,必须采取一定的定位策略使节点定位到最近的采样点上,以此来逼近当前节点到目标节点在起伏地势上的最短路径。本文在后面的仿真实验中采用四点最近定位的方法将节点定位到采样点上。具体方法描述如下:根据传感器节点自身的地理位置坐标,寻找到包含这个节点的由四个采样点构成的网格。分别对这四个采样点求到目标节点采样点在起伏地势上的最短路径,取路径最短的那个采样点作为这个传感器节点对应的采样点。当有多个邻居节点定位到同一采样点时,采用空间欧氏距离的方式作为下一跳的选择。

无线传感器网络路由过程中,利用沿起伏地势最短路径选择下一跳的流程如图4所示。源节点S向目标节点D转发数据时,首先获取所有邻居节点的地理位置信息,然后判断目标节点是否在它的邻居节点内。如果目标节点在邻居节点内,直接将数据发送给目标节点;否则,对当前节点和其邻居节点以及目标节点采用四点最近定位映射到采样点。寻找邻居节点采样点中距离目标节点采样点路径最短的那个采样点。当有多个邻居节点对应到该采样点时,用空间欧氏距离的方式选择下一跳,否则选取该采样点对应的邻居节点作为下一跳。重复以上步骤,直到将数据传到目标节点。

仿真实验

1仿真环境的构建

本文选用MATLAB软件进行仿真环境的构建。在1000m×1000m的范围内,以100m为间隔构建高度不同的空间离散点,用这些点来模拟电子地图的起伏趋势;然后用MATLAB将这些离散空间点拟合成面,构建出电子地图。

2实验仿真数据的对比与分析

路由过程中数据包经过的节点数即路由跳数是衡量无线传感器网络路由协议的重要指标。在路由过程中所经历的节点数越少,越能减少网络的能量消耗,延长网络的生存时间。所以,本文以路由跳数为指标,对比三维贪婪路由算法,来衡量伪三维的地理位置无线传感器网络路由算法的优劣性。本仿真实验中,对于无线传感器网络节点的布采用理想均匀分布和随机分布两种分布方式。以下分别对在这两种分布下,对三维贪婪路由算法和伪三维的基于地理位置的无线传感器网络路由算法进行分析比较。

2.1理想均匀分布传感器节点

理想均匀分布的传感器节点采用和电子地图采样点相同的x坐标和y坐标,在电子地图上获取z坐标。采用该分布方式,可以在路由过程中避免节点定位到采样点时带来的误差,从而可以直接分析和比较两种路由算法的优劣性。设定采样间隔(网格大小)为10m,从节点1到节点10200,分别对两种路由算法进行仿真。图5是两种路由算法下路由跳数的对比图。其中,红色曲线表示采用空间欧氏距离选择策略的三维贪婪路由算法的路由跳数,蓝色曲线表示采用起伏地势最短路径选择策略的伪三维的地理位置无线传感器网络路由算法的路由跳数。从图中可以看出,路由跳数随着节点传输半径的增大而减少,在传输半径相同的情况下,伪三维的地理位置无线传感器网络路由算法的路由跳数明显少于三维贪婪路由算法的路由跳数。通过仿真,在节点传输半径为30m时,将节点1到节点10200在电子地图上的路由轨迹显示出来,如图6所示。红色曲线为三维贪婪路由算法下的路径轨迹。可以看到它没有考虑地势状况。蓝色曲线为伪三维的地理位置无线传感器网络路由算法下的路径轨迹。可以明显看到,它有意识的避开了具有较大起伏的地势,选择了一条较为理想的路径。

2.2随机分布传感器节点

沿电子地图范围内的x方向和y方向,在每隔10m的正方形内随机的分布一个节点,从电子地图上获取节点的z坐标。这种分布的传感器节点既可以体现出在整个电子地图上的均匀分布,又能体现出在一定区域内的随机分布。以下是在随机分布的传感器节点位置不变的情况下,对无线传感器网络中两种路由算法的仿真。电子地图上的采样间隔越小,计算出来的最短路径越和实际相接近。因此,采样间隔是影响伪三维的地理位置无线传感器网络路由算法性能的重要因素。为更加全面的验证该算法性能的优越性,分别选取不同的采样间隔计算起伏地势最短路径,将使用该最短路径进行路由的伪三维的地理位置无线传感器网络路由算法的仿真结果与三维贪婪路由算法的仿真结果进行对比。

分别取采样间隔为10m、15m、20m,计算各采样间隔下节点3到节点8997用伪三维的地理位置无线传感器网络路由算法和三维贪婪路由算法在不同传输半径下的路由跳数。图7是在不同的采样间隔下两种路由算法在不同传输半径下路由跳数的仿真结果对比。三维贪婪路由算法使用空间欧氏距离选择下一跳,与采样间隔无关,因此,在不同采样间隔下,三维贪婪路由算法的路由跳数相同。

图7中,三维贪婪路由算法下的路由跳数用红色曲线表示。以下从两方面对该图进行解释:

⑴当节点传输半径变化时,伪三维的地理位置无线传感器网络路由算法比三维贪婪路由算法的总体效果好得多。但当节点传输半径为34m时,图中采样间隔为20m的伪三维的地理位置无线传感器网络路由算法的路由跳数略大于三维贪婪路由算法。假如计算得离目标节点近似路径最短的节点为A,近似路径次短的节点为B,而节点B的实际最短路径要比节点A的实际最短路径短,只是采样间隔20m较大,在四点最近定位时造成的误差很大,节点A定位到的那个采样点要比节点B定位的采样点到目标节点的采样点的近似最短路径短。根据算法思想,将数据包发送给节点A而不是节点B,造成路径选择偏差而导致路由跳数的增加。

⑵采样间隔变化,传输半径固定。总体效果是采样间隔为10m时好于采样间隔为15m和20m时。因为采样间隔越小,计算出的近似最短路径和实际最短路径越接近。但有部分间隔10m的跳数略大于间隔为15m时的跳数。原因是随着传输半径的增大,邻居节点增多,可选择的下一跳增多。对于同一个节点,由于采样为15m的四点最近定位范围比采样为10m的范围大,所以节点在定位到采样点时,可能会获取到比10m更为优越的近似最短路径,使采样间隔为10m的路由跳数略大于采样间隔为15m的路由跳数。通过以上仿真实验可得出结论,对建立在起伏地势上的无线传感器网络,在基于地理位置信息算法的基础上,用起伏地势上的最短路径代替空间距离,能有效减少路由跳数,从而减少能量消耗,延长网络生存时间。即本文体提出的伪三维的地理位置无线传感器网络路由算法比三维贪婪路由算法有较大优越性。

结束语

本文提出了适用于分布在起伏地势上的无线传感器网络的伪三维的地理位置无线传感器网络路由算法。该算法的核心思想是用起伏地势上的近似最短路径代替空间欧氏距离,使基于地理位置的路由选择更接近于实际的理想数据传输路径。伪三维的地理位置无线传感器网络路由算法在起伏地势上能有效减少源节点和目标节点之间的路由跳数,降低路由时延,进而减少节点的能量消耗,延长整个网络的生存时间。

作者:解荧韩阳龙赵刚 于富财胡光岷单位:电子科技大学光纤传感与通信教育部重点实验室四川石化南充炼油厂

电子地图无线传感器的估算

2013/04/28 阅读:

推荐度:

免费复制文章