考虑节点间距的无线传感网络节点分配算法*

王海峰张 利

(1.南通职业大学电子信息工程学院，江苏 南通 226007；2.西华大学经济学院，四川 成都 610039)

无线传感网络在实际运行过程的依据是合理的节点分配[1-2]，网关节点通常情况下会决定节点在无线传感网络中的位置。合理分配无线传感网络节点可以提高其在运行过程中的连通性和可靠性，节点分配结果同时也决定了无线传感网络的通信效率和寿命等指标，对无线传感网络节点分配具有重要意义。

李道全等[3]在提出了基于蚁群算法、拟物力和质心算法的无线传感网络节点分布优化策略。利用蚁群算法选取无线传感网络节点个数和位置后，运用拟物力算法优化选中的节点，并采用质心算法提高节点定位精度，但是该方法存在节点能耗高、吞吐量低的问题。Karimi-Bidhendi S等[4]研究了一种异构双层无线传感器网络，该异构节点部署问题被建模为一个以网络总功耗为代价函数的优化问题，解决了通信范围受限时的传感器部署问题，但是该方法存在节点能耗高、分配效率低的问题。蒋勇等[5]根据节点的成本属性、服务能力和最大服务半径构建节点布局优化模型，采用和声搜索算法对模型求解，完成节点分配，但是该方法没有考虑节点在无线传感网络中的间隔，存在分配效果差和分配效率低的问题。

为了解决上述问题，在考虑节点间距的基础上，以吞吐量为前提，优化无线传感网络通信链路，实现节点分配。本文的主要研究思路为:首先确定无线传感网络通信节点分配多个方面的约束条件，在此基础上利用网格路由方法实现节点分配，最后通过仿真测试验证此次方法的有效性。

1 节点分配约束条件

无线传感器网络中，节点数量往往成百上千，并且大多数节点都是随机分布的，而应用环境经常是管理人员难以进入的区域，因此很难预先布置好每个节点的位置，这无疑加大了节点定位的难度。同时，为了尽可能地降低节点间的通信开销，延长整个网络的生命周期，本文在考虑节点间距的基础上，从数据转送路径、节点通信容量、节点布局三个方面设定约束条件。

1.1 数据转送路径约束

不同类型节点在通信网络中的通信能力是数据转送路径中的主要约束条件[6-7]，即节点在无线传感网络中的有效通信半径。在无线传感网络节点分配过程中，应该保证任意一个节点经过中继节点可以到达网关节点，在传播过程中不存在逆向传播方向，即从无线传感网络节点到网关节点的传送路径只存在唯一的方向，设Re＿dir＿1、Re＿dir＿2、Re＿dir＿3表示不可逆判断因子，其计算公式如下:

式中:＜SNi，RNj＞表示无线传感网络节点SNi与网络中相邻中继节点RNj的坐标向量；＜SNi，GN＞表示无线传感网络节点SNi至网关节点GN的坐标向量，该向量属于基准向量，可以判断数据转送路径的不可逆；＜RNi，RNj＞表示两个任意相邻中继节点RNi、RNj之间在数据转送路径中的坐标向量；＜RNi，GN＞表示最后一个中继节点RNi至网关节点GN在数据转送路径上的坐标向量。

通过式(1)计算得到的不可逆因子Re＿dir＿1、Re＿dir＿2、Re＿dir＿3判断数据转送路径是否符合不可逆判断条件，通过判断结果可以保证无线传感网络节点分配完成后，中继节点与网关节点之间存在最短路径和最少无线传感网络节点。

1.2 节点通信容量约束

如果节点在无线传感网络中存在过重的任务，即无线传感网络节点在无线传感网络中的数据传输率较高，会对无线传感网络的整体可靠性产生影响[8-9]。因此需要约束无线传感网络节点在无线传感网络中的数据传送率βi:

式中:αj表示起始无线传感网络节点在数据传输路径中对应的数据发信率。

确定无线传感网络节点的分配位置时，需要考虑中继节点与无线传感网络节点之间存在的通信距离，同时需要考虑不同通信距离范围中存在的中继节点，以此为基础，获得无线传感网络的候选通信路径[10-11]。

