基于复杂网络理论的无线传感器网络的连通性

耿 鹏，柳 艳

(南京工程学院，江苏 南京 211167)



基于复杂网络理论的无线传感器网络的连通性

耿 鹏，柳 艳

(南京工程学院，江苏 南京 211167)

针对当前没有将复杂网络中的特征量综合应用到无线传感器网络之中的问题，提出了基于复杂网络理论的无线传感器网络连通性分析方法。该方法利用特征量对无线传感器网络进行拓扑性质研究，分析了随机撒点下的网络由一个连通巨片与若干少量的孤立节点和孤立片组成的特点。通过仿真研究了连通率随通信半径变化的规律，以及节点密度与连通性之间的关系。指出了网络连通率会在临界区间内迅速上升直至达到基本全连通，并在给定区域条件下确定了临界区间的具体值。基于平均度对连通性与覆盖率进行了仿真分析，给出了简化无线传感器网络拓扑结构的建议。

无线传感器网络；复杂网络；连通性；覆盖率

0 引言

无线传感器网络[1](WSN, Wireless Sensor Networks)在军事、国家安全、工业控制、特殊环境监控以及气候变化预测等各个领域有着广阔的应用前景。随着物联网[2](IoT, Internet of Things)技术的不断快速发展，无线传感器网络作为其终端支撑技术，对物体智能化、网络化的推进起着关键作用。与此同时，无线传感器网络规模越来也大，逐渐呈现出与简单网络不同的统计特性[3]。这种大规模无线传感器网络的特性可以用复杂网络[4-5](CN: Complex Networks)理论加以研究。在无线传感器网络的各方面研究中，拓扑控制是其核心问题之一，它对于延长网络生命周期、减少通信干扰、提高路由和MAC协议效率等方面具有重要意义[6]。拓扑控制的目的在于建立一个利用尽量少的活跃节点实现主要网络连通及区域覆盖的拓扑结构[7-8]。

目前基于连通性与覆盖率的无线传感器网络拓扑研究正成为重要方向。文献[9]讨论了网络连通性与覆盖率之间的关系，提出了基于地理信息的节点密度控制算法(OGDC, Optimal Geographical Density Control)。文献[10]提出了一种网络平均度约束的活跃节点选择算法，该算法的计算需要花费较长时间。文献[11]提出了考虑能效性与数据准确到达性的拓扑控制算法。文献[12-14]利用图论思想讨论了网络的连通性问题，利用几个阶段来不断修剪连通支配集，以期达到简化的网络结构。上述文献均没有将复杂网络中的特征量综合应用到无线传感器网络之中。本文针对此问题，将邻接矩阵(Adjacency Matrix)、节点度(Node Degree)和路径长度(Path Length)等概念引入到无线传感器网络的分析之中，提出了基于复杂网络理论的无线传感器网络连通性分析方法。

1 WSN的复杂网络抽象

复杂网络理论被广泛应用在Internet、电力与交通网络、社会网络、生物网络和科研教育网络等方面[15]。随着无线传感器网络的大规模化与复杂化发展，复杂网络中的特征值也可以用来描述无线传感器网络。

1.1 图与邻接矩阵

(1)

显然，对任意的节点i和节点j，有aij=aji，对于网络的连接边数，只需要统计矩阵A的上三角或下三角部分值为1的数量即可，所以连接边数

(2)

1.2 节点度

节点度定义为与某节点直接相连的边的数目，节点i的度记为ki，对基于简单图的无线传感器网络而言，节点度描述的是与该节点相连的邻居节点数目。网络中所有节点度的平均值叫做网络平均度(Average Degree)，记为〈k〉，根据邻接矩阵的概念，对于具有N个节点的网络，有

(3)

(4)

2 基于复杂网络的WSN连通性

无线传感器网络之所以称之为网络，就是其中的节点是连通的，网络的连通性与节点密度、节点通信半径以及各节点之间存在的路径均相关。

2.1 路径与连通性

在集合V中，若存在一个节点序列v=v1,v2, …,vk，其中每对相邻的节点(即vi与vi+1)之间均存在连接边，则称v为v1到vk的一条路径。无线传感器网络中两个节点i与j之间的路径长度定义为此路径所包含的最少连接边数，记作dij。对具有N个节点的网络，平均路径长度(Average Path Length)描述为：

(5)

如果某区域中的每两个节点之间均存在路径，则称此区域是连通的，称为连通片(Connected Component)。无线传感器网络是由多个连通片组成的，但我们总希望大多数节点是连通的，这样便形成了连通巨片(Giant Connected Component)。如果综合考虑了节点通信半径、节点数量与探测目标区域大小之间的关系，在随机撒点的条件下，无线传感器网络往往由一个连通巨片与若干少量的孤立节点和孤立片组成，如图1所示。

