馬曉輝，趙可欣，孫 超，崔凌云

(1.河北水利電力學(xué)院 計(jì)算機(jī)系，河北 滄州 061001;2.河北水利電力學(xué)院 教務(wù)處，河北 滄州 061001)

0 引 言

由于無(wú)線傳感網(wǎng)絡(luò)(wireless sensor networks，WSN)[1-3]是開放的無(wú)線環(huán)境，一些惡意節(jié)點(diǎn)攻擊、破壞節(jié)點(diǎn)間的數(shù)據(jù)傳輸，即存在鏈路不存在問(wèn)題。然而，由于WSN內(nèi)的傳感節(jié)點(diǎn)數(shù)量巨大，并且節(jié)點(diǎn)容量受限，不可能每條鏈路的一對(duì)節(jié)點(diǎn)間建立加密安全系統(tǒng)，只能對(duì)部分鏈路加密，這就形成了不完備安全鏈路ISC(incomplete secure connectivity)問(wèn)題。

目前，已有不少研究人員關(guān)注了不完備安全鏈路問(wèn)題[4-7]。如文獻(xiàn)[4]討論了ISC環(huán)境下的吞吐量，文獻(xiàn)[5]分析了適用于ISC環(huán)境下的成對(duì)密鑰分布的類型。然而，目前還沒(méi)有文獻(xiàn)分析ISC環(huán)境下的網(wǎng)絡(luò)壽命問(wèn)題。盡管有文獻(xiàn)討論了由于不安全鏈路導(dǎo)致無(wú)法基于最優(yōu)路由向基站傳輸數(shù)據(jù)消耗能量成本的問(wèn)題，但是它們并沒(méi)有直接關(guān)注網(wǎng)絡(luò)壽命，同時(shí)，它們只是理論分析了能量成本，并沒(méi)有定量計(jì)算。

網(wǎng)絡(luò)壽命是無(wú)線傳感網(wǎng)絡(luò)的重要性能，因此，它是本文的分析對(duì)象。據(jù)此，提出基于線性規(guī)劃的量化網(wǎng)絡(luò)壽命的分析模型LPQNL(linear programming-based quantifies network lifetime of wireless sensor network analyzed model)。基于傳感節(jié)點(diǎn)間的不完備安全鏈路的事實(shí)，即只允許部分節(jié)點(diǎn)分享密鑰，形成對(duì)稱加密，LPQNL模型討論ISC對(duì)網(wǎng)絡(luò)壽命的影響。為了準(zhǔn)確地估算能量消耗，采用對(duì)數(shù)正態(tài)衰落傳播模型。LPQNL模型主要分析在滿足網(wǎng)絡(luò)壽命的條件下，所需節(jié)點(diǎn)密鑰共享概率的最小值。同時(shí)，分析密鑰共享概率值對(duì)網(wǎng)絡(luò)壽命的影響，并進(jìn)行量化。此外，分析了密鑰共享概率對(duì)路徑長(zhǎng)度、隊(duì)列尺寸以及能量消耗的影響。

1 預(yù)備知識(shí)

1.1 網(wǎng) 絡(luò)

用有向圖G=(V,A)表示無(wú)線網(wǎng)絡(luò)拓?fù)洌渲蠽表示所有傳感節(jié)點(diǎn)集，包括基站(BS)。用W表示除基站外的所有傳感節(jié)點(diǎn)集，即W=V{BS}。而A表示兩個(gè)節(jié)點(diǎn)間的鏈接，即A={(i,j):i∈W,j∈V-i}，其中i,j表示節(jié)點(diǎn)ID號(hào)。

1.2 密鑰共享概率

考慮文獻(xiàn)[5]的密鑰池方案，假定信任中心提供具有P個(gè)密鑰池，傳感節(jié)點(diǎn)可從中隨機(jī)選擇k個(gè)不同的密鑰。密鑰池通常由217至220個(gè)密鑰。兩個(gè)節(jié)點(diǎn)的密鑰共享概率Psharing

