占空比无线传感器网络最小期望延迟路由方法

摘要

本发明是一种占空比无线传感器网络最小期望延迟路由方法，解决在占空比无线传感器网络中所有节点到汇节点的最小期望延迟路由问题。其中最小期望延迟时间为占空比无线传感器网络中任一节点在任意时隙以任一邻居节点作为下一跳节点到基站的最小期望延迟时间。最小期望延迟路由方法包括初始化和路由更新，初始化是对所有传感器节点路由表和时隙竞争表的内容赋初值；根据网络的层次结构，路由更新由第0层逐层进行，通过层间路由更新信息的交互实现路由更新，节点依据网络最小期望延迟时间原则选择下一跳节点。本发明综合考虑了无线传感器网络节点休眠调度、无线链路质量、节点竞争程度，具有更大的报文投递率和更小的报文汇聚完成时间。

说明书

技术领域

本发明属于无线传感器网络技术领域，主要涉及到无线传感器网络中路由的 实现，具体是一种占空比无线传感器网络最小期望延迟路由方法，用于占空比无 线传感器网络的路由。

背景技术

无线传感器网络是由部署在监测区域内的大量廉价微型传感器节点组成，通 过无线通信方式形成的一个多跳自组织网络，具有大规模、自组织、应用相关、 资源受限、协同工作等特性，无线传感器网络应用于对指定区域或目标信息的实 时监测、精确感知、快速采集，已经在军事、工业、农业等诸多领域发挥作用。

路由是无线传感器网络中一项基础且重要的功能，它为网络提供互联机制， 在源和目的节点间建立传输路径。由于无线传感器节点通常以电池供电，而且电 量耗尽后很难更换，故为了节省节点能量，无线传感器网络通常采用占空比的工 作模式。占空比模式让节点在休眠状态和工作状态之间进行切换，节点只在少量 时间处于工作状态发送或接收数据，而在大部分时间处于休眠状态。占空比模式 节省了节点的能量，但是也带来了其它问题，如等待延迟和时变路由等，这些给 路由设计带来更大的挑战。因此，路由协议设计时应当考虑到传感器节点的这种 工作模式。

Shen Z,Zhang P.Routing in Duty-Cycled Surveillance Sensor Networks[J]. International Journal of Distributed Sensor Networks,2013.提出了一种最小延迟路 由方法，该方法一次执行即可为全网中所有节点确定在任意时隙到基站的最小延 迟路由。在寻找路由的过程中，每个节点依据邻居节点的路由更新信息更新自身 的路由表，最终每个节点的路由表都将收敛得到任意时隙到基站的最小延迟以及 相应的下一跳节点。

此方法具有高效完备的特点，高效性表现在，该算法一次执行，即可完成为 任意节点寻找最小延迟路由的过程；完备性表现在，该算法的一次执行，即可为 所有节点在任意时隙寻找最小延迟路由，在时间维度上保证完备性。

最小延迟路由从理论的角度很好解决了占空比无线传感器网络最小延迟路 由，但是还存在以下两方面问题。

一方面，没有考虑无线链路质量对链路延迟的影响。在实际当中，无线链路 质量随时间和空间的变化而变化，导致无线链路具有不稳定性，而基于理想链路 假设的最小延迟路由方法，只考虑到由于占空比工作方式造成的链路时延，而忽 略无线链路质量对报文传输延迟的影响。

另一方面，没有考虑节点竞争对链路延迟的影响。最小延迟路由采用链路延 迟计算节点的下一跳节点。但是大量事件并发需要大量报文汇聚，如此将伴随节 点竞争的提升，节点竞争程度增高，同样影响到报文传输延迟。

在网上通过检索，未发现与本发明密切相关的文献。

发明内容

针对现有技术中最小延迟路由方法没有考虑到无线链路质量和节点竞争程 度两方面因素，而在占空比无线传感器网络寻找路由的过程中，由于不考虑无线 链路质量和节点竞争的影响，会直接影响路由有效性，为此本发明提出一种占空 比无线传感器网络最小期望延迟路由方法。

本发明是一种占空比无线传感器网络最小期望延迟路由方法，全网以同步周 期占空比的方式工作，一个周期由T个连续时隙组成，T≥1，依照应用需求， 任意节点在周期T内的一个时隙或多个时隙处于工作状态，其余时隙处于休眠状 态，网络中每个节点依据其距离基站的最小跳数确定所属层次，基站属于第0 层，距离基站最小跳数为1跳的节点属于第一层，依次类推，最大层用maxLayer 表示，节点内还包括一个路由表、一个时隙竞争表、一个父邻节点表 fatherNeighbors和一个子邻节点表sonNeighbors，所述最小期望延迟路由方法 包含初始化过程和路由更新过程两个部分。