图1 随机撒点下的网络结构图Fig.1 Network structure by random deploying

无线传感器网络的特点是感知信息总是由普通节点向sink节点汇集，可以形象的看作是从树叶向树根汇集。则最简单的树可以从sink节点开始，查找其邻居节点，再查找邻居的邻居(之前已找到的节点排除在外)，依次下去，就可以得到包含sink节点的树，并且可以计算每个节点与sink节点之间的路径长度。这种算法被叫做广度优先搜索算法(Breadth-first Search Algorithm)[16]。假设sink节点位于被测区域中心位置，一种利用此算法生成的无线传感器网络拓扑如图2所示。可以看出，此算法在保证节点全连通的情况下，对拓扑结构进行了较大简化。

图2 广度优先搜索算法生成树状图Fig.2 Generate tree by Breadth-first Search Algorithm

2.2 通信半径与连通性

对于给定区域、给定节点数量的无线传感器网络而言，要想提高网络连通性，最直接的办法就是提高节点通信半径，但通信半径的提高无疑意味着网络能耗的增加。无线传感器网络中的节点能量往往受限，所以讨论当通信半径增加到多少时，能够使得网络基本连通是有必要的。仿真基于Java平台，给定1 000×1 000 m2的区域，随机撒点800个节点，通信半径从10 m开始，依次递增10 m，直到节点达到全连通时结束递增。经过10次实验取平均值，可以得到图3的仿真结果。

图3 连通率随通信半径变化图Fig.3 The connectivity rate varies with the communication radius

从仿真结果可以看出，当通信半径在10 m到50 m时，网络连通率基本为0，而当通信半径继续增加时，连通率发生突变，并且随着通信半径的增加而迅速上升，在80 m处可达到95%以上的基本全连通。因此，在本实验条件下，可以把(50, 80)看作临界区间，网络连通率会在临界区间内迅速上升直至达到基本全连通。显然，临界区间的具体值与节点密度相关。如果定义无线传感器网络节点密度为节点数与所探测对象面积的比值，则可以继续分析节点密度与临界区间的关系。在上述实验基础上，将节点数从100到2 000进行增加，再次仿真得到如图4所示的节点密度与临界区上下限的关系。从仿真图中可以看出，随着节点密度的增加，达到基本全连通所需的通信半径越来越小，临界区间也变得越来越窄。当节点密度大于1.3‰时，临界区间上限与下限的差值稳定在20 m，可以将此值作为在保证连通性的情况下获得较低经济成本的参考值。

图4 节点密度与连通性Fig.4 Node density and connectivity

3 基于平均度的连通性与覆盖率仿真分析

无线传感器网络的某个节点的度描述的是与该节点相连的邻居节点数目。显然对整个网络而言，网络平均度越高，连通性越好。假设探测对象、节点通信半径和节点数量一定，那么平均度越高，则意味着网络中的节点集中度越高。在此情况下，虽然网络连通性得到了保证，但覆盖率却会由于节点的过于集中而降低。在实际应用中，往往通过适当降低连通巨片的平均度来精简网络活动节点数量，以获得更高的能量利用率和更长的生命周期。因此分析平均度与连通性及覆盖率之间的关系，可以直观地知道应该将平均度降低多少，才不会对网络连通性和覆盖率造成较大影响。本文将通过仿真分析的方法来讨论此问题，仿真参数仍然按照2.2节进行设置，假设节点通信半径与感知半径相等，经过10次实验取平均值，可以得到如表1和图5的仿真结果。可以看出，使得连通率与覆盖率均达到95%以上所对应的节点通信半径为80 m，网络平均度约为15。

表1 连通性与覆盖率数据表

图5 连通性与覆盖率仿真图Fig.5 Connectivity and coverage simulation

根据上述实验，可将连通率与覆盖率均达到95%作为前提条件(保证网络的巨片覆盖特性)，随机将节点度大于网络平均度的节点切换到睡眠状态(若检测到某节点的睡眠破坏了连通率或覆盖率，则取消睡眠)，网络运行过程中，当连通率或覆盖率降低时，再随机恢复处于睡眠状态的节点，这样便可节约网络能量，提高生命周期。

4 结论

