一个无线传感器网络的网络分割模型

摘要：首先指出网络分割会影响网络连通性，并进而影响网络的通信效率；接着从物理层和MAC协议入手，讨论了导致无线传感器网络网络分割问题的通信因素。为了定量地刻画网络分割，定义了网络分割比，并分析了影响网络分割比的物理及几何因素。通过试验采集的大量数据及曲线族拟合法，建立了一个无线传感器网络的网络分割模型，定量地确定了网络节点数、面积比与网络分割比的数学关系。

关键词：无线传感器网络；网络分割；拟合优度；网络分割比；曲线族拟合法；网络面积比

中图分类号： TP393.17

文献标识码：A

0引言

无线传感器网络(WSNs)是一种由大量传感器节点以自组网方式构成的无线网络，其目的是协作地感知、采集和处理网络覆盖地理区域中感知对象的信息，并对这些数据进行处理后传送给所需用户[1,2]。由于要在有限的区域内，布撒大量节点，每个节点都有着特定的网络传输半径，共享有限的无限信道。因此，如何有效地确保网络连通性，避免由“孤儿节点”所造成的网络分割便成为了传感器网络所面临的一项重要课题[3]。

造成WSNs网络分割的因素有很多，有通信因素，也有物理及几何因素[4]。在物理层方面，诸如由于能量或其他原因导致的节点“死亡”，由于发送功率等所致的节点发射半径过小等；在链路层方面，由于分组冲突致使节点长期不能发送数据，形成“孤儿节点”，由于随机接入算法[5,6]的不理想，造成节点接入信道的“马太效应”，形成某些节点长期不能争抢到信道而被“饿死”；网络覆盖区域内的节点个数、节点发送半径及节点的移动等同样会导致WSNs的网络分割，造成网络拓扑结构的变化，网络路由的变化，从而最终影响到网络的性能。

尽管造成WSNs网络分割的原因有多种，但节点数、面积比等因素对不同网络场景、不同网络应用下的网络分割比的影响是相同的。本文重点讨论节点数、面积比对无线传感器网络分割的影响，通过构建模拟WSNs的网络运行环境，采用曲线族拟合法[7]对实验数据进行分析，得出WSNs的一个网络分割模型，从而为无线传感器网络的应用布点及拓扑控制提供理论依据。

1网络分割及其产生因素

无线传感器网络节点单跳的传输距离较短，IEEE 802.15.4所规定的通信距离为10m[8]，端到端的通信往往要依靠多跳才能完成。传感器节点利用自身的无线收发设备交换信息，当相互之间不在彼此的通信范围内时，可以借助其他中间节点中继来实现多跳通信。当某一个中间节点帮助其他节点中继时，先接收前一个节点发送的分组，然后再向下一个节点转发以实现中继。

然而并不是所有时刻网络中的节点之间都可以直接或通过中继进行通信，某些时刻节点之间可能无法通信，造成网络分割。图1为一个网络分割的示意图，图中形成了5个子网，其中有两个子网只有一个节点，我们称其为“孤儿节点”。

定义1网络节点之间由于缺少连接，使网络从单一的、连通的网络形成了互不连通的若干个子网，节点之间不能相互通信，称为网络分割(network division)。

网络分割就是节点之间失去连接，网络从单一的、连通网络形成了互不连通的不同子网。而造成WSNs网络分割的原因多种多样：如物理层原因，可能是节点失去电能造成节点“死亡”，或是邻居节点之间的距离超出了通信半径，进而形成了不同的子网，使网络覆盖面积内的节点之间无法通信；链路层原因，可能会由于产生隐藏终端、暴露终端等问题，引起数据冲突致使节点失去连接，也可能由于接入协议设计的不理想，造成接入信道时产生逻辑上的“孤立”；网络层路由问题，有些路由算法不能准确地路由，造成的节点之间不能及时、准确的通信。但更普遍的网络分割的形成则是受某些几何因素、物理运动方式的影响。

在无线传感器网络中，网络分割与同时可以发送信号而不互相干扰的节点个数相关，节点发射半径的大小也会影响网络分割。因此，网络覆盖范围内可同时传送数据的节点数、移动节点的发射半径是影响WSNs网络分割的物理及几何因素。下面假设网络覆盖区域一定，通过模拟节点的运动导致网络拓扑结构变化，采样大量的数据，并借助于曲线族拟合法来得到节点个数、节点传输半径（面积比）与网络分割比三者之间的定量变化关系。

2实验环境

本文的实验平台为东北大学嵌入式技术实验室自主开发的网络模拟平台WSNet1.0，该平台分别对物理层（节点运动模型，节点大小，节点发射半径，网络场景大小），数据链路层、网络层协议进行了描述。WSNet1.0可以对网络运行环境进行灵活设置，可以设置的参数包括：网络覆盖区的大小、节点数、节点发送功率、节点发射半径、节点的运动方式、节点运动速度、MAC协议、网络层协议等。图2为WSNet1.0试验平台的界面。

通过WSNet1.0，可以实时采集所需要的网络数据，试验要求的计算参数，如连接变化率、网络分割比、空间复用率等重要参数通过数据库接口记录到数据库内，并进行分析。针对网络分割问题，按照不同节点数、不同节点发射半径，进行了数十种组合，千余个样本点数据的采集，数据库中已经存储数万条记录。

3网络分割模型

由于无线传感器网络是面向应用的网络，而节点数、节点发射半径与网络覆盖范围会因具体的应用不同而不同，因此有必要抽象出它们之间的相对量，而忽略具体应用尺度不同的影响。本文通过定义网络分割比和面积比，来统一考虑现实世界不同应用背景情况下的WSNs的物理尺度差异。

定义2网络分割存在的时间比上整个的网络运行时间，这个比值称为网络分割比(network division ratio)，满足下面公式：

