柴 群，吳小平，梁劍波

（凱里學院 信息工程學院，貴州 凱里556011）

一種周期性無線傳感器網絡的跨層優(yōu)化模型*

柴 群，吳小平，梁劍波

（凱里學院 信息工程學院，貴州 凱里556011）

基于跨層優(yōu)化協(xié)議，提出了一種跨層優(yōu)化模型。首先基于跨層優(yōu)化協(xié)議的能量效率樹與調度器，根據不同目標建立了三個目標成本函數(shù)；然后，為能量效率樹與調度器設計了一系列合理的限制條件，并設計了網絡數(shù)據傳輸延遲的上、下界來提高最優(yōu)解的求解速度；最終，利用求解軟件獲得網絡生命期的最優(yōu)解，同時降低了網絡數(shù)據傳輸?shù)难舆t。仿真試驗結果證明，與原跨層優(yōu)化協(xié)議相比，本算法提高了網絡生命期、吞吐量，并降低了傳感網絡中數(shù)據傳輸?shù)难舆t。

周期性無線傳感網；跨層優(yōu)化；目標成本函數(shù)；限制條件；最優(yōu)解

0 引言

由于無線傳感網將大量傳感器分布于目標區(qū)域用來監(jiān)控目標區(qū)域中的可感知狀態(tài)（溫度、高度等）[1]，因此被廣泛應用于工業(yè)控制[2]、農產品生產[3]及戰(zhàn)爭[4]等領域。傳感節(jié)點一般體積較小、成本低廉，傳感節(jié)點的能量是一個重要資源。

文獻[5]針對周期性采集數(shù)據的傳感器網絡提出了一種基于分布式的跨層能效優(yōu)化協(xié)議EEDS。EEDS的核心思想是建立一個能量效率樹狀結構，樹的節(jié)點為傳感器節(jié)點，并建立了相應的TDMA調度器[6]。

本文基于EEDS協(xié)議的能量效率樹與調度器建立了跨層優(yōu)化模型。本算法通過設置目標成本函數(shù)，并求解其最優(yōu)解來獲得全局最優(yōu)生命周期，從而提高了原協(xié)議的網絡生命期，降低了數(shù)據傳輸?shù)难舆t。

1 EEDS協(xié)議及其模型簡介

EEDS的核心思想是建立一個聯(lián)合路由樹狀結構及TDMA調度器。EEDS協(xié)議將每個時間幀分為若干輪，每輪分為 3個階段：建立樹狀結構（BT）、建立調度器（BS）、數(shù)據傳輸（DT）。BT階段：建立以sink節(jié)點為根的樹狀結構；BS階段：建立一個分布式 TDMA調度器；DT階段：將數(shù)據從源節(jié)點傳輸至sink節(jié)點。每輪中的3個階段重復多次，如圖1所示。

圖1 EEDS的幀時序

1.1 建立能量效率樹狀結構

采用文獻[7]的算法建立能效樹狀結構。首先，初始化sink節(jié)點并廣播控制信息，控制信息由 4部分組成：狀態(tài)、深度、父節(jié)點、剩余能量值。

設采集數(shù)據的節(jié)點為 v，typev表示其狀態(tài)：0表示無效，1表示該節(jié)點為葉節(jié)點，2表示非葉節(jié)點；levelv表示從 v至sink節(jié)點的跳數(shù)，parentv表示 v至 sink路徑上的下一跳；powerv表示節(jié)點 v的剩余能量 Ev。每個節(jié)點的初始狀態(tài)設為 0，sink節(jié)點的初始廣播信息為（2，0，NULL，∞）。

假設節(jié)點v（狀態(tài)為 1）從節(jié)點 w收到消息（2，levelw，v，Ew），則當信道空閑時，v將廣播消息（2，levelv，parentv，Ev）。以上過程持續(xù)進行直至出現(xiàn)葉節(jié)點。采用與兩個時間，從而防止兩個相鄰節(jié)點同時廣播的情況。此外，為了使能量較多的鄰居節(jié)點早于另一節(jié)點發(fā)送廣播，與應滿足使函數(shù)Ev單調遞減的條件。文獻[10]中設，其中 t0表示相鄰節(jié)點間傳輸時間的上界，c＞0是一個調節(jié)常量。

1.2 建立TDMA調度階段

基于第一階段建立的能量效率樹，建立TDMA調度器。設TRR、TRT為2個關于節(jié)點的時間常量：對于一個節(jié)點v，TRRv表示該節(jié)點準備好接收其子節(jié)點信息的時間間隙長度，TRTv表示該節(jié)點準備好向其子節(jié)點發(fā)送信息的時間間隙。因此節(jié)點在時間段[TRRv，TRRv+1]內必須處于喚醒狀態(tài)。設t′表示時間間隙，在該時間間隙內節(jié)點采集數(shù)據并向父節(jié)點傳輸數(shù)據。然后，因葉節(jié)點無子節(jié)點，所以葉節(jié)點的TRRv無效；對于非葉節(jié)點v，可表示為：

