英语原文共 11 页
基于最短路径算法的无线传感器网络温湿度监测
Pritam Khan，Arnab Ghosh，Gargi Konar，Niladri Chakraborty
动力工程系
贾达夫普尔大学
加尔各答，印度
pritamk249@gmail.com，arnab281290 @ yahoo.com，gargi_konar @ yahoo.co.in，chakraborty_niladri2004@yahoo.com
摘要
无线传感器网络在系统监控、驱动、自动化和过程控制等方面都占有重要地位。与有线网络相关的复杂性和成本已在很大程度上通过无线网络得到克服。ZigBee是最流行、最高效的无线传感器模块之一，其遵循明确的路由协议。环境监测和养护是任何国家的基本问题之一。在本次研究中，对某一地区的温度和湿度数据进行了监测，利用这样一个应用模型进行处理：无线传感器网络的节点对某些地方的温度和湿度进行感知，采用最短路径算法将数据从传感器传输到控制站，然后通过可用的最短路径传输这些数据。在Turbo C中开发并运行了最短路径算法的代码，并对结果进行了数学显示。使用MikroC运行相同的程序，以生成与微控制器兼容的十六进制代码。通过最短路径进行数据的无线传输是针对能量感知路由过程的。
关键词：Dijkstra算法;环境监测;路由;无线传感器网络;ZigBee
一、无线传感器网络简介
无线传感器网络由分布在各个地方的自主传感器组成，用于感知温度、湿度等环境条件，并通过网络将这些信息传递给控制站。无线传感器网络在遥感和监测领域得到了广泛的应用，这些技术最近已经走在世界前列，因为它们主要用于军事应用，环境监测和保护，目标跟踪，自动化和工业化上。
无线传感器网络是由几个节点到几百个甚至上千个节点构建的。可以将一个或多个传感器连接到节点，以积累作为无线传感器网络中标记或终端设备的数据。较小尺寸的半导体、微控制器、无线电收发器和其他较小的组件集成在一个主板上，以产生传感器节点。传感器网络的设计、实现和操作需要将信号处理、网络和协议、嵌入式系统、信息管理和分布式算法的知识结合起来。
在设计特定的传感器网络时，成本效益，可扩展性，可靠性和高容错性是需要注意的重要因素，功耗也是设计无线传感器网络的重要因素。低能量路由对延迟约束数据的影响被用于使用多跳路由来降低传输能量。适当的路由确保消除可能存在于网络中的各种干扰的影响，并且还能确定网络的大小。
这项工作的目的是通过无线传感器网络在线获取有关各地环境参数的信息。这可以扩展用于监控工厂或工业生产过程中的不同参数。通过使用无线网络可以避免由于布线拥塞、激进活动、不利的气候条件等引起的问题。无线传感器网络中的数据传输由最短路径算法引导能够实现节能传输过程。
在本文中，使用无线传感器网络监测了一些大气条件，即室内区域的温度和湿度。这些收集的数据使用Dijkstra的最短路径算法计算，通过最短路径通过网络节点传输。通过在线监测这些数据，与研究所选区域内外的大气条件作比较。这里使用的无线传感器模块是使用IEEE 802.15.4协议的ZIGBEE模块。
二、ZIGBEE和IEEE 802.15.4协议
ZigBee是一种标准，它定义了一组用于低数据速率短距离无线网络的通信协议。有三种类型的ZigBee设备--ZigBee协调器、ZigBee路由器和ZigBee终端设备。基于ZigBee的无线设备工作在868MHz、915MHz和2.4GHz频段。它需要3.3V的输入，并通过IEEE 802.15.4协议帮助进行无线联网。在这项工作中，ZigBee模块有助于在室内达到40米的射频通信，并且在室外覆盖最远90米的距离。
IEEE802.15.4协议主要关注低功耗，低复杂度和低成本。它通常设计用于短距离通信，以最大化数据传输速率。在住宅、工业和环境监测、控制和自动化的情况下，IEEE 802.15.4协议在无线传感器网络应用中得到了有效的应用。在这项工作中，用该协议以节能的方式将检测到的数据通过最短的过去传输到控制站。
无线传感器网络设备内置的ZIGBEE模块的基本功能是从目标源收集信息，通过选定的节点无线传输数据，并将数据存储在控制站进行处理。构成无线传感器网络的设备被编程为标签、路由器和网关或协调器。标签收集信息，当网关将信息存储在控制站时，路由器有助于传输数据。下一节将解释该框架的应用接口，让最终用户可视化跟踪和传感结果。
三、应用模型:温度和湿度监测
在无线传感器网络的这一应用中，使用各自的传感器检测室内区域的温度和湿度。这些数据由标记或终端设备收集，并通过路由器传输到协调器或网关。网关将信息输入控制站，控制站是此应用程序中的计算机，最终用户可以可视化感知数据。
（一）使用的硬件
对于此应用程序，所需的硬件已在下面列出：
1.温度传感器NCP 9700
NCP 9700是NTC（负温度系数）型热敏电阻，其检测温度在-40℃至1250℃的范围内。图1显示了我们应用程序的整个框图。
2.湿度传感器HIH 5030
HIH 5030传感器是一种湿度传感器，可检测大气的相对湿度，并提供2.7V的电压输出，由无线传感器网络开发板的ADC（模数转换器）检测。
3.一个标签或终端设备，E52
由传感器收集的大气数据由标签或终端设备收集以进行传输。标签可以从E51到E999获取地址。这里选择的标签有一个地址E52。
4.两个路由器，R1和R2
数据被传输到控制站，以便在这些路由器的帮助下进行监控。这里我们只使用了两个地址为R1和R2的路由器。
5.协调员或网关G.
网关G，更好地称为协调器CO，将传输的数据馈送到计算机以进行监视。
6.控制站
计算机在此工作中充当控制站，其中观察到感测值并且其显示数据到达控制站的最短路径。这里的无线传感器培训套件使用ATMEGA 324PA微控制器作为传感器板的核心，ZigBee模块用于无线传感器通信。
（二）最短路径的解决方案图
图1标识了在该传输期间遵循的最短路径。这里，标签E52最初收集来自传感器NCP9700和HIH5030的信息。在此应用中遵循的最短传输路径是E52→R1→CO，路由器R2保持空闲。协调器CO最终将该数据馈送到计算机中以进行可视化和监视。这里通过使用Dijkstra的最短路径算法来完成无线传感器对最短路径的识别。该算法在第四章第一小节中解释。
四、最简短的路径算法
在无线传感器网络中存在的节点中，采用最短路径算法，使数据从节点传输到节点所消耗的能量达到最佳，从而形成能量感知路由技术。由于路由器、标记和协调器的位置在网络中是固定的，因此数据将始终在可用的最短路径中流动，从一个节点跳转到另一个节点。源节点和目标节点是固定的，跳跃的方向是从源到目标的。
在这里，由于节点的静态位置，将发生主动路由。在这种路由中，会定期监视对等连接，以确保活动节点之间的任何路径随时可用。
主动路由方案使用开放最短路径优先(OSPF)协议工作。链路状态路由协议是一种OSPF。在链路状态协议中，节点运行的最短路径算法称为Dijkstra的最短路径算法。
还有其他算法，例如Warshall的算法，Bellman-Ford算法，它也描述了最短路径算法。但这些算法仅适用于有向图。Dijkstra的算法的优点是可以为无向图获得最短路径，从而避免负权重的问题。
（一）Dijkstra的最短路径算法
采用dijkstra算法解决了具有单一来源的加权图的最短路径问题。源顶点(节点)和目标顶点存在，这些顶点由用户分配为输入。其他节点也存在，并在这些节点的帮助下对最短路径进行了排序。该过程是从vs开始，并系统地构造一个最短路径列表，以显示位于vs和vd之间的网络中的所有顶点，直到到达vd为止。
通过顶点矩阵以顶点的形式在输入时采用加权图，其中包括以下注意事项:
如果顶点vi和vj之间没有直接路径，则权重w(i，j)=0。
w(i，j)=边缘的重量，如果vi和vj是直接连接的。
从初始顶点到任何中间顶点(直到到达vd)的最短距离存储在一系列距离中，len[]。另一个数组包含最近的vd前置，即顶点、路径[]的数组。在每次迭代中，当选择具有最小值的特定节点(例如，vi)时，该顶点将包含在集合[]中，即布尔标记数组(即数组元素为0或1)。还有另一个二维数组[][]，用于形成顶点的输入图。最终，我们得到从vs到vd的最短路径后到达vd，然后回溯遍历的路径(路径[])。
这里，如图2所示，我们考虑了网络中的4个节点。节点v1是活动标签或源节点vs（我们工作中的E52），节点v4是协调器（本工作中的CO）或目标节点vd。节点v2和v3分别是网络中的路由器R1和R2。不同节点之间的距离或权重以米为单位指定。利用Dijkstra的算法，对最短路径进行排序。
算法如下：
1.键入输入图形，顶点数n，源顶点vs和目标顶点vd作为函数中的参数，例如dijkstra（a[][]，n，vs，vd）。
2.对i=1，2，..........................n重复步骤3。
将数组元素集[i]重置为0
3.重复循环i=1，2，.......................................n
检查a[vs，i]是否等于0
[如果vs和vi之间没有直接边缘]
然后：len[i]=Infinity[无穷大值为9999]，路径[i]=0[无效路径]。
否则：len[i]=a[vs，i]和path[i]=vs[vs是vi的直接前身]。
[循环结束。]
4.将值集[vs]设置为1，并将值len[vs]重置为0。
5.重复循环while（vd未包含在set[]中）。设置j=srch_min（len，set，n）{此函数将返回一个具有最小标签的顶点，使其不包含在set[]}中，并且set[j]的值为1。
6.重复循环i=1，2，.....................................，n
检查set[]中是否存在vi，然后检查vi和vj是否通过边连接。如果是，则检查len[j] a[i，j]lt;len[i][如果现有标签不是最小值则发生替换]。如果是，则len[i]=len[j] a[i，j]和path[i]=j
[循环结束。]
[第5步循环结束。]。
7.设置cost=len[vd]。
8.通过回溯打印最短的成本，然后打印最短的路径。
9.退出。
该算法使用C语言程序运行以获得数学输出。在输入数组后，获得所需的输出。
输出：
输入顶点数：4
输入加权矩阵（带权重）作为输入：
输入a[0][0]：0的值
输入a[0][1]的值：4
输入a[0][2]的值：6
输入a[0][3]的值：10
输入[1][0]的值：4
输入a[1][1]：0的值
输入a[1][2]：9的值
输入a[1][3]的值：5
输入a[2][0]的值：6
输入a[2][1]的值：10
输入a[2][2]：0的值
输入a[2][3]的值：5
输入a[3][0]的值：10
输入a[3][1]的值：5
输入a[3][2]的值：5
输入a[3][3]：0的值
输入的矩阵是：
0 4 6 10
4 0 9 5
6 9 0 5
10 5 5 0
输入起始顶点：v1
输入结束顶点：v4
v1和v4之间的最短路径：v1→v2→v4
v1和v4之间的最短长度为9
为了生成相应的十六进制代码，该算法也在MikroC软件中运行。无线传感器网络工具包的微控制器只能理解以十六进制代码生成的指令。
现在，到了时间复杂点，Dijkstra算法中最糟糕的情况是O(n2)的顺序，其中n是顶点的数量。当图形稀疏时，即在远小于O的图形中(|V|2)边缘，则可以更恰当地执行该算法，方法是以邻接列表的形式存储图形，并使用二进制、配对或斐波那契堆作为获取最小路径的优先级队列。
图形边缘的权重必须为非负，算法才能工作。此外，该算法还在无向图上工作。Dijkstra的算法是一种贪婪的算法，这虽然是最短路径算法，但不是最有效的算法。最短的路径遍历可减少能耗。本文利用无线传感器网络对温湿度参数进行能量感知路由，该网络的路由基于最短路径算法，这一点由Dijkstra算法进行了说明。
五、结果与讨论
（一）设置控制站
在Apache Tomcat7.0.10和My sql 5这两个软件的帮助下，可以在计算机中可视化收集到的数据。这两个软件有助于开发网络的本地主机。最初选择了室内区域的地图，选择该区域中存在的温度和湿度传感器。这些传感器提供输入到ADC的模拟输出电压。ADC的输出显示在无线传感网络开发板的LCD屏幕上，其十进制值范围为0-127。使用MySQl 5软件将温度传感器数据(-400℃至1250)相对于小数点值0-127进行缩放。在这里，1个十进制ADC输出对应于1.290℃温度的变化。湿度传感器也类似，它显示的湿度值在0-100之间。在这里，1个十进制ADC输出对应于0.79的湿度变化。这些传感器相对于ADC十进制输出的相关缩放情况如表一所示。
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
