基于孙子剩余定理的无线传感器网络数据可靠传输方法

摘要

本发明公开了一种基于孙子剩余定理的无线传感器网络数据可靠传输方法，在节点随机抛撒之后在单位圆盘图UDG的基础上结合Gabriel图对网络进行拓扑控制，调整节点发射功率，更新邻居节点集，形成网络数据通信拓扑。对要发送的数据包先进行线性编码，将数据编码成多份相互线性无关的数据，再对这些数据采用孙子剩余定理分割成较小的子数据包并将这些子数据包沿着多路径采用最小跳路由算法传输到sink节点，最后由sink节点完成对分割数据的合并以及对编码数据的解码。本发明的数据通信方法实现较为简单，不需要复杂的路由协议就可以有效提高网络能量的使用效率，减少网络拥塞的发生，充分发挥编码效应，保证数据可靠地传输到sink节点，可用于大规模无线传感器网络。

说明书

技术领域

本发明属于无线传感器技术领域，涉及一种无线传感器网络中的数据传输方法，具体地 说，涉及一种基于孙子剩余定理的无线传感器网络数据可靠传输方法。

背景技术

无线传感网络WSNs是以大量传感节点为基本部件的多跳无线通信网络。这些节点部署 在给定的应用区域后，节点各自感知该区域内的信息并生成数据，再通过无线多跳的方式将 数据传递给sink节点并由sink节点进行进一步的处理。

在无线传感网络的应用中，传感器节点在被随机散在一定的检测区域之后需要通过自组 织方式构成网络，并在自己的区域内完成数据采集。节点在向目的节点发送数据时通常要同 时汇报节点的位置信息。目的节点在收到数据之后可以准确的判断该事件发生的区域，并采 取进一步措施。例如在森林防火中，当传感器节点监测到火灾发生时，消防人员需要准确定 位火灾发生的位置。通常情况下，传感器节点可以利用GPS(全球定位系统)定位装置或相关 定位协议确定地理位置，并通过广播数据包与邻居节点交换位置信息。

传感器节点通常由能量有限的电池供电，对电量的使用效率队节点以及对整个传感器网 络来说至关重要。其中研究表明，节点通信阶段发送数据所消耗的能量占节点能量消耗的大 部分。根据上述特点研究者们提出了提高WSNs能量效率的方法、机制或协议。

在减少网络能量消耗、延长网络生存时间方面，基于拓扑控制的方法效果显著，得到了 广泛关注与研究。拓扑控制一般主要有两种方法：一种是基于功率控制的，另外一种则是采 用分层措施。基于功率控制的方法是在满足连通覆盖基本要求的前提下，尽可能减小节点发 射功率提高能量效率。分层的思想则是根据节点的邻接情况设法改变网络逻辑拓扑，通常的 做法将整个网络分成一个一个的簇状结构。

在功率控制的实现途径中，人们经常用到临近图。Gabriel图是一种常用的临近图。通 常情况下在构造的Gabriel图上可以找到和原图最低能耗相当的路径。在文献An Energy-saving Algorithm of WSN based on Gabriel Graph中，作者提出以每个节点最大的GG 边作为发射功率调整相应的通信半径，同时让数据的发送过程在Gabriel图上进行。这样每 个节点可供选择的下一跳仅限于和其有GG边连接的节点，而不再是最大通信范围内的所有 邻居，减少了通信计算量以及通信干扰发生的几率。

为了降低能量消耗并且考虑到算法的复杂性。在文献ANovel Reliable and Energy-Saving  Forwarding Technique for Wireless Sensor Networks中。本申请人提出在源节点将数据进行数 据压缩，将需要发送的原始数据利用孙子剩余定理进行分割，将较大的数据分成一系列较小 的数据，使得每个节点只需要发送各个小的子数据即可。Sink节点只要正确的收到这些子数 据，就能利用它们还原成原数据。这里只需要假设sink节点的计算能力以及能量大于传统的 传感器节点就可以适用于WSN并且可以保持较低的数据传输复杂性。但是文章中没有考虑 网络拓扑的构建是否会带来通信干扰，同时也没有考虑到不可靠的通信链路对数据可靠传输 的影响。