本文提出了基于复杂网络理论的无线传感器网络连通性分析方法。该方法利用复杂网络的特征量对无线传感器网络进行拓扑性质研究，分析了随机撒点下的网络由一个连通巨片与若干少量的孤立节点和孤立片组成的特点。通过仿真研究了连通率随通信半径变化的规律，以及节点密度与连通性之间的关系，指出了网络连通率会在临界区间内迅速上升直至达到基本全连通，并在给定区域条件下确定了临界区间的具体值。基于平均度对连通性与覆盖率进行了仿真分析，给出了简化无线传感器网络拓扑结构的建议。下一步的研究重点是在保证连通率与覆盖率的前提条件下，设计具体的减少活动节点的方案，以保证网络的整体性能。

[1]Manges W. It’s Time for Sensors to Go Wireless[J]. Sensors Magazine， 1999:4-6.

[2]Internet of Things[EB/OL]. http://en.wikipedia.org/wiki/Internet of Things.

[3]罗自强, 李德毅. 无线传感器网络的概率统计分析[J]. 探测与控制学报, 2007, 29(2): 16-19.

[4]Albert R, Barabasi A L. Statistical mechanics of complex networks[J]. Review of Modern Physics, 2002,74(1):47-97.

[5]Boccaletti S, Latora V, Moreno Y, et al. Complex networks:structure and dynamics[J]. Physics Reports,2006,424(4-5):175-308.

[6]张学, 陆桑璐, 陈贵海. 无线传感器网络的拓扑控制[J]. 软件学报, 2007, 18(4): 943-954.

[7]Winghtman P, Labrador M. Atarraya: A Simulation Tool to Teach and Research Topology Control Algorithms for Wireless Sensor Networks[C]// Proceedings of the 2nd Internotional Conference on Simulation Tods and Techniques for Communications, Networks and Systerms. ICST SIMUTools, 2009.

[8]Zhu Chuan, Zheng Chunlin, Shu Lei, et al. A survey on coverage and connectivity issues in wireless sensor networks[J]. Journal of Network and Computer Applications, 2012, 35(2):619-632.

[9]ZHANG H, HOU JC. Maintaining sensing coverage and connectivity in large sensor networks[J]. Wireless Ad Hoc and Sensor Networks, 2005, 1(1): 89-123.

[10]Ji Shouling, Fan Pingzhi, Pan Yi, et al. Constructing a load-balanced virtual backbone in Wireless Sensor Networks[C]// Proceedings of International Conference on Computing Networking and Communications. Maui, Hawaii, USA, 2012:147-163.

[11]Mohamed Hefeeda, Hossein Ahmadi. Energy Efficient Protocol for Deterministic and Probabilistic Coverage in Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(5):579-593.

[12]Yu JG, Deng X, Yu DX, et al. CWSC: Connected k-coverage working sets construction algorithm in wireless sensor networks[J]. AEU-INTERNATIONAL JOURNAL OF ELECTRONICS AND COMMUNICATIONS, 2013, 67 (11): 937-946.

[13]Ammari Habib M, Sajal K Das. Centralized and Clustered k-Coverage Protocols for Wireless Sensor Networks[J]. IEEE Transactions on Computers, 2012, 61(1):118-133.

[14]Habib M Ammari. On the problem of k-coverage in mission-oriented mobile wireless sensor networks[J]. COMPUTER NETWORKS, 2012, 56(7): 1935-1950.

[15]汪小帆, 李翔, 陈关荣. 网络科学导论[M]. 北京：高等教育出版社, 2012: 1-21.

[16]Vahid Khalilpour Akram, Orhan Dagdeviren. Breadth-First Search-Based Single-Phase Algorithms for Bridge Detection in Wireless Sensor Networks[J].Sensors, 2013(13): 8786-8813.

Connectivity of Wireless Sensor Complex Networks

GENG Peng, LIU Yan

(Nanjing Institute of Technology, Nanjing 211167, China)

Aiming at the problem that the feature amount of complex networks are not applied to wireless sensor networks, a method for analyzing the connectivity of wireless sensor networks based on complex network theory was presented in this paper. The topological property of the wireless sensor networks is studied based on the feature amount. When sensors were random deployed, we considered the network was composed by giant connected component, a few isolated nodes and isolated sheet. Through simulation, the relationship between the change of the connectivity and the radius of the communication and the relationship between the density of nodes and the connectivity of the nodes were studied. The network connectivity rate rose rapidly until the critical interval was reached, and the value of the critical interval was determined by the given region. A simulation about connectivity and coverage based on the average degree was analyzed.

wireless sensor networks; complex networks; connectivity; coverage

2016-05-04

南京工程学院校级科研基金项目资助(QKJB201405)

耿鹏(1979—)，男，湖北钟祥人，讲师，研究方向：无线传感器网络，复杂网络，嵌入式系统。E-mail:huayiliu2000@126.com。

TP393

A

1008-1194(2016)05-0123-05