2 基于線性規(guī)劃問題EEDS協(xié)議優(yōu)化模型（LPP）

本文基于EEDS協(xié)議建立了新的跨層優(yōu)化 LPP模型，因此，LPP的限制條件與成本函數(shù)必須滿足EEDS協(xié)議。EEDS協(xié)議中建立了一個能效樹，本模型的首要目標是最大化網絡的生命期，另一個重要目標是最小化延遲。

假設網絡中共n個節(jié)點（包括sink節(jié)點），sink的序號設為 1，設 dij表示節(jié)點 i和節(jié)點 j之間的距離，1≤i，j≤n，設 R表示節(jié)點的單跳傳輸范圍，Ei表示節(jié)點 i（1≤i）的剩余能量。

2.1 成本函數(shù)

EEDS協(xié)議的主要目標是最大化網絡生命期，首先建立一個能效樹，樹中的每個節(jié)點選擇能量最多的父節(jié)點來進行數(shù)據傳輸，從而實現(xiàn)了整體網絡生命期的優(yōu)化。設ECi為節(jié)點i從子節(jié)點接收數(shù)據包所消耗的能量，Ei表示節(jié)點i的剩余能量。

應考慮如下因素：

（1）對于剩余能量較高的節(jié)點，應最大化其ECi；反之，對于能量低的節(jié)點，則最小化其ECi。

（2）Ei高的節(jié)點，其子節(jié)點應該更多。

綜上，應最大化每個節(jié)點的ECi×Ei。因此，成本函數(shù)則是最大化所有節(jié)點 ECi×Ei的總和：

LPP模型另一個目標為最小化延遲，延遲定義為一個數(shù)據包到達sink節(jié)點所需的總時間。根據 EEDS協(xié)議，每個中間節(jié)點需將其本輪接收的所有數(shù)據均傳至其父節(jié)點，最終所有數(shù)據傳至sink節(jié)點。將sink節(jié)點表示為node-1，為了最小化延遲，node-1的傳輸時間（t1）必須最小化。因此，第二個目標表示為：

兩個目標結合后的目標變?yōu)檠舆t最小的最優(yōu)能量效率樹，目標函數(shù)變?yōu)椋?/p>

LPP模型可通過式（4）求解，或者將延遲作為一個限制條件來求解網絡生命期的最大值。

2.2 能效樹的限制條件

為了表示節(jié)點i與節(jié)點j之間的父子鏈接關系，定義二值變量 xij為：

對于兩個節(jié)點組成的節(jié)點對，僅有一個父節(jié)點與一個子節(jié)點，或者兩節(jié)點間無關系，因此：

式（6）表示兩個節(jié)點為父子關系時，xij與 xji中至少有一個為1；兩者無關系時為0。

設節(jié)點通信范圍為R，節(jié)點僅可與其通信范圍內的節(jié)點通信。對于一對節(jié)點（i與j），如果距離大于R，則無法建立鏈接，表示為：

設距離為d的兩個節(jié)點間發(fā)送k比特數(shù)據的能耗

為ETx，而接收k比特數(shù)據所需能量為 ERx：

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

設Num_childi表示節(jié)點i的子節(jié)點數(shù)量，表示為：

從式（13）與式（14）可得如下關系：

設ETi表示節(jié)點i向其父節(jié)點傳輸一個數(shù)據包所需能量，顯然ETi依賴于節(jié)點i至父節(jié)點p的距離dip。由于節(jié)點i僅有一個父節(jié)點j，則xij=1且xik=0；其中，k=1，…，n，k≠j。因此：

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

節(jié)點必須具有足夠的能量用來完成與父、子節(jié)點的通信，因此，每輪中節(jié)點的傳輸總能耗必須低于其剩余能量：

2.3 TDMA調度器限制條件

引入一個二值變量：在一個時間間隙中，一對節(jié)點間是否有數(shù)據傳輸，表示為：

其中，2≤i≤n且1≤j≤n。所有節(jié)點傳輸所需時間間隙總數(shù)量最多為n-1，因此1≤l≤n-1，可得以下限制：

設對于時間間隙l，父節(jié)點i最多從一個子節(jié)點接收數(shù)據包。如果在時間間隙l，從子節(jié)點k接收數(shù)據，則表示為 ykil=1且 yjil=0，其中 j≠k。因此：

EEDS協(xié)議定義：一個傳輸周期中一個節(jié)點僅可傳輸一次數(shù)據：

節(jié)點i的傳輸時間（ti）可如下計算：

EEDS協(xié)議規(guī)定：節(jié)點接收到所有子節(jié)點數(shù)據后再向父節(jié)點發(fā)送。因此，若k是節(jié)點i的子節(jié)點，則i比k的傳輸時間長。增加上述限制：

其中k是i的子節(jié)點。

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

因此LPP的成本函數(shù)為式（2）～（4），限制函數(shù)為式（5）～（11）、式（15）、式（18）～（22）、式（25）。

3 仿真試驗與結果

3.1 試驗環(huán)境與試驗平臺