第1部分，初始化过程：

初始化过程在节点间是相互独立的，具体是所有传感器节点对自身路由表和 时隙竞争表的内容赋初值，路由表包含期望延迟信息表expDelay[1,2,...,T]和下一 跳节点信息表nextHop[1,2,...,T]，其中expDelay[1,2,...,T]包含T项，表示节点在 一个周期内，从第1个时隙至第T个时隙传输报文至基站节点的期望延迟时间， 用时隙表示，nextHop[1,2,...,T]表示节点在一个周期内，从第1个时隙至第T个 时隙传输报文至基站节点路由中的下一跳节点，任意节点i的时隙竞争表为 competors_i[1,2,...,T]，包含T项，每一项包含在相应时隙以节点i作为下一跳的 节点。

第2部分，路由更新过程：

路由更新过程由第0层开始逐层进行，首先由基站构造路由更新信息并进行 广播，逐层更新过程中，任意两层的层间节点通过路由更新信息的交互实现较高 一层节点路由表的更新，节点依据网络最小期望延迟时间原则选择下一跳节点， 节点的时隙竞争表或路由表获得更新，都将构造路由更新信息并进行广播，层间 路由更新过程结束后，较高一层节点获得任意时隙到基站的最小期望延迟路由， 直到网络中的倒数第二层即maxLayer-1层与最大层即maxLayer层的层间路由 更新过程结束，全网路由更新过程完毕。

本发明的实现还在于占空比无线传感器网络最小期望延迟路由方法，节点路 由表的初始化、时隙竞争表的初始化包括有如下步骤：

1.a路由表的初始化，初始化基站s的期望延迟信息表和下一跳节点信息表 为expDelay_s[1,2,...,T]＝0，nextHop_s[1,2,...,T]＝s；对于除基站外任意节点i，初 始化expDelay_i[1,2,...,T]＝∞,nextHop_i[1,2,...,T]＝i，∞通常用一个极大数表示。

1.b时隙竞争表的初始化，初始化所有节点的时隙竞争表内的T项皆为空。

本发明的实现还在于占空比无线传感器网络最小期望延迟路由方法，逐层更 新过程中，任意两层的层间节点通过路由更新信息的交互实现较高一层节点路由 表的更新，包括两种情况：

任意节点i接收fatherNeighbors中任一节点j发来的路由更新信息，路由更 新信息中包含节点j的时隙竞争表和期望延迟信息表，节点i根据路由更新信息， 对一个周期内的每个时隙计算以节点j为下一跳到基站sink的期望延迟。

2.1.a在任意时隙，节点i的期望延迟信息表对应项为初始化状态，更新期望 延迟信息表的对应项为以节点j为下一跳计算得到的期望延迟，更新下一跳节点 信息表对应项为节点j。

2.1.b在任意时隙，节点i的期望延迟信息表对应项不为初始化状态，节点j 若为节点i在该时隙的下一跳节点，则直接更新期望延迟信息表对应项为以节点 j为下一跳计算得到的新的期望延迟，节点j若不为节点i的下一跳，同样在该 时隙以节点j为下一跳计算得到新的期望延迟，如果新的期望延迟小于节点i期 望延迟信息表对应项，更新期望延迟信息表对应项为新的期望延迟，并更新下一 跳节点信息表对应项为节点j。

任意节点i接收到sonNeighbors中任一节点j发来的路由更新信息，路由更 新信息中包含节点j的下一跳节点信息表，根据路由更新信息，节点i遍历节点j 的下一跳节点信息表。

2.2.a在任意时隙，节点j的下一跳节点信息表对应项为节点i，若节点i的 时隙竞争表对应项不包含节点j，在节点i的时隙竞争表对应项中添加节点j。

2.2.b在任意时隙，节点j的下一跳节点信息表对应项不为节点i，若节点i的 时隙竞争表对应项包含节点j，从节点i的时隙竞争表对应项中删除节点j，时 隙竞争表中不包含重复项。

本发明采用上述占空比无线传感器网络中最小期望延迟路由方法，从基站开 始逐层更新，一次执行即可为所有节点确定在任意时隙至基站的最小期望延迟路 由。