(1)

若兩個(gè)節(jié)點(diǎn)至少共享一個(gè)密鑰，則兩節(jié)點(diǎn)便形成了通信連接，可以將所感測(cè)的數(shù)據(jù)轉(zhuǎn)發(fā)至基站。例如，當(dāng)Psharing為0.5、P=220時(shí)，則k=853。若使用AES-128的加密算法，每個(gè)加密密鑰需要16B的內(nèi)存。因此，相應(yīng)的存儲(chǔ)空間約為14kB。在典型的WSN的網(wǎng)絡(luò)內(nèi)，節(jié)點(diǎn)通常有512kB的內(nèi)存容量，只需占用3%的內(nèi)存用于安全加密，這是可行的。

1.3 無(wú)線傳播能量消耗

(2)

其中，ρ表示傳感節(jié)點(diǎn)的電子電路所消耗的能量、ε表示發(fā)射機(jī)效率。Tb為一比特所持續(xù)的時(shí)間、η表示最小能量等級(jí)。

相應(yīng)地，接收M字節(jié)的數(shù)據(jù)所消耗的能量Erx,ij

Erx=8×M×ρ

(3)

(4)

(5)

(6)

2 基于線性規(guī)劃LP(linear programming)的量化網(wǎng)絡(luò)的分析模型

本節(jié)著重討論提出的分析模型，包括最大化網(wǎng)絡(luò)壽命和最小化能量消耗，旨在分析密碼共享概率對(duì)網(wǎng)絡(luò)壽命的影響。

首先明確網(wǎng)絡(luò)壽命的定義。引用文獻(xiàn)[10]給出的定義，其已被廣泛采用。假定網(wǎng)絡(luò)在初始時(shí)刻tstart內(nèi)部署了W個(gè)傳感節(jié)點(diǎn)，在時(shí)刻tend時(shí)第一個(gè)節(jié)點(diǎn)的能量消耗殆盡，那么該網(wǎng)絡(luò)壽命Tlife

Tlife=tend-tstart

(7)

從式(7)可以看出，網(wǎng)絡(luò)壽命取決于第一個(gè)節(jié)點(diǎn)能量消耗殆盡的時(shí)間。為了最大化網(wǎng)絡(luò)壽命，應(yīng)當(dāng)平衡網(wǎng)絡(luò)內(nèi)能量消耗，使得多數(shù)節(jié)點(diǎn)能量消耗速度相近，避免某單一節(jié)點(diǎn)因能量過(guò)早殆盡，縮短了網(wǎng)絡(luò)壽命。換而言之，所有節(jié)點(diǎn)以平衡方式消耗能量。此外，網(wǎng)絡(luò)壽命還與消息傳輸模式相關(guān)。若一些節(jié)點(diǎn)不在彼此通信范圍內(nèi)，整個(gè)網(wǎng)絡(luò)就被分割。因此，在最大化網(wǎng)絡(luò)壽命時(shí)，應(yīng)盡可能考慮網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)的行為，即是整個(gè)網(wǎng)絡(luò)特征決定了網(wǎng)絡(luò)壽命，而不是部分節(jié)點(diǎn)的特性。

將網(wǎng)絡(luò)執(zhí)行時(shí)間劃分等間隔的輪(round)，每輪時(shí)長(zhǎng)Trnd=100 s。在每一輪，每個(gè)節(jié)點(diǎn)接收數(shù)據(jù)所消耗的能量為EDA=600 μJ，并產(chǎn)生MD=230字節(jié)的數(shù)據(jù)。數(shù)據(jù)包由MH=25字節(jié)的開銷和MD=230字節(jié)的數(shù)據(jù)組成。因此整個(gè)數(shù)據(jù)包長(zhǎng)度MP=MP+MD=255字節(jié)。