发明内容

本发明的目的在于克服上述技术存在的缺陷，提供一种基于孙子剩余定理的无线传感器 网络数据可靠传输方法，同时考虑拓扑控制以及不可靠通信链路对数据传输的影响，通过采 用网络编码增加传输冗余来提高数据传输的可靠性，有效的降低了对单个数据的依赖，减少 了不可靠通信链路所带来的影响，同时可以提高整个网络的能量使用率，降低网络的通信干 扰，满足大规模无线传感网络的传输要求。

其具体技术方案为：

一种基于孙子剩余定理的无线传感器网络数据可靠传输方法，针对无线传感其网络能耗 均衡且传输可靠的问题，采用线性网络编码以及最小跳路由算法实现数据通信，包括如下步 骤：

(1)在L×L的平面区域内，随机抛撒N个无线传感器节点，Sink节点位于监测区域 边缘，负责接受采集数据并且对数据进行相关处理；

(2)无线传感器网络WSNs中传感器节点以最大发射功率广播位置信息，并记录邻居 节点的信息，形成网络的单位圆盘图UDG；

(3)根据单位圆盘图UDG，利用Gabriel图构造算法，形成网络基于Gabriel图的拓 扑结构；

(4)根据Gabriel图的拓扑结构，形成数据通信拓扑结构；

(4a)节点i在Gabriel图下分别计算与各邻居节点的距离，找出其中的最大距离，并调整 自身的发射功率，调整其通信半径与对大距离一致，降低通信干扰；

(4b)节点i在调整半径后在新的通信半径下发送查询消息元数据信息，找出非对称链路 的邻居节点，从而得到对称链路的邻居节点集N(i).；

(4c)重复(4a)、(4b)，直到整个网络中所有节点i都得到了邻居节点集N(i)，形成网络的数 据通信拓扑；

(5)在构建的数据通信拓扑上，需要发送数据的节点将数据包完成相应处理后以最小 跳数路由算法传递到sink节点；

(5a)需要发送数据的节点i首先查找自身的邻居节点集N(i)中邻居节点的数目|N(i)|；

(5b)若邻居节点集的个数为1时，节点i对数据不做任何处理并将数据传递给唯一的邻 居节点j，节点j查找自身的邻居节点集N(j)的个数|N(j)|；

(5c)若邻居节点集的个数|N(j)|大于等于2个时候将数据包首先通过线性编码将数据编 码成多份线性无关的数据，然后再对各个数据采用孙子剩余定理进行数据分割，数据分割的 数目与节点i的邻居节点集的个数相同；

(5d)将分割后的数据以最小跳数路由算法传递到sink节点；

(5e)sink节点收到分割后的数据，首先对分割后的数据进行合并，再通过网络编码进行 数据解码恢复出原始数据，即源节点所要发送的数据；

(5f)在其他时间段内，如果网络中有其他传感器节点u需要发送其采集数据的数据包， 重复(5a)-(5e)就使sink节点收到源节点发送的数据。

进一步优选，步骤(3)中所述的根据单位圆盘图UDG，利用Gabriel图构造方法，形成网 络的Gabriel图拓扑，按如下步骤进行：

(3a)节点i根据自己和邻居节点j的位置信息，计算以i和j二者连线为直径的圆的圆心 位置以及半径；

(3b)节点i计算上述圆心到其他邻居节点的距离，并判断该距离是否小于上述半径，如 果小于则将该节点从邻居节点集中删除；

(3c)重复步骤(2a)-(2b)，直到节点i对所有邻居节点j都进行操作，从而完成该节点邻居 节点的更新；