本发明的实现还在于：占空比无线传感器网络中任一节点i在任意时隙t以任 一邻居节点j作为下一跳节点到基站sink的期望延迟时间为

$\mathrm{expDela}{y}_i\left(t\right)=\underset{s=1}{\overset{\mathrm{SMAX}}{\Sigma }}{P}_{\mathrm{ij}}\left(s\right)\times [{\mathrm{delay}}_{\mathrm{ij}}(t,s)+\mathrm{expDela}{y}_j\left((t+{\mathrm{delay}}_{\mathrm{ij}}(t,s))\mathrm{mod}T\right)]$

其中，delay_ij(t,s)表示节点i到节点j的延迟时间，具体是节点i以节点j作 为下一跳节点，从第t时隙起，直到报文被第s次尝试发送且发送成功，所经历 的时隙数；t+delay_ij(t,s)表示节点j转发来自节点i的报文的时隙；modT表示对 T取模，(t+delay_ij(t,s))modT表示在周期内，节点j转发来自节点i的报文的时 隙；expDelay_j((t+delay_ij(t,s))modT)表示在第(t+delay_ij(t,s))modT时隙，节点j 到sink的期望延迟时间；delay_ij(t,s)+expDelay_j((t+delay_ij(t,s))modT)表示节点i 以节点j作为下一跳节点到sink的延迟时间；P_ij(s)表示节点i以节点j作为下一 跳节点，报文在第s次尝试发送才发送成功的概率；SMAX表示报文最大尝试发 送次数，P_ij(s)与delay_ij(t,s)+expDelay_j((t+delay_ij(t,s))modT)相乘并进行从s＝1 到s＝SMAX的累和表示节点i在时隙t以邻居节点j作为下一跳节点到基站sink 的期望延迟时间。

本发明采用上述公式计算期望延迟作为路由更新过程中节点选择下一跳的 度量标准，提高节点选择路由的有效性。

本发明的实现还在于：期望延迟时间中用P_ij(s)表示节点i向节点j传输报 文，报文在第s次尝试发送才发送成功的概率为

P_ij(s)＝(1-(Pd_ij×Pb_ij))^s-1(Pd_ij×Pb_ij)/P_ij

P_ij表示报文最大尝试发送次数SMAX内，报文成功传输的概率为

$P_{\mathrm{ij}}=\underset{s=1}{\overset{\mathrm{SMAX}}{\Sigma }}{(1-{\mathrm{Pb}}_{\mathrm{ij}}\times {\mathrm{Pd}}_{\mathrm{ij}})}^{s-1}({\mathrm{Pb}}_{\mathrm{ij}}\times {\mathrm{Pd}}_{\mathrm{ij}})$

Pb_ij表示节点竞争成功率，0≤Pb_ij≤1，通过现有无线链路质量估计方法获 得，Pd_ij表示报文成功传输率，0≤Pd_ij≤1。

本发明采用上述计算报文在第s次尝试发送才发送成功概率的方法，充分考 虑到无线链路质量和节点竞争程度两个影响无线传感器网络路由的因素。

本发明的实现还在于：报文成功传输的概率中用Pb_ij表示节点i向节点j传输 报文，节点i竞争成功的概率，在某个时隙，节点i存在n-1个竞争节点时，节 点i竞争成功的概率为

${\mathrm{Pb}}_{\mathrm{ij}}=\underset{c=0}{\overset{n-1}{\Sigma }}{p}_s\left(c\right)$

其中$p_s\left(c\right)=p_{n-1}^c\times p_{\mathrm{cs}}\left(c\right),p_{n-1}^c=C_{n-1}^c{\left(\frac{1}{2}\right)}^c{\left(\frac{1}{2}\right)}^{n-1-c}$表示节点i的n-1个竞争节点 中有c个节点与节点i同时有报文的概率，表示当节点i与c个有报 文的节点竞争节点j，节点i竞争成功的概率。

本发明采用上述计算节点竞争成功的概率，量化了节点竞争程度对无线传感 器网络路由的影响。

与现有技术相比，本发明的优点

一、本发明中提出的占空比无线传感器网络最小期望延迟路由方法，综合考 虑到节点休眠调度、无线链路质量、节点竞争程度三个方面。节点休眠调度节约 了无线传感器网络节点的能量，延长了无线传感器网络的寿命。引入无线链路质 量和节点竞争程度为无线传感器网络的路由提供更为有效的寻找路由的度量标 准，为所有节点确定最小期望延迟路由。