设X1和X2表示无线传感网络节点SN1的两条路径，X3和X4表示无线传感网络节点SN2的两条路径，“1”表示选中某条数据传输路径，“0”表示数据传输路径没有被选中。无线传感网络完成布设后，节点在无线传感网络中运行时必然会选择一条路径传输数据，因此存在式(3):

根据上述传输路径中中继节点RN自身的通信容量，设置约束条件如式(4):

式中:β1、β2、β3表示中继节点RN1、RN2、RN3对应的数据传送率；αi表示无线传感网络节点传输数据的发信率；γi表示中继节点RN1、RN2、RN3对应的数据转送率最大值。

1.3 无线传感网络节点布局约束

传感器发送节点在无线传感网络中与传感器接收节点之间存在的功率关系为式(5):

式中:PR、PT分别表示节点在无线传感网络中的接收功率和发送功率；GT、GR分别表示接收天线和发射天线在无线传感网络中对应的增益；λ表示无线信号媒介对应的波长；d表示收发节点在无线传感网络中的间距；L表示损耗因子，通常情况下不受无线传播的影响。

设P0表示无线传感网络节点可以接收并正确解码信号的最小功率，当节点功率PR＝P0时，在无线传感网络中的最小发送功率PTm为式(6):

分析式(6)可知，无线传感网络节点的传输距离与发送功率之间成正比关系。

设dis＿fac表示通信网络距离因子，其表达式如式(7):

2 无线传感网络节点分配算法

考虑节点间距的无线传感网络节点分配算法利用网格路由方法实现无线传感网络节点分配。

利用网格路由方式划分无线传感网络监测区域，获得二维网格。网格路由可以提高无线传感网络数据传输的可靠性，避免因节点失效和包丢失产生的故障问题，因此所提算法在网格的交叉点上分配无线传感网络节点。

2.1 网格间距

根据网格间距划分无线传感网络监测区域。当网格相邻节点间距过大导致无法提供通信时，网格中的相邻节点容易发生数据转发和数据包丢失。此时，无线传感网络中节点之间的通信可以通过增加无线传感网络中传感器发射功率实现通信，但这一过程会增加节点的能量消耗；当网格相邻节点间距过小时，会增加无线传感网络节点到sink节点的数据转发跳数，并且所选节点的数量也随之增加，存在能耗较高的问题。通过上述分析可知，分配无线传感网络节点时需要设定合理的网格间距[12-13]。

考虑节点间距的无线传感网络节点分配算法通过链路质量指示和接收信号强度指示器设置网格间距。

无线传感网络接收机和发射机之间的距离可以通过测量射频信号的能量计算，接收功率与发射功率之间的关系如式(8):

式中:n表示无线传感网络的传播因子；PT、PR分别表示无线信号在无线传感网络中的发射功率和接收功率；d表示接收机和发射机之间在无线传感网络中的距离。

为了实现数据在无线传感网络中的传输，需要保障无线传感网络节点与中继节点之间的通信，因此网格间距通常情况下需要符合下式:

式中:L、R均表示网格距离参数。

2.2 无线传感网络节点数据转发跳数

设si和s0表示网格中的节点，其对应的坐标为

如果点si在垂直方向或水平方向转发数据，需要布置较多的无线传感网络节点，此时能耗较高，用描述点si和s0转发数据时对应的最大跳数；当点si在sis0方向转发数据时，需要较少的传感器数量，此时能耗较低，用描述点s和s转发数据时对应的最大i0跳数。

根据上述分析，利用式(10)设置无线传感网络节点到sink节点的最大数据转发跳数hop＿cpunt＿max(si，s0):

式中:d(si，s0)表示点si和s0之间存在的距离。

2.3 吞吐量

在分配无线传感网络节点时，必须考虑节点在数据传输期间的吞吐量。选择通信节点路径过程中应基于以下标准:

根据上述分析，采用贪婪算法实现无线传感网络节点的分配，具体过程如图1所示。

图1 无线传感网络节点分配流程图

图1所示的无线传感网络节点分配过程为:

步骤1:初始化节点k＝0，并输入节点位置、通信半径和网格间距等基础信息；

步骤2:计算传感器节点与sink节点之间的距离，并按照距离降序进行排列；

