一种周期性无线传感器网络的跨层优化模型*

柴 群，吴小平，梁剑波

（凯里学院 信息工程学院，贵州 凯里556011）

一种周期性无线传感器网络的跨层优化模型*

柴 群，吴小平，梁剑波

（凯里学院 信息工程学院，贵州 凯里556011）

基于跨层优化协议，提出了一种跨层优化模型。首先基于跨层优化协议的能量效率树与调度器，根据不同目标建立了三个目标成本函数；然后，为能量效率树与调度器设计了一系列合理的限制条件，并设计了网络数据传输延迟的上、下界来提高最优解的求解速度；最终，利用求解软件获得网络生命期的最优解，同时降低了网络数据传输的延迟。仿真试验结果证明，与原跨层优化协议相比，本算法提高了网络生命期、吞吐量，并降低了传感网络中数据传输的延迟。

周期性无线传感网；跨层优化；目标成本函数；限制条件；最优解

0 引言

由于无线传感网将大量传感器分布于目标区域用来监控目标区域中的可感知状态（温度、高度等）[1]，因此被广泛应用于工业控制[2]、农产品生产[3]及战争[4]等领域。传感节点一般体积较小、成本低廉，传感节点的能量是一个重要资源。

文献[5]针对周期性采集数据的传感器网络提出了一种基于分布式的跨层能效优化协议EEDS。EEDS的核心思想是建立一个能量效率树状结构，树的节点为传感器节点，并建立了相应的TDMA调度器[6]。

本文基于EEDS协议的能量效率树与调度器建立了跨层优化模型。本算法通过设置目标成本函数，并求解其最优解来获得全局最优生命周期，从而提高了原协议的网络生命期，降低了数据传输的延迟。

1 EEDS协议及其模型简介

EEDS的核心思想是建立一个联合路由树状结构及TDMA调度器。EEDS协议将每个时间帧分为若干轮，每轮分为 3个阶段：建立树状结构（BT）、建立调度器（BS）、数据传输（DT）。BT阶段：建立以sink节点为根的树状结构；BS阶段：建立一个分布式 TDMA调度器；DT阶段：将数据从源节点传输至sink节点。每轮中的3个阶段重复多次，如图1所示。

图1 EEDS的帧时序

1.1 建立能量效率树状结构

采用文献[7]的算法建立能效树状结构。首先，初始化sink节点并广播控制信息，控制信息由 4部分组成：状态、深度、父节点、剩余能量值。

设采集数据的节点为 v，typev表示其状态：0表示无效，1表示该节点为叶节点，2表示非叶节点；levelv表示从 v至sink节点的跳数，parentv表示 v至 sink路径上的下一跳；powerv表示节点 v的剩余能量 Ev。每个节点的初始状态设为 0，sink节点的初始广播信息为（2，0，NULL，∞）。

假设节点v（状态为 1）从节点 w收到消息（2，levelw，v，Ew），则当信道空闲时，v将广播消息（2，levelv，parentv，Ev）。以上过程持续进行直至出现叶节点。采用与两个时间，从而防止两个相邻节点同时广播的情况。此外，为了使能量较多的邻居节点早于另一节点发送广播，与应满足使函数Ev单调递减的条件。文献[10]中设，其中 t0表示相邻节点间传输时间的上界，c＞0是一个调节常量。

1.2 建立TDMA调度阶段

基于第一阶段建立的能量效率树，建立TDMA调度器。设TRR、TRT为2个关于节点的时间常量：对于一个节点v，TRRv表示该节点准备好接收其子节点信息的时间间隙长度，TRTv表示该节点准备好向其子节点发送信息的时间间隙。因此节点在时间段[TRRv，TRRv+1]内必须处于唤醒状态。设t′表示时间间隙，在该时间间隙内节点采集数据并向父节点传输数据。然后，因叶节点无子节点，所以叶节点的TRRv无效；对于非叶节点v，可表示为：

2 基于线性规划问题EEDS协议优化模型（LPP）

本文基于EEDS协议建立了新的跨层优化 LPP模型，因此，LPP的限制条件与成本函数必须满足EEDS协议。EEDS协议中建立了一个能效树，本模型的首要目标是最大化网络的生命期，另一个重要目标是最小化延迟。

假设网络中共n个节点（包括sink节点），sink的序号设为 1，设 dij表示节点 i和节点 j之间的距离，1≤i，j≤n，设 R表示节点的单跳传输范围，Ei表示节点 i（1≤i）的剩余能量。

2.1 成本函数

EEDS协议的主要目标是最大化网络生命期，首先建立一个能效树，树中的每个节点选择能量最多的父节点来进行数据传输，从而实现了整体网络生命期的优化。设ECi为节点i从子节点接收数据包所消耗的能量，Ei表示节点i的剩余能量。

应考虑如下因素：