(3d)重复步骤(2c)，知道整个无线传感器网络中的所有节点k都进行了上述的操作，这就 完成了整个网络的Gabriel拓扑构建；

进一步优选，步骤(5c)所述当节点j的邻居节点集的个数|N(j)|大于等于2个时候将数 据包首先通过线性编码将数据编码成多份线性无关的数据，然后再对各个数据采用孙子剩余 定理进行数据分割，按照如下步骤进行；

(5c1)当节点j的邻居节点集的个数|N(j)|大于等于2个时，查找其邻居节点集N(j)中 是否包含sink节点，如果sink节点属于其邻居节点集，则直接选择sink节点为下一跳节点， 并且对要数据包不做任何处理；否则，执行步骤(5c2)；

(5c2)假设源节点S需要发送假设要发送的m个数据包为B₁，B₂，L，B_m，则源节点S从有 限域F_q中随机选取编码向量将源节点的m个数据包B₁，B₂，L，B_m编码 成n个数据包E₁，E₂，L，E_n(n≥m)：

$E_i=\underset{j=1}{\overset{m}{\Sigma }}{\alpha }_{\mathrm{ij}}{B}_j;i=\mathrm{1,2},L,n$

这样通过采用线性编码，就将源节点S本来要发送的m个数据包B₁，B₂，L，B_m转换为 E₁，E₂，L，E_n，这种编码的好处在于把不同的数据糅合在一起，减少了对单个数据的依赖， 增加了数据的传输可靠性；

(5c3)在传输编码后的数据E_k的时候，在节点内部定义固有的素数p_ki，其中素数的个 数与其邻居节点的个数相同，根据孙子定理可知，对任意给定的整数集合{E_k1，E_k2，...，E_kN}， 存在唯一的整数使得E_k=E_ki(modp_ki)，因此，在传输一个数据E_k时，只需要 在其邻居节点的各条路径上传输E_ki即可。

进一步优选，步骤(5e)中sink节点收到分割后的数据，首先对分割后的数据进行合并， 再通过网络编码对数据进行解码来恢复原始数据，按照如下步骤进行：

(5e1)当sink节点收到分割后的数据E_ki后，利用孙子剩余定理将分割的数据E_ki进行合 并，得到分割前的数据E_k，E_k的计算方法为：其中的系数 $c_{\mathrm{ki}}=Q_{\mathrm{ki}}{q}_{\mathrm{ki}},M_k=\underset{i}{\overset{N}{\Pi }}{p}_{\mathrm{ki}},Q_{\mathrm{ki}}=\frac{M_k}{p_{\mathrm{ki}}},$q_ki使得c_ki=1(modp_ki)；

(5e2)在得到分割前的数据E_k后，假定节点收到的m个数据分别为E₁，E₂，...E_m，进一步 判断相应的m个系数向量α₁，α₂，...α_k是否线性无关，如果是，则将数据通过编码进行解码：

$\left(\begin{array}{c}{B}_1\\ B_2\\ M\\ B_m\end{array}\right)={\left(\begin{array}{ccc}{\alpha }_{11}& K& {\alpha }_{1m}\\ M& O& M\\ {\alpha }_{m1}& L& {\alpha }_{\mathrm{mm}}\end{array}\right)}^{-1}\left(\begin{array}{c}{E}_1\\ E_2\\ M\\ E_m\end{array}\right)$

通过上述的解码就将数据还原成原始数据B₁，B₂，...，B_m。

与现有技术相比，本发明的有益效果为：

本发明结合Gabriel图对WSNs进行拓扑控制，结合Gabriel图限定各节点的通信范围， 减小了节点数据收发的能耗，并降低了节点间的通信干扰。

本发明利用无线传输的广播特性和网络编码技术提出数据可靠的传输方案，避免了无线 链路的不可靠性对数据传输的影响。通过保证本地节点的可靠传输，充分发挥编码效应，保 证数据可靠地传输到sink节点。