假定從節(jié)點(diǎn)i流向節(jié)點(diǎn)j的數(shù)據(jù)包數(shù)量表示為fij。每個(gè)節(jié)點(diǎn)均產(chǎn)生相同的數(shù)據(jù)流si=MP，并向基站傳輸?；贚P的最大化網(wǎng)絡(luò)壽命的目標(biāo)函數(shù)以及約束條件如式(8)～式(14)所示。式(8)限定了數(shù)據(jù)流為非負(fù)數(shù)。而式(7)對(duì)數(shù)據(jù)流平衡進(jìn)行了約束：除了基站外，其它任意節(jié)點(diǎn)(節(jié)點(diǎn)i)，流出的數(shù)據(jù)流和流入的數(shù)據(jù)流的差等于該節(jié)點(diǎn)所產(chǎn)生的總數(shù)據(jù)。

MaximizeTlife

subjectto

fij≥0, ?(i,j)∈A

(8)

(9)

(10)

ei=ξ?i∈W

(11)

(12)

(13)

(14)

此外，所有節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)均需要傳輸至基站。式(10)對(duì)能量進(jìn)行限制。一個(gè)節(jié)點(diǎn)所消耗的總體能量由接收數(shù)據(jù)包消耗的能量、傳輸數(shù)據(jù)包所消耗的能量、因數(shù)據(jù)包丟失所產(chǎn)生的重傳所消耗的能量、數(shù)據(jù)收集和處理所消耗的能量組成。式(10)表明，所消耗的能量不大于節(jié)點(diǎn)的初始能量ei。式(11)規(guī)定了每個(gè)節(jié)點(diǎn)的初始能量均為ξ。

盡管最大化網(wǎng)絡(luò)壽命是無(wú)線傳感網(wǎng)絡(luò)的根本目的，但是分析平均路徑長(zhǎng)度、平均隊(duì)列尺寸以及平均能量消耗率也是非常重要的。因此，對(duì)式(10)和式(11)進(jìn)行了修改。網(wǎng)絡(luò)內(nèi)總體能量消耗Etot，定義如式(15)所示

(15)

3 性能分析

為了更好地分析密碼共享概率對(duì)網(wǎng)絡(luò)壽命的影響，利用MATLAB構(gòu)建網(wǎng)絡(luò)拓?fù)浜屯ㄓ么鷶?shù)建模系統(tǒng)GAMS(generalalgebraicmodelingsystem)。考慮圓形的拓?fù)浣Y(jié)構(gòu)，基站位于圓形中心。W=300個(gè)傳感節(jié)點(diǎn)在區(qū)域S內(nèi)均勻分布[12-15]。區(qū)域S的面積越大，表示節(jié)點(diǎn)密度越小。每次實(shí)驗(yàn)仿真獨(dú)立重復(fù)100次，取平均值作為最終的數(shù)據(jù)。

仿真參數(shù)見(jiàn)表1。在仿真過(guò)程中，主要考查共享密碼概率Psharing和區(qū)域S的面積對(duì)網(wǎng)絡(luò)壽命、隊(duì)列尺寸的變化、路徑長(zhǎng)度以及能量消耗的影響，其中Psharing從0.05至1.0變化，區(qū)域S分別為300m2、400m2和500m2。

表1 仿真參數(shù)

(1)網(wǎng)絡(luò)壽命下降率

提出的模型的根本目的在于最大化網(wǎng)絡(luò)壽命Tlife。當(dāng)密碼共享概率Psharing=1，對(duì)流量沒(méi)有限制時(shí)，能獲得最大的網(wǎng)絡(luò)壽命。因此，以Psharing=1得到網(wǎng)絡(luò)壽命T為基準(zhǔn)，而Psharing<1時(shí)的網(wǎng)絡(luò)壽命一定小于T。仿真結(jié)果如圖1所示。縱坐標(biāo)表示Psharing<1的網(wǎng)絡(luò)壽命比T的下降率。