使用LINGO求解器來求解LPP模型。本實驗中，設置LINGO自動選擇合適的方案。利用Visual Basic將本算法編程實現(xiàn)并產生可執(zhí)行程序（驅動程序），驅動調用LINGO求解器來求解。

3.2 參數(shù)設置

試驗中，設網絡進行1 000個周期活動。如果1 000個周期小于 TP，則使用能效樹；否則，使用 TP。每輪結束，驅動計算每個節(jié)點的剩余能量，將剩余能量為0的節(jié)點刪除。若該輪數(shù)據傳輸成功，則使用更新的輸入參數(shù)調用LINGO求解器。

采用不同的網絡參數(shù)建立多組試驗：每組配置中，傳感節(jié)點在不同維度上隨機分布，但所有網絡配置中，sink均處于幾何中心位置；每組試驗測試30個不同的網絡結構，每組試驗的結果為30次試驗的平均值，其置信水平為0.95。采用文獻[8]的能量模型，參數(shù)設置如下：節(jié)點通信范圍（R）：15 m；電氣能耗（eelec）：50（nJ/bit）；sink的起始能量：100 J；各節(jié)點初始化能量：2 J；控制數(shù)據包大?。?0 B；數(shù)據包大?。?00 B；放大器能耗：100（pJ/bit/m2）。

試驗中比較參數(shù)包括：網絡生命期、總吞吐量與延遲。生命期設為：從開始直至目標區(qū)域的網絡覆蓋率降至75%的時間。

3.3 試驗結果與分析

將EEDS協(xié)議的仿真結果與本文模型優(yōu)化的結果（僅考慮第一個成本函數(shù)）進行比較。

第一組試驗設為：將10個節(jié)點隨機分布于大小為50 m×50 m的方形區(qū)域，試驗結果如圖2所示。從圖2可看出兩個解的變化趨勢相仿，但LPP的解優(yōu)于 EEDS仿真的解。在250 s后，LPP的節(jié)點存活數(shù)量為 5，而EEDS仿真的結果僅為150 s，即降至5個節(jié)點。LPP解比EEDS仿真的解性能提高了66%。

圖3所示為LPP解與EEDS仿真的覆蓋率的比較，可看出 LPP的覆蓋率較優(yōu)：250 s之后 LPP解的覆蓋率降至60%，而仿真在190 s即降至60%。LPP解比EEDS仿真的性能提高了31.5%。

圖4所示為網絡生命期隨網絡密度變化的試驗結果?？煽闯鰞蓚€解的性能接近，生命期均隨著網絡密度的提高而提高。原因在于：當網絡密度較高時，節(jié)點間距離較近，從而傳輸數(shù)據消耗的能量也較少。此外，高密度下節(jié)點的鄰居節(jié)點數(shù)量也較多，因此，每輪中節(jié)點可選擇不同的鄰居節(jié)點進行傳輸。反之，如果密度較低，每個

節(jié)點僅有一個鄰居節(jié)點，因此該節(jié)點消耗較多的能量，導致其能量可能較早耗盡。

從圖4中可看出，LPP解的生命期優(yōu)于 EEDS仿真解，當網絡密度為0.025 node/m2時，LPP解的網絡生命期為395 s，而EEDS的生命期僅為308 s。LPP解的性能比EEDS仿真提高了28.3%。其原因在于：LPP模型建立的能效樹假設網絡的全局信息是已知的，在此基礎上建立了一個最優(yōu)樹，而EEDS仿真基于局部信息建立，無法獲得全局最優(yōu)解。

圖2 存活節(jié)點的數(shù)量隨時間的變化

圖3 覆蓋率隨時間的變化

4 小結

現(xiàn)有的EEDS協(xié)議通過建立跨層優(yōu)化模型提高了網絡生命期，本文基于EEDS協(xié)議建立了優(yōu)化模型與目標成本函數(shù)，并設計一些合理的限制條件來提高求解速度。試驗結果證明，本優(yōu)化模型進一步提高了EEDS協(xié)議的網絡生命期性能，并降低了數(shù)據傳輸?shù)难舆t。

表2 本文方法與文獻[7]方案在計算方面的比較

3 結束語

本文提出了一種基于TPA的審計方案，該方案可利用致盲計算保護用戶的隱私，從而改善數(shù)據完整性問題。作為一種高效的公共審計方案，本文方案為TPA提供了特權，使其可以同時處理來自于多個用戶發(fā)出的不同的信息。通過最小化計算密集型操作改進了本文方案的效率，通過對安全性和其他性能的詳細分析表明，本文方案是安全和有效的，且支持刪除、修改、附加等數(shù)據操作。未來將研究為云環(huán)境構造完全的動態(tài)和安全性方案。參考文獻

[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]傅穎勛，羅圣美，舒繼武.安全云存儲系統(tǒng)與關鍵技術綜述[J].計算機研究與發(fā)展，2013，50（1）：136-145.

[4]侯清鏵，武永衛(wèi)，鄭緯民，等.一種保護云存儲平臺上用戶數(shù)據私密性的方法[J].計算機研究與發(fā)展，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-），女，碩士，講師，主要研究方向：云存儲、信息安全等。