本发明在采用网络编码的同时利用孙子剩余定理将原先较大的数据分割成一系列小的 子数据包，每个节点只需传输子数据包，均衡了能量消耗的同时避免了出现网络拥塞。

本发明适用于大型无线传感器网络，具有很好的可扩展性。

附图说明

图1是本发明基于孙子剩余定理的无线传感器网络数据可靠传输方法的总流程图；

图2是本发明中需要传输数据的节点S对要发送数据数据处理的过程图；

图3是本发明在给定网络中仿真所生成的单位圆盘图UDG与Gabriel图拓扑，其中，

图3(a)是本发明在给定网络中仿真所生成的单位圆盘图UDG拓扑；

图3(b)是本发明在给定网络中仿真所生成的Gabriel图拓扑；

图4是本发明采用孙子剩余定理后仿真100次所得到的最大能量降低因子(MERF)的排 序图；

图5是本发明采用孙子剩余定理数据分割前与分割后不同数据大小数量的对比图，其 中：

图5(a)是本发明未采用孙子剩余定理数据分割前数据包大小的数量；

图5(b)是本发明采用孙子剩余定理数据分割后数据包大小的数量；

图6是本发明采用线性编码与未采用线性编码的传输可靠性对比图。

具体实施方式

下面结合附图和具体实施例对本发明的技术方案作进一步详细地说明。

参照图1，本发明基于孙子剩余定理的无线传感器网络数据可靠传输方法，具体步骤如 下：

步骤1.在L×L的平面区域内，随机抛撒N个无线传感器节点，Sink节点位于监测区域 边缘，负责接受采集数据并且对数据进行相关处理。

步骤2.无线传感器网络WSNs中传感器节点以最大发射功率广播位置信息，并记录邻 居节点的信息，形成网络的单位圆盘图UDG。

(2.1)网络中各节点以最大发射功率广播自身的位置信息；

(2.2)节点i收到邻居节点j的位置信息后，记录该位置信息并将j加入邻接表，形成节 点i的初始邻接表；

(2.3)重复(2.1)-(2.2)，直到节点i将所接受到的位置信息的所有节点都加入邻接表，形成初 始邻接表；

(2.4)重复(2.3)，直到网络所有节点都得到的初始邻接表，从而形成网络的单位圆盘图 UDG。

步骤3.根据单位圆盘图UDG，利用Gabriel图构造算法，形成网络基于Gabriel图的拓 扑结构。

(3.1)节点i根据自己和邻居节点j的位置信息，计算以i和j二者连线为直径的圆的圆心 位置以及半径；

(3.2)节点i计算上述圆心到其他邻居节点的距离，并判断该距离是否小于上述半径，如 果小于则将该节点从邻居节点集中删除；

(3.3)重复步骤(3.1)-(3.2)，直到节点i对所有邻居节点j都进行操作，从而完成该节点邻 居节点的更新；

(3.4)重复步骤(3.3)，知道整个无线传感器网络中的所有节点k都进行了上述的操作，这就 完成了整个网络的Gabriel拓扑构建。

步骤4.根据Gabriel图的拓扑结构，形成数据通信拓扑结构：

(4.1)节点i在Gabriel图下分别计算与各邻居节点的距离，找出其中的最大距离，并调 整自身的发射功率，调整其通信半径与对大距离一致，降低通信干扰；

(4.2)节点i在调整半径后在新的通信半径下发送查询消息元数据信息，找出非对称链路 的邻居节点，从而得到对称链路的邻居节点集N(i)；

(4.3)重复(4.1)-(4.2)直到整个网络中所有节点i都得到了邻居节点集N(i)，形成网络的 数据通信拓扑。

步骤5.在构建的数据通信拓扑上，需要发送数据的节点将数据包进行压缩编码处理之 后以最小跳数路由算法沿着多路径传递到sink节点。

(5.1)需要发送数据的节点i首先查找自身的邻居节点集N(i)中邻居节点的数目；