二、本发明中提出的占空比无线传感器网络最小期望延迟路由方法，经一次 执行，即可得到所有节点在任意时隙至基站的最小期望延迟路由，最小期望延迟 路由总是为节点选取期望延迟更小的节点作为下一跳，也就意味着竞争者数目更 小、链路质量更好的下一跳节点。因此最小期望延迟路由方法具有更大的报文投 递率和更小的报文汇聚完成时间。

附图说明

图1是本发明实施例1的示意图，也是任一节点i接收任意节点j发来的路 由更新信息后，路由表或时隙竞争表的更新过程。

图2是本发明实施例3-4的示意图,其中，图2(a)为占空比无线传感器网络 拓扑图，图2(b)是图2(a)所示网络拓扑中节点工作休眠时隙分布示意图。

图3是本发明实施例5所述占空比无线传感器网络占空比为1/10，最大尝试 发送次数为4时，不同报文突发，报文汇聚完成时间对比曲线图。

图4是本发明实施例5所述占空比无线传感器网络占空比为1/10，最大尝试 发送次数为6时，不同报文突发，报文汇聚完成时间对比曲线图。

图5是本发明实施例6所述占空比无线传感器网络占空比为1/10，报文突发 为10％时，不同报文尝试发送次数，报文投递率对比曲线图。

图6是本发明实施例6所述占空比无线传感器网络占空比为1/10，报文突发 为30％时，不同报文尝试发送次数，报文投递率对比曲线图。

图7是本发明实施例6所述占空比无线传感器网络占空比为1/10，报文突发 为100％时，不同报文尝试发送次数，报文投递率对比曲线图。

具体实施方式

下面结合附图和实施例对本发明详细说明。

以下实施实例用于说明本发明，但不用来限制本发明的适用范围。

实施例1

全网以同步周期占空比的方式工作，一个周期由T个连续时隙组成，T≥1， 依照应用需求，任意节点在周期T内的一个时隙或多个时隙处于工作状态，其余 时隙处于休眠状态，网络中每个节点依据其距离基站的最小跳数确定所属层次， 基站为第0层，距离基站最小跳数为1跳的节点为第一层，依次类推，最大层用 maxLayer表示，节点内还包括一个路由表、一个时隙竞争表、一个父邻节点表 fatherNeighbors和一个子邻节点表sonNeighbors，所述最小期望延迟路由方法 包含初始化过程和路由更新过程两个部分。

第1部分，初始化过程：

初始化过程在节点间是相互独立的，具体是所有传感器节点对自身路由表和 时隙竞争表的内容赋初值；路由表包含期望延迟信息表expDelay[1,2,...,T]和下一 跳节点信息表nextHop[1,2,...,T]，其中expDelay[1,2,...,T]包含T项，表示节点在 一个周期内，从第1个时隙至第T个时隙传输报文至基站节点的期望延迟时间， 用时隙表示，nextHop[1,2,...,T]表示节点i从第1个时隙至第T个时隙传输报文至 基站节点路由中的下一跳节点；任意节点i的时隙竞争表competors_i[1,2,...,T]包 含T项，每一项包含在相应时隙以节点i作为下一跳的节点。

节点路由表的初始化、时隙竞争表的初始化包括有如下步骤：

1.a路由表的初始化，初始化基站s的期望延迟信息表和下一跳节点信息表 为expDelay_s[1,2,...,T]＝0，nextHop_s[1,2,...,T]＝s；对于除基站外任意节点i，初 始化expDelay_i[1,2,...,T]＝∞,nextHop_i[1,2,...,T]＝i，∞通常用一个极大数表示。

1.b时隙竞争表的初始化，初始化所有节点的时隙竞争表内T项皆为空。

第2部分，路由更新过程：

路由更新过程由第0层开始逐层进行，首先由基站构造路由更新信息并进行 广播，逐层更新过程中，任意两层的层间节点通过路由更新信息的交互实现较高 一层节点路由表的更新，节点依据网络最小期望延迟时间原则选择下一跳节点， 节点的时隙竞争表或路由表获得更新，都将构造路由更新信息并进行广播，层间 路由更新过程结束后，较高一层节点获得任意时隙到基站的最小期望延迟路由， 直到网络中的倒数第二层即maxLayer-1层与最大层即maxLayer层的层间路由 更新过程结束，全网路由更新过程完毕。逐层更新过程中，任意两层的层间节点 通过路由更新信息的交互实现较高一层节点路由表的更新，包括两种情况，参见 图1。