（1）对于剩余能量较高的节点，应最大化其ECi；反之，对于能量低的节点，则最小化其ECi。

（2）Ei高的节点，其子节点应该更多。

综上，应最大化每个节点的ECi×Ei。因此，成本函数则是最大化所有节点 ECi×Ei的总和：

LPP模型另一个目标为最小化延迟，延迟定义为一个数据包到达sink节点所需的总时间。根据 EEDS协议，每个中间节点需将其本轮接收的所有数据均传至其父节点，最终所有数据传至sink节点。将sink节点表示为node-1，为了最小化延迟，node-1的传输时间（t1）必须最小化。因此，第二个目标表示为：

两个目标结合后的目标变为延迟最小的最优能量效率树，目标函数变为：

LPP模型可通过式（4）求解，或者将延迟作为一个限制条件来求解网络生命期的最大值。

2.2 能效树的限制条件

为了表示节点i与节点j之间的父子链接关系，定义二值变量 xij为：

对于两个节点组成的节点对，仅有一个父节点与一个子节点，或者两节点间无关系，因此：

式（6）表示两个节点为父子关系时，xij与 xji中至少有一个为1；两者无关系时为0。

设节点通信范围为R，节点仅可与其通信范围内的节点通信。对于一对节点（i与j），如果距离大于R，则无法建立链接，表示为：

设距离为d的两个节点间发送k比特数据的能耗

为ETx，而接收k比特数据所需能量为 ERx：

其中，Eelec表示芯片的电气能耗，Eamp表示放大器的能耗。

设Num_childi表示节点i的子节点数量，表示为：

从式（13）与式（14）可得如下关系：

设ETi表示节点i向其父节点传输一个数据包所需能量，显然ETi依赖于节点i至父节点p的距离dip。由于节点i仅有一个父节点j，则xij=1且xik=0；其中，k=1，…，n，k≠j。因此：

将式（16）代入式（13）：

节点必须具有足够的能量用来完成与父、子节点的通信，因此，每轮中节点的传输总能耗必须低于其剩余能量：

2.3 TDMA调度器限制条件

引入一个二值变量：在一个时间间隙中，一对节点间是否有数据传输，表示为：

其中，2≤i≤n且1≤j≤n。所有节点传输所需时间间隙总数量最多为n-1，因此1≤l≤n-1，可得以下限制：

设对于时间间隙l，父节点i最多从一个子节点接收数据包。如果在时间间隙l，从子节点k接收数据，则表示为 ykil=1且 yjil=0，其中 j≠k。因此：

EEDS协议定义：一个传输周期中一个节点仅可传输一次数据：

节点i的传输时间（ti）可如下计算：

EEDS协议规定：节点接收到所有子节点数据后再向父节点发送。因此，若k是节点i的子节点，则i比k的传输时间长。增加上述限制：

其中k是i的子节点。

将式（23）代入式（24）：

因此LPP的成本函数为式（2）～（4），限制函数为式（5）～（11）、式（15）、式（18）～（22）、式（25）。

3 仿真试验与结果

3.1 试验环境与试验平台

使用LINGO求解器来求解LPP模型。本实验中，设置LINGO自动选择合适的方案。利用Visual Basic将本算法编程实现并产生可执行程序（驱动程序），驱动调用LINGO求解器来求解。

3.2 参数设置

试验中，设网络进行1 000个周期活动。如果1 000个周期小于 TP，则使用能效树；否则，使用 TP。每轮结束，驱动计算每个节点的剩余能量，将剩余能量为0的节点删除。若该轮数据传输成功，则使用更新的输入参数调用LINGO求解器。

采用不同的网络参数建立多组试验：每组配置中，传感节点在不同维度上随机分布，但所有网络配置中，sink均处于几何中心位置；每组试验测试30个不同的网络结构，每组试验的结果为30次试验的平均值，其置信水平为0.95。采用文献[8]的能量模型，参数设置如下：节点通信范围（R）：15 m；电气能耗（eelec）：50（nJ/bit）；sink的起始能量：100 J；各节点初始化能量：2 J；控制数据包大小：40 B；数据包大小：100 B；放大器能耗：100（pJ/bit/m2）。

试验中比较参数包括：网络生命期、总吞吐量与延迟。生命期设为：从开始直至目标区域的网络覆盖率降至75%的时间。

3.3 试验结果与分析

将EEDS协议的仿真结果与本文模型优化的结果（仅考虑第一个成本函数）进行比较。

第一组试验设为：将10个节点随机分布于大小为50 m×50 m的方形区域，试验结果如图2所示。从图2可看出两个解的变化趋势相仿，但LPP的解优于 EEDS仿真的解。在250 s后，LPP的节点存活数量为 5，而EEDS仿真的结果仅为150 s，即降至5个节点。LPP解比EEDS仿真的解性能提高了66%。