(5.2)若邻居节点集的个数为1时，节点i对数据不做任何处理并将数据传递给唯一的邻 居节点j，节点j查找自身的邻居节点集N(j)的个数；

(5.3)若邻居节点集的个数大于等于2个时候将数据包首先通过线性编码将数据编码成多 份线性无关的数据，然后再对各个数据采用孙子剩余定理进行数据分割，数据分割的数目与 节点i的邻居节点集的个数相同；

(5.3.1)当节点j的邻居节点集的个数|N(j)|大于等于2个时，查找其邻居节点集N(j)中 是否包含sink节点，如果sink节点属于其邻居节点集，则直接选择sink节点为下一跳节点， 并且对要数据包不做任何处理；否则，执行步骤(5c2)；

(5.3.2)假设源节点S需要发送假设要发送的m个数据包为B₁，B₂，L，B_m，则源节点S从 有限域F_q中随机选取编码向量将源节点的m个数据包B₁，B₂，L，B_m编 码成n个数据包E₁，E₂，L，E_n(n≥m)：

$E_i=\underset{j=1}{\overset{m}{\Sigma }}{\alpha }_{\mathrm{ij}}{B}_j;i=\mathrm{1,2},L,n$

这样通过采用线性编码，就将源节点S本来要发送的m个数据包B₁，B₂，L，B_m转换为 E₁，E₂，L，E_n。这种编码的好处在于把不同的数据糅合在一起，减少了对单个数据的依赖， 增加了数据的传输可靠性；

(5.3.3)在传输编码后的数据E_k的时候，在节点内部定义固有的素数p_ki，其中素数的个 数与其邻居节点的个数相同。根据孙子定理可知，对任意给定的整数集合{E_k1，E_k2，...，E_kN}， 存在唯一的整数使得E_k=E_ki(modp_ki)。因此，在传输一个数据E_k时，只需要 在其邻居节点的各条路径上传输E_ki即可。

(5.4)将分割后的数据以最小跳数路由算法沿着各指向邻居节点的多路径传输到sink节 点；

(5.4.1)网络中节点到Sink节点的跳数用h表示，初始时Sink节点s设置h_s=0，其它节 点设置h＝∞；

(5.4.2)Sink节点广播带有h_s=0的路由建立信息，邻居节点j收到信息后，将其到Sink 节点的跳数h_j改为h_u=h_j+1=1，并广播带有h_j=1信息；

(5.4.3)当网络中任意节点v收到节点j广播的带有h_j的路由建立信息后，做如下处理： 1)若h_v<h_j+1，不作任何处理；2)若h_v＝h_j+1，将节点j添加到路由表中；3)若h_v>h_j+1，清 空现有的路由表，将节点j添加到路由表中，更新h_v＝h_j+1，并广播带有h_v的路由建立信息；

(5.4.4)沿着上述过程更新路由建立信息，最终可建立基于最小跳数的路由。

(5.5)sink节点收到分割后的数据，首先对分割后的数据进行合并。再通过网络编码进行 数据解码恢复出原始数据，即源节点所要发送的数据。

(5.5.1)当sink节点收到分割后的数据E_ki后，利用孙子剩余定理将分割的数据E_ki进行合 并，得到分割前的数据E_k。E_k的计算方法为：其中的系数 $c_{\mathrm{ki}}=Q_{\mathrm{ki}}{q}_{\mathrm{ki}},M_k=\underset{i}{\overset{N}{\Pi }}{p}_{\mathrm{ki}},Q_{\mathrm{ki}}=\frac{M_k}{p_{\mathrm{ki}}},$q_ki使得c_ki=1(modp_ki)；

(5.5.2)在得到分割前的数据E_k后，假定节点收到的m个数据分别为E₁，E₂，...E_m，进一步 判断相应的m个系数向量α₁，α₂，...α_k是否线性无关，如果是，则可以将数据通过编码进行解 码：