任意节点i接收fatherNeighbors中任一节点j发来的路由更新信息，路由更 新信息中包含节点j的时隙竞争表和期望延迟信息表，节点i根据路由更新信息， 对一个周期内的每个时隙，计算以节点j为下一跳，到基站sink的期望延迟：

2.1.a在任意时隙，若节点i的期望延迟信息表对应项为初始化状态，更新期 望延迟信息表对应项为以节点j为下一跳计算得到的期望延迟，更新下一跳节点 信息表对应项为节点j。

2.1.b在任意时隙，节点i的期望延迟信息表对应项不为初始化状态，节点j 若为节点i在该时隙的下一跳节点，则直接更新期望延迟信息表对应项为以节点 j为下一跳计算得到的新的期望延迟，节点j若不为节点i的下一跳，同样在该 时隙以节点j为下一跳计算得到新的期望延迟，如果新的期望延迟小于节点i期 望延迟信息表对应项，更新期望延迟信息表对应项为新的期望延迟，并更新下一 跳节点信息表对应项为节点j。

任意节点i接收到sonNeighbors中任一节点j发来的路由更新信息，路由更 新信息中包含节点j的下一跳节点信息表，根据路由更新信息，节点i遍历节点j 的下一跳节点信息表：

2.2.a在任意时隙，节点j的下一跳节点信息表对应项为节点i，若节点i的 时隙竞争表对应项不包含节点j，在节点i的时隙竞争表对应项中添加节点j；

2.2.b在任意时隙，节点j的下一跳节点信息表对应项不为节点i，若节点i的 时隙竞争表对应项包含节点j，从节点i的时隙竞争表对应项中删除节点j，时 隙竞争表中不包含重复项。

实施例2

占空比无线传感器网络最小期望延迟路由方法同实施例1，其中期望延迟时 间为

$\mathrm{expDela}{y}_i\left(t\right)=\underset{s=1}{\overset{\mathrm{SMAX}}{\Sigma }}{P}_{\mathrm{ij}}\left(s\right)\times [{\mathrm{delay}}_{\mathrm{ij}}(t,s)+\mathrm{expDela}{y}_j\left((t+{\mathrm{delay}}_{\mathrm{ij}}(t,s))\mathrm{mod}T\right)]$

该延迟时间是占空比无线传感器网络中任一节点i在任意时隙t以任一邻居 节点j作为下一跳节点到基站sink的期望延迟时间，式中，delay_ij(t,s)表示节点i 到节点j的延迟时间，具体是节点i以节点j作为下一跳节点，从第t时隙起，直 到报文被第s次尝试发送且发送成功，所经历的时隙数；t+delay_ij(t,s)表示节点j 转发来自节点i的报文的时隙；modT表示对T取模，(t+delay_ij(t,s))modT表示 在周期内，节点j转发来自节点i的报文的时隙；expDelay_j((t+delay_ij(t,s))modT) 表示在第(t+delay_ij(t,s))modT时隙，节点j到sink的期望延迟时间； delay_ij(t,s)+expDelay_j((t+delay_ij(t,s))modT)表示节点i以节点j作为下一跳节点 到sink的延迟时间；P_ij(s)表示节点i以节点j作为下一跳节点，报文在第s次尝 试发送才发送成功的概率；SMAX表示报文最大尝试发送次数，P_ij(s)与 delay_ij(t,s)+expDelay_j((t+delay_ij(t,s))modT)相乘并进行从s＝1到s＝SMAX的累 和表示节点i在时隙t以邻居节点j作为下一跳节点到基站sink的期望延迟时间。

期望延迟时间中用P_ij(s)表示节点i向节点j传输报文，报文在第s次尝试发 送才发送成功的概率为

P_ij(s)＝(1-(Pd_ij×Pb_ij))^s-1(Pd_ij×Pb_ij)/P_ij

P_ij表示报文最大尝试发送次数SMAX内，报文成功传输的概率为

$P_{\mathrm{ij}}=\underset{s=1}{\overset{\mathrm{SMAX}}{\Sigma }}{(1-{\mathrm{Pb}}_{\mathrm{ij}}\times {\mathrm{Pd}}_{\mathrm{ij}})}^{s-1}({\mathrm{Pb}}_{\mathrm{ij}}\times {\mathrm{Pd}}_{\mathrm{ij}})$