图3所示为LPP解与EEDS仿真的覆盖率的比较，可看出 LPP的覆盖率较优：250 s之后 LPP解的覆盖率降至60%，而仿真在190 s即降至60%。LPP解比EEDS仿真的性能提高了31.5%。

图4所示为网络生命期随网络密度变化的试验结果。可看出两个解的性能接近，生命期均随着网络密度的提高而提高。原因在于：当网络密度较高时，节点间距离较近，从而传输数据消耗的能量也较少。此外，高密度下节点的邻居节点数量也较多，因此，每轮中节点可选择不同的邻居节点进行传输。反之，如果密度较低，每个

节点仅有一个邻居节点，因此该节点消耗较多的能量，导致其能量可能较早耗尽。

从图4中可看出，LPP解的生命期优于 EEDS仿真解，当网络密度为0.025 node/m2时，LPP解的网络生命期为395 s，而EEDS的生命期仅为308 s。LPP解的性能比EEDS仿真提高了28.3%。其原因在于：LPP模型建立的能效树假设网络的全局信息是已知的，在此基础上建立了一个最优树，而EEDS仿真基于局部信息建立，无法获得全局最优解。

图2 存活节点的数量随时间的变化

图3 覆盖率随时间的变化

4 小结

现有的EEDS协议通过建立跨层优化模型提高了网络生命期，本文基于EEDS协议建立了优化模型与目标成本函数，并设计一些合理的限制条件来提高求解速度。试验结果证明，本优化模型进一步提高了EEDS协议的网络生命期性能，并降低了数据传输的延迟。

表2 本文方法与文献[7]方案在计算方面的比较

3 结束语

本文提出了一种基于TPA的审计方案，该方案可利用致盲计算保护用户的隐私，从而改善数据完整性问题。作为一种高效的公共审计方案，本文方案为TPA提供了特权，使其可以同时处理来自于多个用户发出的不同的信息。通过最小化计算密集型操作改进了本文方案的效率，通过对安全性和其他性能的详细分析表明，本文方案是安全和有效的，且支持删除、修改、附加等数据操作。未来将研究为云环境构造完全的动态和安全性方案。参考文献

[1]边根庆，高松，邵必林.面向分散式存储的云存储安全架构[J].西安交通大学学报，2011，45（4）：41-45.

[2]RONG C，NGUYEN S T，JAATUN M G.Beyond lightning：A survey on security challenges in cloud computing[J]. Computers&Electrical Engineering， 2013，39（1）：47-54.

[3]傅颖勋，罗圣美，舒继武.安全云存储系统与关键技术综述[J].计算机研究与发展，2013，50（1）：136-145.

[4]侯清铧，武永卫，郑纬民，等.一种保护云存储平台上用户数据私密性的方法[J].计算机研究与发展，2011，48（7）：1146-1154.

[5]WANG Q，WANG C，REN K，et al.Enabling public auditability and data dynamics for storage security in cloud computing[J]. Parallel and Distributed Systems，IEEE Transactions on，2011，22（5）：847-859.

[6]WANG C，WANG Q，REN K，et al.Privacy-preserving public auditing for data storage security in cloud computing[C]. INFOCOM，2010 Proceedings IEEE.Ieee，2010：1-9.

[7]WANG C，CHOW S S M，WANG Q，et al.Privacy-preserving public auditing for secure cloud storage[J]. Computers，IEEE Transactions on，2013，62（2）：362-375.

[8]KOO D，HUR J，YOON H.Secure and efficient data retrieval over encrypted data using attribute-based encryption in cloud storage[J].Computers&Electrical Engineering，2013，39（1）：34-46.

Cross layer optimization based periodic wireless sensor network model

Chai Qun，Wu Xiaoping，Liang Jianbo
（School of Information Engineering，Kai Li University，Kaili 556011，China）

Based on the cross layer optimization protocol，a new model is proposed.Firstly，based on the energy efficient tree and the schedule program of the protocol，three target cost functions are setup according to the different targets.Then，a series of reasonable constraint are designed for the energy efficient tree and the schedule program，and the constrain conditions for upper bound and lower bound to increase the speed.Lastly，with the solution software，the optimal lifetime is computed and the delay of the data transfer is reduced.Experiments result prove that，compared with the protocol，the proposed model improves the network lifetime and throughput，and reduces the data transfer delay.

periodic wireless sensor network；cross layer optimization；target cost function；constraint condition；optimal solution

TP393.4

A

0258-7998（2015）05-0126-04

10.16157/j.issn.0258-7998.2015.05.031

2015-01-30）

杜朝晖（1969-），女，硕士，讲师，主要研究方向：云存储、信息安全等。

贵州省省校合作计划项目（黔科合 LH字[2014]7230）

王建玺（1981-），女，硕士，讲师，主要研究方向：云存储、信息安全等。