$\left(\begin{array}{c}{B}_1\\ B_2\\ M\\ B_m\end{array}\right)={\left(\begin{array}{ccc}{\alpha }_{11}& K& {\alpha }_{1m}\\ M& O& M\\ {\alpha }_{m1}& L& {\alpha }_{\mathrm{mm}}\end{array}\right)}^{-1}\left(\begin{array}{c}{E}_1\\ E_2\\ M\\ E_m\end{array}\right)$

通过上述的解码就可以将数据还原成原始数据B₁，B₂，...，B_m。

本发明的效果可以通过以下仿真进行进一步说明：

仿真条件

在L×L的平面区域内，随机抛撒N个无线传感器节点，使得网络节点均匀分布在监测 区域内，Sink节点位于监测区域边缘，负责接受采集数据并且对数据进行相关处理。假设数 据传输过程中不进行数据融合，同时假定整个网络具有结合了时分多址TDMA技术的理想 介质访问控制MAC协议。

其他仿真参数如表1所示：

表1

区域(m²) 100×100 节点数目 100 Sink位置 (0，0) 初始能量(J) 2 最大通信半径(m) 25 数据包大小(bits) [10，80]

仿真内容

仿真1，结合上述参数，生成网络单位圆盘图UDG与Gabriel图拓扑，如图3所示，其 中图3(a)是网络单位圆盘图UDG，图3(b)是网络Gabriel图拓扑。从图3(a)与图3(b)的比较 可以看出，Gabriel图拓扑保证了整个网络的连通性，同时与UDG相比，各节点邻居节点数 目减少，可以降低节点间通信干扰。

仿真2，结合上述仿真条件，分别采用基于孙子生于定理以及网络线性编码的传输方案 与只采用最小跳数据传输两种通信方案进行比较，分析同一网络下节点能量消耗情况以及数 据包传输情况，结果如图4-6所示。

在图4中，我们用最大能量消耗降低因子MERF来评估两种通信方式节点最大能量消 耗情况，其中w表示只采用最小跳数据传输所传输的数据包大小， w_CRT表示采用孙子生于定理所传输数据包的大小。在随机100次不同结构下随机发送 [10，80]bits大小的数据包，并将100次的结果进行排序。从图4中可以看出，相比于只采取 最小跳传输，采用孙子剩余定理以及编码方式传输每个节点可以至少节省45％左右的能量。 在图5中，给出了采用孙子剩余定理与未采取孙子剩余定理时发送数据包大小情况对比。从 图5中可以看出，采用孙子剩余定理可以将[10，80]bits的数据压缩到[10，20]bits。降低了单个 节点传输较大数据包所造成的能耗，均衡了网络负载，在一定程度上避免了网络拥塞。在图 6中，给出了考虑不可靠通信链路时，未采用网络编码以及采用网络编码数据传输的可靠性 对比。假设节点默认发送3个数据包，采用线性编码时可将数据编码发送5个数据包。从图 6中可以看出，采用线性编码的数据传输可靠性要远远大于未采用线性编码的数据传输可靠 性。

符号说明：WSNs：Wireless Sensor Networks无线传感器网络

i：传感器节点

j：传感器节点i的邻居节点

S：发送数据的源节点

w：未采取孙子剩余定理时发送数据包大小

w_CRT：采取孙子剩余定理时发送数据包大小

N(i)：节点i的邻居节点集

|N(i)|：节点i邻居节点集个数

MERF：Max Energy Reduction Factor最大能量降低因子

UDG：Unit Disk Graph单位圆盘图

GG：Gabriel Graph Gabriel图

MAC：Media Access Control介质访问控制

TDMA：Time Division Multiple Access时分多址

以上所述，仅为本发明较佳的具体实施方式，本发明的保护范围不限于此，任何熟悉本 技术领域的技术人员在本发明披露的技术范围内，可显而易见地得到的技术方案的简单变化 或等效替换均落入本发明的保护范围内。