Pb_ij表示节点竞争成功率，0≤Pb_ij≤1，Pd_ij表示报文成功传输率， 0≤Pd_ij≤1。

报文成功传输的概率中用Pb_ij表示节点i向节点j传输报文，节点i竞争成功 的概率，在某个时隙，节点i存在n-1个竞争节点时，节点i竞争成功的概率为

${\mathrm{Pb}}_{\mathrm{ij}}=\underset{c=0}{\overset{n-1}{\Sigma }}{p}_s\left(c\right)$

其中$p_s\left(c\right)=p_{n-1}^c\times p_{\mathrm{cs}}\left(c\right),p_{n-1}^c=C_{n-1}^c{\left(\frac{1}{2}\right)}^c{\left(\frac{1}{2}\right)}^{n-1-c}$表示节点i的n-1个竞争节点 中有c个节点与节点i同时有报文的概率，表示当节点i与c个有报 文的节点竞争节点j，节点i竞争成功的概率。

实施例3

占空比无线传感器网络最小期望延迟路由方法同实施例1-2，本例以图2(a) 所示的简单网络，对本发明的占空比无线传感器网络最小期望延迟路由方法逐层 路由更新过程中第0层与第1层的层间节点路由更新过程进行描述。

图2(a)所示为一个三层树形拓扑结构的占空比无线传感器网络，节点0作 为基站属于第0层，节点1～节点2距离节点0一跳的距离属于第一层，节点3～ 节点6距离节点0两跳的距离属于第三层。节点间的连线表示节点互相连通，因 为最小期望延迟路由严格按照层次结构执行路由更新，路由更新信息的传输和接 收仅仅发生在层间，简化起见，略去同一层可能互相连通节点间的连线。假设互 连节点间双向链路质量一致，节点间的双向链路报文成功传输率均为1，即假设 任意节点i与节点j之间Pd_ij＝Pd_ji＝1。

节点1～节点6以同步周期占空比模式工作，周期T＝10，基站节点0拥有 持续的供电，在一个周期T个时隙均处于工作状态，除基站节点外其余节点在一 个周期内仅工作一个时段，且一个时段仅包含一个时隙，参见图2(b)为节点 工作休眠时隙分布示意图，因此该无线传感器网络占空比为0.1，设定报文尝试 发送次数上限SMAX＝6。

路由更新过程由第0层开始逐层进行，节点0构造路由更新信息并广播，路 由更新信息包含节点0路由表内期望延迟信息表和时隙竞争表，其中期望延迟信 息表如表1所示，时隙竞争表也包含10项，初始化均为空。

节点1或节点2接收fatherNeighbors中节点0发来的路由更新信息，分别 以节点0作为下一跳更新自身的路由表，节点1与节点2更新后的路由表相同， 如表2所示。

表1节点0的期望延迟信息表

时隙 1 2 3 4 5 6 7 8 9 10 期望延迟 0 0 0 0 0 0 0 0 0 0

表2节点1或节点2的路由表

时隙 1 2 3 4 5 6 7 8 9 10 期望延迟 1 1 1 1 1 1 1 1 1 1 下一跳节点 0 0 0 0 0 0 0 0 0 0

第1层节点1和节点2的路由表获得更新，因此节点1和节点2分别构造路 由更新信息并广播，路由更新信息包含节点路由表内的下一跳节点信息表，如表 3所示。

表3节点1或节点2下一跳节点信息表

时隙 1 2 3 4 5 6 7 8 9 10 下一跳节点 0 0 0 0 0 0 0 0 0 0

节点0接收到来自sonNeighbors中节点1和节点2的路由更新信息，更新自 身的时隙竞争表，如表4所示。

在任意时隙，节点1或节点2的下一跳节点信息表对应项为节点0，节点0 的时隙竞争表对应项初始化为空，不包含节点1和节点2，在节点0的时隙竞争 表每一项中添加节点1和节点2，时隙竞争表获得更新的节点0构造路由更新信 息并广播。

节点1或节点2接收到来自fatherNeighbors中节点0的路由更新信息，更 新自身的路由表，节点1与节点2更新后的路由表相同，如表5所示

表4节点0的时隙竞争表