其中，Td表示网络分割时间、Tr表示网络运行时间。

定义3网络覆盖面积比上单个节点发射半径覆盖的面积，这个比值称为网络面积比(network acreage ratio)，简称面积比，满足下面公式：

(2)

其中Snet表示网络覆盖面积,Snode表示节点发射半径覆盖面积。本文后续内容中，面积比即代表的是网络面积比。

利用本文第2节所提到的实验环境，设定网络覆盖面积为1B099×800，节点数分别从10取到860，面积比分别取1到30，网络运行50B000个单位时间，运行结果的网络分割数据分布如图3所示。

图3中X轴表示网络中的节点数N，Y轴表示面积比Ra，Z轴表示网络分割比Rd。可以看出，在网络覆盖面积一定的情况下，网络分割比与节点密度、节点通信半径之间存在着一定的变化关系，为了定量地确定三者之间的数学关系，下面采用曲线族拟合法对其进行拟合。

3.1节点数―网络分割比

将图3在XOZ面上投影，可以得到节点数N~网络分割比Rd面投影。根据投影得到的结果，我们能得到如下几点结论：

1) 网络分割比Rd随着节点数N的增加而降低。当网络覆盖面积一定，节点密度越大网络分割出现的机会越小；反之，节点密度越小网络分割出现的越频繁。

2) 面积比Ra会对N~Ra关系曲线造成影响。在Ra从1到30的变化过程中，网络由分割走向连通的趋势不同。当Ra较小，即取Ra∈(1, 10)时，节点数N在低端对网络分割比Rd影响明显；而当Ra较大，即取Ra∈(20, 30)时，节点数N在高端对网络分割比Rd影响明显。3) 无论面积比Ra如何变化，只要节点数足够大，网络终将趋向连通，即Rd渐近于0。

3.2面积比―网络分割比

与本文3.1节处理方法相类似，将图3在YOZ面上投影，得到面积比Ra~网络分割比Rd面投影。根据投影结果，可以得出如下几点结论：

1) 网络分割比Rd随着面积比Ra的增加而增加。即当网络覆盖面积Snet一定时，节点发射半径越小，面积比Ra越大，则网络分割出现越频繁；反之，节点发射半径越大，面积比Ra越小，网络分割出现越不频繁。

2) 节点数N会对Ra~Rd关系曲线产生影响。当节点数分别从10取到860的过程中，Ra~Rd关系曲线由陡峭上升逐渐变成平滑上升。这说明，当网络中节点数较小时，面积比（节点发射半径）对网络分割起决定作用。

3) 当节点数量N增加到一定程度时，网络分割比Rd对面积比Ra的变化关系将变得平缓。这表明，当网络密度足够大时，尽管节点发射半径较小，网络仍然会倾向于全连通。在本文的测试数据中，当N>620时，网络基本上处于全连通状态。

3.3网络分割比模型

为了得到节点数N、面积比Ra与网络分割比Rd的函数关系，首先要确定投影函数族及曲面方程形式。选择节点数―网络分割比(XOZ面)作为投影面，借助于统计分析工具SPSS12.0所提供的11种基本函数(对数曲线、S曲线、幂函数曲线、Logistic曲线等)[9]进行回归分析与曲线拟合。各曲线拟合优度如表1所示。为了节约篇幅，表1只显示了几组有代表性曲线的拟合优度值，从左至右依次为复合曲线、三次曲线、幂率曲线、S曲线、等比级数曲线、指数曲线以及Logistic曲线，节点数N≤500时的数值。

表格(有表名)

从表1可以看出三次多项式曲线拟合优度最好。然而，由于三次多项式中含有四个参数B0,B1,B2及B3，进一步拟合确定这些参数将变得非常困难，拟合精确度很难把握。为此，从拟合优度表中，选择拟合参数较少、拟合优度次优的S型曲线进行拟合，则其曲面方程形式表示如下：

Rd=eB0+B1Ra

(3)

其中，Rd代表网络分割比，参数B0、B1是节点数N的函数。

接下来要确定式(3)中的参数B0、B1的值。表2为参数B0、B1与节点数N（N≤500）的对应取值。

表格(有表名)

表2S曲线参数与节点数N的对应取值情况

オ

再次利用回归分析，拟合参数B0、B1与节点数N的关系模型。根据曲线族拟合的拟合优度值，可以得出参数B0、B1与节点数N的关系模型最接近三次曲线。经过计算，最终曲面方程确立如下：

将式(4)、(5)代入式(3)中，于是得到网络分割比的曲面方程如下：

其中Ra为网络的面积比，N是节点数，Rd为网络分割比。公式(6)最终确定了本文所提出的WSNs的网络分割模型。根据此公式所确定的曲面形状如图4所示。比较图4与图3，可以直观地看出二者形状非常相似，这也验证了本文所建立的网络分割比模型的正确性。

4结语

空间分割对无线传感器网络端到端的通信效率有着重要的影响。物理层、MAC及网络层协议均会导致网络分割，影响到网络分割比。即使是相对“公平的”信道接入算法，当网络内节点密度较大时，节点接入信道时的“马太效应”使得网络分割仍不可避免。然而无论具体的网络状况如何，物理因素(节点个数)和几何因素(发射半径、面积比)对网络分割的影响有其自身的规律。

本文通过定义网络分割比，定量地刻画了网络分割问题；通过实验采集得大量数据，并利用曲线族拟合法确定了网络分割比、节点数、面积比三者之间满足由S曲线所确定的网络分割模型Rd=eB0+B1Ra。该模型从根本上揭示了节点数、面积比对网络分割比的变化规律，对于WSNs节点的实际布撒及网络的拓扑控制具有一定的理论指导意义。