步骤3:以排列后的节点顺序为基础，构建传感器节点集合；

步骤4:使得k＝k＋1，并判断传感器节点和sink节点距离是否小于通信距离，如果是，结束节点分配，如果不是，执行步骤5；

步骤5:在通信范围内搜索中继节点，并选择下一跳节点；

步骤6:根据最近贪婪准则选择下一跳，直至达到sink节点；

步骤7:判断选择的k是否等于最大节点数量n，如果是，完成节点分配，如果不是，返回步骤3，重复步骤4～7，直至完成节点分配。

3 仿真测试与结果

为了验证考虑节点间距的无线传感网络节点分配算法的整体有效性，需要对所提算法进行测试。

在半径为40 m的圆形范围内任意安置200个传感器节点，簇节点处于圆形范围的中心位置。仿真运行过程中，传感器节点每隔4 s收集相应的数据，并将检查数据信息传递给其他节点。通过对比所提算法分配前后的节点能耗、吞吐量以及分配效果，以及所提算法与文献[3]算法和文献[4]算法的分配效率，验证所提算法的优越性。仿真场景设置参数如表1所示。

3.1 节点能耗

采用考虑节点间距的无线传感网络节点分配算法分配节点，对比分配前后的节点能耗，测试结果如图2所示。

根据图2中的数据可知，采用所提算法分配无线传感网络节点后，与分配前相比，节点能耗显著下降，最高能耗为2.8×10-11W，表明所提算法，在节点数据传输过程中，考虑了相邻节点间距对能耗的影响，并将吞吐量作为传输前提条件，优化了节点的能耗。

图2 分配前后无线传感网络节点能耗变化

3.2 吞吐量

当吞吐量一致时，最大跳数越高，节点传输数据的能力越好，利用无线传感网络对同一组数据进行传输，对比节点分配前后传输数据的最大跳数，测试结果如图3所示。

图3 分配前后最大跳数测试结果

分析图3可知，采用考虑节点间距的无线传感网络节点分配算法对节点分配后，在无线传感网络中传输吞吐量一致的相同数据时，所用的最大跳数明显减少，分配后最大跳数为2，相较于分配前降低了较高的跳数，由此可知，所提算法可用较少的节点传输相同的数据，表明用所提算法对节点进行分配后，节点的吞吐量得以提高。

3.3 分配效果测试

采用考虑节点间距的无线传感网络节点分配算法对节点进行分配，测试所提算法的分配效果。

图4中的黑色方块，表明节点存在重复，分析图4(a)可知，原始无线传感网络中存在大量的节点重复，采用所提算法分配无线传感网络节点后，结果如图4(b)所示，根据图4(b)可知，采用所提算法对无线传感网络节点分配后，无线传感网络中不存在重复的节点，表明所提算法的无线传感网络节点分配效果好，因为所提算法对节点分配时，考虑了节点在网格中的间距，避免了节点重复问题。

图4 无线传感网络节点分配结果

3.4 分配效率

为了进一步验证所提算法的整体有效性，将文献[3]算法和文献[4]算法与所提算法进行对比测试，测试上述算法分配无线传感网络节点所用的时间，测试结果如图5所示。

图5 不同算法的节点分配时间

分析图5可知，在多次迭代中所提算法分配节点所用的时间远低于文献[3]算法和文献[4]算法分配节点所用的时间，最高时间为0.62 min，验证了所提算法具有较高的节点分配效率。

4 结束语

无线传感网络被广泛地应用在各个领域中进行数据监测，其中的无线传感网络节点具有采集、传输、处理数据的功能，然而在特殊或复杂环境下难以补充无线传感网络节点的能量，因此研究无线传感网络节点的分配算法有利于降低节点能耗。目前无线传感网络节点分配算法存在节点能耗高、吞吐量低、布局效果差和分配效率低的问题。为此，在考虑节点间距的前提下，研究了无线传感网络节点分配算法，通过网格间距、无线传感网络节点数据转发跳数、吞吐量、节点分配四方面的约束和优化，实现了无线传感网络节点分配，仿真结果表明，该算法可有效地解决目前算法中存在的问题，为无线传感网络的运行提供了保障。