时隙 竞争列表 1 1，2 2 1，2 3 1，2 4 1，2 5 1，2 6 1，2 7 1，2 8 1，2 9 1，2 10 1，2

表5节点1或节点2的路由表

时隙 1 2 3 4 5 6 7 8 9 10 期望延迟 1.3 1.3 1.3 1.3 1.3 1.3 1.3 1.3 1.3 1.3 下一跳节点 0 0 0 0 0 0 0 0 0 0

在任意时隙，若节点1或节点2的期望延迟信息表均不为初始化状态，对任 意时隙计算得到期望延迟，由于节点0为节点1或节点2当前的下一跳，则不做 对比直接更新各自路由表中的期望延迟信息表。

节点1与节点2的下一跳节点均只有节点0，不可能再更换下一跳节点，第 0层与第1层之间的层间路由更新过程结束。

实施例4

占空比无线传感器网络期望延迟时间的计算，同实施例2。

假设图2(a)所示简单网络第0层与第1层的层间路由更新结束，当前节点1 的路由表如表7所示。

表7节点1的路由表

时隙 1 2 3 4 5 6 7 8 9 10 期望延迟 1.3 1.3 1.3 1.3 1.3 1.3 1.3 1.3 1.3 1.3 下一跳节点 0 0 0 0 0 0 0 0 0 0

节点1的时隙竞争表如表8所示。

表8节点1的时隙竞争表

时隙 竞争列表 1 3，4，5 2 3，4，5 3 4，6 4 3，5 5 4，5，6 6 3，4，5 7 6 8 5 9 5 10 4，6

节点3接收到来自fatherNeighbors中节点1的路由更新信息，该路由更新 信息包含节点1的期望延迟信息表和时隙竞争表。对一个周期内的每个时隙，计 算在该时隙以节点1为下一跳到节点0的期望延迟时间。

计算节点3在第1个时隙以节点1作为下一跳，到基站sink的期望延迟时间 为$\exp {\mathrm{Delay}}_3\left(1\right)=\underset{s=1}{\overset{6}{\Sigma }}{P}_{31}\left(s\right)\times [{\mathrm{delay}}_{31}(1,s)+{\mathrm{expDelay}}_1\left((1+{\mathrm{delay}}_{31}(1,s))\mathrm{mod}10\right)],$其 中，delay₃₁(1,s)表示节点3到节点1的延迟时间，具体是节点3以节点0作为下 一跳节点，从第1时隙起，直到报文被第s次尝试发送且发送成功所经历的时隙 数，例如当s＝1时，在第1时隙，节点3若要向节点1发送报文，节点1在第1 个时隙处于工作状态，可以直接发送，仅需要1个时隙的报文传输延迟时间；当 s＝2时，说明在第一个时隙，节点3向节点1发送报文失败，紧接着，节点3 在第2个时隙向节点1发送报文，节点1在第2个时隙处于休眠状态，需要等到 下个周期的第1个时隙，节点3才能第二次尝试向节点1发送报文，需要10个 时隙的报文传输延迟时间，包含9个时隙用来等待和1个时隙用来传输，再加上 第一次传输失败的1个时隙，因此总延迟时间为11个时隙。1+delay₃₁(1,s)表示 节点1转发来自节点3的报文的时隙，例如在第1个时隙，节点3第一次发送就 发送成功，那么节点1最快在第2个时隙就转发该报文；而在第1个时隙，节点 3第二次发送并发送成功，那么节点1最快在距离第1个时隙之后的第12个时 隙转发该报文。modT表示对T取模，(1+delay₃₁(1,s))mod10表示在周期内，节 点0转发来自节点1的报文的时隙，节点1仅在第1个时隙处于工作状态，因此 节点1最快只能在周期内的第2个时隙转发报文；表 示在第(1+delay₃₁(1,s))mod10个时隙，节点1到sink的期望延迟时间。P₃₁(s)表 示节点3以节点1作为下一跳节点，报文在第s次尝试发送才发送成功的概率， 由于节点3接收到的节点1的路由更新信息中，时隙竞争表在时隙1包含除了节 点3以外另外2个竞争者，那么${\mathrm{Pb}}_{31}=\underset{c=0}{\overset{3-1}{\Sigma }}{p}_s\left(c\right)=\underset{c=0}{\overset{3-1}{\Sigma }}{C}_{3-1}^c{\left(\frac{1}{2}\right)}^c{\left(\frac{1}{2}\right)}^{3-1-c}\times \frac{1}{c+1},$其中 可得Pb₃₁＝0.58，又假设的Pd₃₁＝1，得 P₃₁＝0.99，根据P₃₁(s)＝(1-(Pd₃₁×Pb₃₁))^s-1(Pd₃₁×Pb₃₁)/P₃₁计算。相关结果的如 表9所示。

