每周文章分享-98

背景介绍

关键技术

算法介绍

1. 系统模型

(1) 网络模型：本文考虑的网络是一个数据采集网络，网络半径为R，由中心sink节点和普通节点组成。普通节点定期生成监测数据包，数据包汇聚后采用多跳方式向sink节点发送数据包。对于节点s_i，根据到达节点s_i的数据包的时序，将接收到的数据包与节点s_i中的当前数据包聚合，聚合完成后s_i向下一个节点发送聚集的数据包。

(2) 节点模式：网络中节点的部署密度为ρ，通信半径为r。该网络被分成几个环，第k个环由具有k跳到sink的所有节点组成，并且一个环的宽度l小于r的值，l=αr|0<α≤1(见图1)。节点采用最小跳路由(MHR)进行数据传输。

定义1：考虑到节点A位于第T环中，其转发集FS是指节点A传输范围内第T-1环的节点集合。如图1所示，可以看出，节点A的FS由节点E、F、G组成。

(3) 网络中的节点采用局部同步的方式，从而以较低的传输时延与其FS中的节点进行通信。整个时间由小的等长时隙组成，一个传输周期由w个时隙组成。

图1 网络结构

2. 问题陈述

根据以上分析，定义并形式化了所解决问题如下：

(1) 最大化网络寿命：一般而言，网络寿命是指消耗第一个节点的所有能量的持续时间。原因是当能量耗尽时，数据包将被中断，数据分组传输过程将无法完成，这将损害网络安全。考虑到节点i，Ei代表能量消耗，因此，最大化网络寿命可以讨论如下：

(2) 最大限度地提高能源利用率：能耗是评估网络前期工作的重要指标。如何在不损害网络寿命的前提下利用剩余能量提高网络性能是值得进一步研究的问题。能量指标可以用能效利用率来表示，它是指所有节点的能耗与所有初始能量的比值。最大化能量有效利用率如下：

(3) 最小化延迟延迟(记为D)：D是从生成数据分组到将数据分组发送到宿的持续时间。假设多跳路由的0跳数据的时延为d_0，则最小化的端到端(E2E)时延如下：

因此，目标可以通过以上三个公式获得。

3. ESQ ALGORITHM

研究动机：在基于仲裁系统设计的过程中，需要考虑以下几个方面

(1)两个节点之间的交集时隙越大，转发时延越小。

(2)在QTS总数确定的情况下，如果QTS中不允许包含某些行和列，则会增加两个节点之间的相交时隙数。如果增加QTS的数量，相交时隙数将会增加。然而，增加节点的QTS也会增加节点的能量消耗，导致网络寿命的下降。在保持QT总数不变的情况下增加交叉口数量具有重要意义。

(3)数据传输过程需要持续几个时隙，因此不会选择没有数据操作的时隙作为QTS。这样可以增加交叉时隙，降低网络时延。

ST-Gird Quorum 系统

定义2：考虑两个集合U={01,…,n−1}和M={M1,M2,…,MQ}。对于任一Mi属于M，且Mi是U的子集，如果Mi满足条件Mj∈M∧Mi∩Mj=∅，则M是一个仲裁系统。

定义3：考虑到n不能是任何整数，它必须是完美平方。设1≤m1≤w，0≤u≤w√n−1，S(n,w,u,m1)表示如下：

当n=16, w=3时, S(16,3,2,2) = {0,1,6,7,8,9,10,11} 可以如图2(A)所示，其中Qt仅在√n×√n网格的前w行中被选择。M1表示在√n×√n网格中选择m1行，u表示第一个QT的序列号。因此，QTS序列随u的不同而不同。

图2. n = 16,w = 3 (a) S-clique(16,3,2,2); (b) T-clique (16,3,41);(c) ST-grid(24,21)

定义4：T-clique：设1≤m2≤√n，0≤v≤w√n−1，T(n,w,v,m2)如下：

其中，m2表示在√n×√n网格中选择m2列，而v表示第一QT的序列号。因此，所获得的QTS序列随不同的v而变化，例如，当n=16，w=3时，T-clique(16,3,4,1)={0,4,8}(见图2(B))。

4. ESQ based MAC-protocol

在以上分析的基础上，本文对ESQ协议进行了讨论。节点选择S-clique还是T-clique取决于环号。如果偶数环中的节点选择S-clique，奇数环中的节点选择T-clique。否则，奇数环中的节点选择S-clique。在选择S-clique和T-clique之后形成ST-grid。在选择S- or T-clique之后，根据定理2选择合适的参数。在w×n网格中确定QTS的数目，然后在n×n网格中将其转换为QTS序列号。