從圖1可知，隨著密碼共享概率Psharing的增加，網(wǎng)絡(luò)壽命下降率下降。原因在于：Psharing越大，表明網(wǎng)絡(luò)內(nèi)提供的鏈路數(shù)越多，找到最優(yōu)路由的概率就越大。相應(yīng)地，數(shù)據(jù)傳輸效率就越高，越多節(jié)省能量。此外，注意到圖1，Psharing從0.05變化到1.0的過(guò)程中，網(wǎng)絡(luò)壽命下降率先有激烈變化，后緩慢。在Psharing從0.05變化至0.2時(shí)，網(wǎng)絡(luò)壽命下降率快，而當(dāng)Psharing從0.2變化至1.0時(shí)，網(wǎng)絡(luò)壽命下降率變化相當(dāng)緩慢。這些數(shù)據(jù)表明，當(dāng)Psharing達(dá)到某值后，維持所有鏈路的安全是沒(méi)有必要的。例如，在S=300時(shí)，當(dāng)Psharing=0.2時(shí)，網(wǎng)絡(luò)下降率為2.48%，而Psharing=0.3時(shí)，網(wǎng)絡(luò)壽命下降率為1.439%。

此外，網(wǎng)絡(luò)密度對(duì)網(wǎng)絡(luò)壽命的影響較小。在Psharing=0.1時(shí)，S=300、400以及500時(shí)的網(wǎng)絡(luò)壽命下降率分別為33.2%、46.2%和55.9%。在Psharing=0.5時(shí)，S=300、400以及500時(shí)的網(wǎng)絡(luò)壽命下降率分別為0.7%、1.0%和1.2%。面積越大，網(wǎng)絡(luò)壽命下降率呈上升趨勢(shì)。原因在于：網(wǎng)絡(luò)密度越高，參與數(shù)據(jù)傳輸?shù)墓?jié)點(diǎn)越多，能量消耗相對(duì)多。

(2)隊(duì)列尺寸增加百分率

類似地，以Psharing=1的隊(duì)列尺寸為基準(zhǔn)，分析Psharing從0.05至1.0變化時(shí)，隊(duì)列尺寸的增加變化率，結(jié)果如圖2所示。從圖2可知，隊(duì)列尺寸增加百分率隨Psharing的增加而下降，同時(shí)，區(qū)域面積的增加也加大了隊(duì)列尺寸的增加速度。例如，當(dāng)Psharing=0.4時(shí)，S=300、400和500的隊(duì)列尺寸增加百分率分別為5%、6.4%和9.0%。

圖2 隊(duì)列尺寸增加百分率

(3)路徑長(zhǎng)度增加百分比

仍以Psharing=1的路徑長(zhǎng)度為基準(zhǔn)，分析Psharing從0.05至1.0變化時(shí)，路徑長(zhǎng)度增加百分率，結(jié)果如圖3所示。從圖3可知，路徑長(zhǎng)度增加百分率隨Psharing的增加而下降，但是在Psharing從0.05至1.0變化時(shí)整個(gè)過(guò)程中，路徑長(zhǎng)度增加百分比小于10%。同時(shí)，區(qū)域面積的增加也加大了路徑長(zhǎng)度寸的增加速度。例如，當(dāng)Psharing=0.5時(shí)，S=300、400和500的隊(duì)列尺寸增加百分率分別為2.8%、3.52%和4.2%。

圖3 路徑長(zhǎng)度增加百分比

(4)能量消耗增加的百分比

最后，分析能量消耗增加速度。仍以Psharing=1的能量消耗為基準(zhǔn)，分析Psharing從0.05至1.0變化時(shí)，能量消耗增加的百分比，結(jié)果如圖4所示。從圖4可知，Psharing的增加，降低了能量消耗的增加速度，這與圖1的數(shù)據(jù)相吻合。Psharing的增加，提高了路由選擇的機(jī)會(huì)，增加了選擇最優(yōu)路由的概率，進(jìn)而降低了能量消耗。

圖4 能量消耗增加的百分比

4 結(jié)束語(yǔ)