最终可求得节点3在第1个时隙以节点1作为下一跳到节点0的期望延迟时 间expDelay₃(1)＝9.13，单位为时隙。

表9占空比无线传感器网络最小期望延迟时间计算过程

本发明采用上述占空比无线传感器网络最小期望延迟时间，量化了节点竞争 程度对无线传感器网络路由的影响，结合报文成功传输率充分考虑到无线链路质 量和节点竞争程度两个影响无线传感器网络路由的因素，通过最小期望延迟时间 计算的最小期望延迟作为路由更新过程中节点选择下一跳的度量标准，提高节点 选择路由的有效性。

实施例5

占空比无线传感器网络最小期望延迟路由方法同实施例1-4，对以上方案进 行仿真。将本发明中的最小期望延迟路由(MEDR)与Shen Z,Zhang P.Routing in  Duty-Cycled Surveillance Sensor Networks[J].International Journal of Distributed  Sensor Networks,2013.提出的最小延迟路由(MDR)进行报文汇聚完成时间进行 比较。

仿真中具体参数为场景的范围设定在100×100m的平面之内，节点数为50 到500之间，假设随机部署的节点不会产生孤岛，节点0为基站节点，节点传输 半径为25，占空比设定为1/10，报文最大尝试发送次数用C表示，仿真中分别 考虑两种尝试发送次数C＝4和C＝6。

报文汇聚两种典型的应用场景：1)无线传感器网络被部署好以后，任意节 点监测到用户感兴趣的事件即刻向基站节点汇聚，但通常一个事件的发生将导致 一个局部区域内的节点均被触发，被触发同时将自身感知到的事件原始数据进行 汇聚，造成报文突发，分别考虑两种规模的报文突发，监测到事件的节点数目分 别占全网节点数目的10％、30％，即在一个包含全网规模10％的节点的局域内， 每个节点都有一个报文需要汇聚；2)无线传感器网络被部署好以后，全网除汇 节点外所有节点每间隔一段时间采集一次数据并进行汇聚，类似于突发报文的节 点数目占全网节点数目的100％，即全网范围内，每个节点都有一个报文要汇聚。

参见图3及图4所示横坐标为节点数目，纵坐标为报文汇聚完成的时间。出 于对竞争均衡和链路质量的综合考虑，最小期望延迟路由方法总是为节点选取期 望延迟更小的节点作为下一跳，也就意味着为节点选择竞争者数目更小、链路质 量更好的下一跳节点，因此最小期望延迟路由MEDR较MDR具有更小的报文 汇聚完成时间。

实施例6

占空比无线传感器网络最小期望延迟路由方法，同实施例1-4，对以上方案 进行仿真，将本发明中的最小期望延迟路由MEDR与最小延迟路由MDR的报 文投递率进行比较。

参见图5-图7所示横坐标为节点数目，纵坐标为报文投递率。由于考虑到 无线链路质量对报文传输的影响，MEDR总是为节点选取链路质量更好的节点 作为下一跳节点，因此MEDR的丢包率更低，图5～7中MEDR与MDR的报文 投递率，随着报文最大尝试发送次数增大，报文被丢弃的概率降低，报文的投递 率均会有所上升，而在相同的最大尝试发送次数条件下，MEDR较MDR具有更 高的报文投递率。

简而言之，本发明的占空比无线传感器网络最小期望延迟路由方法，解决在 占空比无线传感器网络中所有节点到汇节点的最小期望延迟路由问题。其中最小 期望延迟时间为占空比无线传感器网络中任一节点在任意时隙以任一邻居节点 作为下一跳节点到基站的最小期望延迟时间。最小期望延迟路由方法包括初始化 和路由更新，初始化是对所有传感器节点路由表和时隙竞争表的内容赋初值；根 据网络的层次结构，路由更新由第0层逐层进行，通过层间路由更新信息的交互 实现路由更新，节点依据网络最小期望延迟时间原则选择下一跳节点。本发明综 合考虑了无线传感器网络节点休眠调度、无线链路质量、节点竞争程度，具有更 大的报文投递率和更小的报文汇聚完成时间。