Page 248 - 《软件学报》2021年第9期

2872 Journal of Software 软件学报 Vol.32, No.9, September 2021

发送充电请求的传感器节点进行无线充电.在这个过程中,区域内的 DCV 周期性地巡游各个锚点,收集
锚点处数据,并将收集到的数据传送至基站;
• 顶层用于放置基站,位于整个网络区域的中心位置,用于处理收集到的数据且给移动小车充电,以维持
整个网络的持续运行.
2.2 网络分区方案

与静态充电桩和全网多跳通信相比,使用移动充电节点可以大大增强充电过程和可控性,利用移动数据收
集小车可以有效减少通信能耗及延迟问题.不过,当网络范围较大时,WCV 可能无法及时移动至待充电传感器
节点位置或无法完成此次充电队列,造成传感器节点死亡,网络中断.此外,多部 DCV 可能集中在相同区域而影
响了整体网络性能.为提高 DCV 的数据收集量以及 WCV 的充电效率,本文提出一种基于传感器节点邻域相似
度和节点之间距离的网络区域划分方案,即 NP-NSD.该方案将网络划分为多个区域,并在每个区域内部署一辆
DCV 和 WCV,分别负责该区域内传感器节点的数据收集和电量补充.
传感器节点邻域相似度最早由 MIT 实验室的 Jeh 和 Widom 教授提出,用 SimRank 模型表示,用于衡量拓扑
图中任意两个对象之间的相似程度 [29] .由于计算传感器节点相似度的时间复杂度较高,因此,Yu 等人基于本地
2
信息冗余提出了一种高效的 SimRank 计算方法,将时间复杂度由 O(K|E| )减少到 O(K|E||V|),其中, K 为总的迭代
次数,E 为边个数,V 为节点个数 [30] .
SimRank 模型的基本思想是:如果两个传感器节点在基于图的拓扑结构中邻域比较相似,即有较多的相似
邻居节点,则这两个传感器节点应该也比较相似.所以,两个传感器节点是否相似,是由它们的邻居节点来确定.
由于当传感器节点的传感范围较大以及网络中节点分布较为密集时,网络区域划分单单依靠节点之间邻域相
似度是远远不够的,因此,本文将传感器节点之间的距离也作为衡量节点是否属于同一分区的重要指标.
首先,传感器节点与自身的相似度定义为 1.对于存在邻域的传感器节点 i 与 j,它们的相似度定义为其所有
一跳邻居两两相似度的均值,再和阻尼系数 c 相乘.对于任意两个存在邻居节点的传感器节点 i 与 j,传感器节点
之间的相似度表示为
⎧ 1, i = j
ri ⎪ c (1)
(, ) j = ⎨
(, ), i ≠
⎪ ∑ ml , rm l j
⎩ N 1_ hop () i N 1_ hop ( ) j
这里:传感器节点 m∈N 1_hop (i),l∈N 1_hop (j).N 1_hop (i)表示传感器节点 i 在第 1 跳邻居节点的集合;r(m,l)表示节
点 m 与节点 l 的相似度;c 是一个阻尼系数,使得距离越远的传感器节点 i 与 j 对 r(i,j)的影响越小.
若存在传感器节点 i 与 j,且 N 1_hop (i)=∅或 N 1_hop (j)=∅,则 r(i,j)=0.用矩阵 R 表示网络中传感器节点的两两相
似度矩阵,则矩阵 R 是一个对角线元素为 1 的对称矩阵.
用矩阵 D 表示任意两个传感器节点之间的距离,则矩阵 D 是一个对角线为 0 的对称矩阵.将矩阵 R 和 D 中
的下三角元素值从小到大排序并从 1 开始编号,然后将编号放入对应元素值所在矩阵中的位置.矩阵 B 定义为
传感器节点 i 与 j 的分区指数,则 B 表示为
⎧ 0, i ≤ j
B = ⎨ (2)
R ij
⎩ 0.5 ( , ) 0.5 ( , ), i+ D i j > j
接着,将矩阵 B 下三角元素中值最小的两个传感器节点划分为同一区域.随后,根据层次聚类的方法,直到将
整个网络区域划分为设定的 h 部分为止.
设定 200 个可充电传感器节点均匀分布于 100m×100m 的传感区域内.每个传感器节点的传感范围 d r =10m.
采用网络分区方案 NP-NSD 的分区示例结果如图 3 所示.分区后的传感器节点用 4 种图标(三角形、菱形、圆
形和方形)加以表示,整个网络分为 4 部分.从图中可以看出:网络中所有节点均可达,且同一分区内的物理链路
较为密集,分区之间的链路较为稀疏,断开分区间传感器节点的链路连接几乎不影响节点数据包的传输.
网络区域划分完毕后,在每个区域内分别放置一辆 DCV 和 WCV,保证数据收集和节点能量补充.选择各个
区域内到其他传感器节点距离之和以及路由跳数之和最小的传感器节点作为小车出发点位置 [16] ,即车站.