針對(duì)無(wú)線傳感網(wǎng)絡(luò)的不完備的安全鏈接環(huán)境，提出了基于線性規(guī)劃LP的量化網(wǎng)絡(luò)的分析模型LPQNL。LPQNL量化密度共享概率對(duì)網(wǎng)絡(luò)壽命的影響，同時(shí)分析了密度共享概率對(duì)隊(duì)列尺寸、路徑長(zhǎng)度以及能量消耗的影響。仿真結(jié)果表明，當(dāng)密碼共享概率大于0.3后，網(wǎng)絡(luò)壽命受密碼共享概率的影響微小，這一結(jié)果有利于設(shè)計(jì)無(wú)線傳感網(wǎng)絡(luò)的密鑰分布方案。

[1]SHENYanxia,XUEXiaosong.PathoptimizationstrategyofWSNsmobilebeaconnodes[J].TransducerandMicrosystemTechnologies,2012,31(12):42-46(inChinese).[沈艷霞,薛小松.無(wú)線傳感網(wǎng)絡(luò)移動(dòng)信標(biāo)節(jié)點(diǎn)路徑優(yōu)化策略[J].傳感器與微系統(tǒng),2012,31(12):42-46.]

[2]GUIYihong.ResearchonHEDSAdataaggregationofwirelesssensornetwork[J].ComputerEngineering,2011,37(7):160-164(inChinese).[歸奕紅.無(wú)線傳感器網(wǎng)絡(luò)HEDSA數(shù)據(jù)聚合研究[J].計(jì)算機(jī)工程,2011,37(7):160-164.]

[3]TaghikhakiZ,MeratniaN,HavingaPJM.Atrust-basedprobabilisticcoveragealgorithmforwirelesssensornetworks[J].ProcediaComput,2013,21(5):455-464.

[4]KoyluogluO,KoksalC,GamalH.Onsecrecycapacitysca-linginwirelessnetworks[J].IEEETransInfTheory,2012,58(5):3000-3015.

[5]EschenauerL,GligorVD.Akey-managementschemefordistributedsensornetworks[C]//ProcACMConfComputCommunSecur,2012:41-47.

[6]ChanH,PerrigA,SongD.Randomkeypredistributionschemesforsensornetworks[J].ProcIEEESympSecurPrivacy,2013,10(9):197-213.

[7]DuW,DengJ,HanY,etal.Akeymanagementschemeforwirelesssensornetworksusingdeploymentknowledge[C]//ProcIEEEIntConfComputCommun,2014:586-597.

[8]CotukH,BicakciK,TavliB,etal.Theimpactoftransmissionpowercontrolstrategiesonlifetimeofwirelesssensornetworks[J].IEEETransComput,2014,99(11):2866-2879.

[9]ZunigaM,KrishnamachariB.Analyzingthetransitionalregioninlowpowerwirelesslinks[C]//ProcSensorMeshAdHocCommunNetw,2014:517-526.

[10]ChengZ,PerilloM,HeinzelmanW.Generalnetworklifetimeandcostmodelsforevaluatingsensornetworkdeploymentstrategies[J].IEEETransMobileComput,2013,7(4):484-497.

[11]ChengM,GongX,CaiL.Jointroutingandlinkrateallocationunderbandwidthandenergyconstraintsinsensornetworks[J].IEEETransWirelessCommun,2014,8(7):3770-3779.

[12]SpechtE.ThebestknownpackingsofequalcirclesintheUnitCircle[EB/OL].http://hydra.nat.uni-magdeburg.de/packing/,2016.

[13]ZhangJ,HongP,XueH,etal.Anovelpowercontrolschemeforfemtocellinheterogeneousnetworks[C]//IEEEConsumerCommunicationsandNetworkingConference,2012:802-806.

[14]PalanisamyP,NirmalaS.Downlinkinterferencemanagementinfemtocellnetworks-acomprehensivestudyandsurvey[C]//InternationalConferenceonInformationCommunicationandEmbeddedSystems,2013:747-754.

[15]MustaphaB,HafldA,MichelG.Source-basedroutinginwirelessmeshnetworks[J].IEEESystemsJournal,2016,10(1):262-271.