图3.  QTS关系映射

图4. ST-grid quorum时隙结构

图4显示了ST-grid Quorum系统的框架结构。数据收集周期中的时隙时间n是16(即，信标间隔，BI)，非QTS中的节点不发送数据分组。然而，节点的QTS的第一部分是信标窗口(BW)时间，其余的时隙是在其间执行数据操作的数据窗口(DW)。BW时隙中的节点决定是否执行数据操作。如果不需要数据操作，节点将在随后的DW时间保持休眠状态。如果需要数据操作，将在下一个DW时间内完成。传感器节点A选择S-clique，节点B选择T-clique。当QTS选择限制在第2行和第3行时，则w=2。如图4所示，在ESQ grid Quorum中，相交时隙数为4，而在n×n栅格仲裁中相交时隙数为2。因此，ESQ网格仲裁可以显著提高相交时隙数。

1. 参数设置

网格大小为n×n，n=6。对于常见协议，从n×n=36个时隙中选择的QTS数量为12个，即占空比为1/3；ESQ MAC协议在总时隙数为18的情况下，从w=3行中选择12条QTS，占空比为2/3，说明基于对QTS选择的限制，ESQ协议将占空比提高到以前协议的两倍。

2. 单跳延迟

节点一跳时延是指节点向下一跳发送数据包的时间。根据分析，延时主要包括2个部分：(1)传输延时，是中间节点发生的延时，包括从网络接口接收数据所需的时间，数据传输到网络端口所需的时间，以及数据传输到目的地所需的时间；(2)排队延迟：即转发节点的排队时间。显然，所有转发节点的转发延迟几乎相同，而排队延迟可能有很大的不同。数据节点传输的数据量越大，排队延迟越大。

如图5和6给出了基于ESQ的MAC协议和其他基于Quorum的协议之间的单跳延迟的比较。显然，距离汇点较短的节点延迟较大，是因为需要时隙来传输数据包，数据包的数量越大，所需的时间也就越长。因此，单跳时延表现出很大的变化，在一些极端情况下，节点不需要发送数据包，因此其排队时延为0，在这种情况下，总时延仅包括几乎没有变化的转发时延。

图5. 不同MAC协议下的节点延迟

图6. 不同r下MAC协议的节点延迟

3. E2E延迟

如果网络不阻塞，每一跳产生的时延主要是转发时延，排队时延几乎为零。不同环路的端到端延迟呈线性变化；如图7所示，与基于Quorum的协议相比，ESQ协议可以将端到端延迟从31.08%降低到54.32%，这表明ESQ协议可以显著减少延迟。

 图7. 在不同的λ及没有网络拥塞的情况下网络的端到端延迟

图8. 在不同的λ高负载网络的端到端延迟

排队延迟随着环数的增加而显著增加，如图8所示。E2E延迟主要由排队延迟组成，因此上升非常快，然而，对于那些离sink较远的节点，处理的数据量迅速减少，时延变化缓慢，是因为转发时延主要影响网络时延，因此，ESQ协议仍然可以有效地降低传输延迟。

4. 能源成本与网络寿命

一般来说，ESQ协议可以在不增加延迟的情况下提高网络生存期。在上述实验中，ESQ协议中选择的QTS数量与其他基于Quorum的协议中选择的QTS数量相同。因此ESQ协议的能耗与其他协议相同。但是，它可以减少网络延迟。结果表明，ESQ算法在不增加网络时延的情况下，可以提高网络的生存期。如果其他协议选择的QTS不属于ESQ协议中所选QTS的范围，只要将其删除，数据传输就不会受到影响。这是因为在ESQ协议选择的QTS范围之外没有需要传输的数据包，传输延迟不会受到影响。然而，由于QTS的降低，网络的生存期可以得到改善。如图9显示了ESQ协议与其他协议相比的能耗，从图中可以看出，ESQ协议可以将能耗降低4.23%至48.66%。

图9. 不同λ下的能量消耗

为了提高网络性能，提出了一种基于ESQ (Element Shift Quorum)的MAC协议。在ESQ协议中，QTS的选择是基于节点到sink的距离，节点距离sink越远，分配的QTS时间越早。因此，节点的QTS分配在需要传输数据包的时隙上。这样可以在QTS中成功传输节点的数据包总数，从而降低了传输时延。ESQ方案不仅可以减少传输延迟，而且可以增加网络的生存期。对于原来的n×n仲裁协议，如果选择的QTS较小，网络时延会大于n×n个时隙，在实际应用中是不利的。相反，ESQ可以在不牺牲网络生命周期的情况下显著降低网络时延。因此，ESQ可以适应更广泛的应用。

-END-