何 莉，李 博

(河南工程學(xué)院 計(jì)算機(jī)學(xué)院,河南 鄭州 451191)

物聯(lián)網(wǎng)節(jié)點(diǎn)需求量計(jì)算方法

何 莉，李 博

(河南工程學(xué)院 計(jì)算機(jī)學(xué)院,河南 鄭州 451191)

物聯(lián)網(wǎng)節(jié)點(diǎn)覆蓋的全面性和連通性直接關(guān)系著對(duì)物理空間監(jiān)控的有效性.當(dāng)前，人們對(duì)二維空間覆蓋問(wèn)題研究得較多，但隨著物聯(lián)網(wǎng)應(yīng)用領(lǐng)域向空中和水下延伸，三維空間節(jié)點(diǎn)覆蓋問(wèn)題亟待解決.現(xiàn)有的三維空間k-覆蓋問(wèn)題的解決方法通常是1-覆蓋問(wèn)題解決方案的簡(jiǎn)單擴(kuò)展，存在一定的局限.在總結(jié)現(xiàn)有研究結(jié)果的基礎(chǔ)上，提出了一種新的三維空間k-覆蓋節(jié)點(diǎn)數(shù)量快速計(jì)算方法，利用指數(shù)增長(zhǎng)方法快速確定節(jié)點(diǎn)需求量的充分值，然后利用分治策略快速定位節(jié)點(diǎn)需求量的必要值，實(shí)驗(yàn)結(jié)果證明新方法具有較強(qiáng)的適應(yīng)性且更加貼合實(shí)際.

k-覆蓋; 分治策略；三維空間覆蓋問(wèn)題

物聯(lián)網(wǎng)被譽(yù)為繼計(jì)算機(jī)和Internet之后世界信息產(chǎn)業(yè)發(fā)展的第三次浪潮.物聯(lián)網(wǎng)從物理世界獲取信號(hào)，經(jīng)信息系統(tǒng)處理后，反作用于物理系統(tǒng).物聯(lián)網(wǎng)信息系統(tǒng)工作的有效性取決于物理信息獲取的全面性.因此，要有效監(jiān)控物理空間，就要先解決物聯(lián)網(wǎng)節(jié)點(diǎn)的覆蓋問(wèn)題，這是物聯(lián)網(wǎng)研究與應(yīng)用的基礎(chǔ).

物聯(lián)網(wǎng)二維空間覆蓋問(wèn)題的研究成果[1]較多.隨著物聯(lián)網(wǎng)在空中和水域的應(yīng)用，三維空間的覆蓋問(wèn)題逐漸成為研究熱點(diǎn).三維空間覆蓋問(wèn)題的復(fù)雜度遠(yuǎn)高于二維空間，不能簡(jiǎn)單地從二維空間的研究成果推廣應(yīng)用于三維空間.三維空間的覆蓋問(wèn)題分為1-覆蓋和k-覆蓋問(wèn)題，1-覆蓋問(wèn)題可以看作k-覆蓋問(wèn)題的特例，即k=1時(shí)的情況.現(xiàn)有研究分別從子空間劃分和節(jié)點(diǎn)部署最低密度的角度嘗試解決1-覆蓋問(wèn)題，并從空間角度將1-覆蓋問(wèn)題的研究成果推廣到k-覆蓋問(wèn)題[2].子空間劃分的基本思想是在節(jié)點(diǎn)的通信距離與探測(cè)距離比率確定的情況下，選取合適的三維立體空間結(jié)構(gòu)為基本單元，無(wú)縫填充覆蓋目標(biāo)，節(jié)點(diǎn)部署在每個(gè)基本單元的幾何中心.對(duì)于1-覆蓋，通常在每個(gè)單元放置1個(gè)節(jié)點(diǎn)；對(duì)于k-覆蓋，每個(gè)單元放置k個(gè)節(jié)點(diǎn).為滿足活動(dòng)節(jié)點(diǎn)需求量最少且保證節(jié)點(diǎn)連通性的條件，感知距離至少是通信距離的0.542 326倍.當(dāng)節(jié)點(diǎn)的通信距離和探測(cè)距離的比率不同時(shí)，選取不同的多面體滿足1-覆蓋三維空間[3].節(jié)點(diǎn)最低密度求解方法的基本思想是對(duì)于給定空間中的任何一個(gè)點(diǎn)，要滿足1-覆蓋或k-覆蓋條件，確定在空間中需要部署的節(jié)點(diǎn)的最低密度[4].

現(xiàn)有研究存在的待改進(jìn)之處：①對(duì)于子空間劃分方法，k-覆蓋問(wèn)題的解決方法是在1-覆蓋基本單元幾何中心放置k個(gè)節(jié)點(diǎn)，在理論上是可行的，但考慮到節(jié)點(diǎn)本身需要占據(jù)一定的空間及從安全角度來(lái)說(shuō)，多個(gè)節(jié)點(diǎn)并不適合于集中放置，所以在實(shí)際部署時(shí)這種方法存在不合理之處；②現(xiàn)有方法側(cè)重于覆蓋率，通常假設(shè)節(jié)點(diǎn)探測(cè)距離與通信距離滿足一定的約束條件時(shí)節(jié)點(diǎn)的連通性得到滿足，當(dāng)約束條件改變時(shí)，需要復(fù)雜的計(jì)算才能獲得節(jié)點(diǎn)的需求量.

基于以上不足，課題組提出了一種新穎的節(jié)點(diǎn)需求量計(jì)算方法以解決物聯(lián)網(wǎng)空間k-覆蓋問(wèn)題.給定節(jié)點(diǎn)探測(cè)距離r，新方法能夠計(jì)算通信距離d和k取不同值時(shí)節(jié)點(diǎn)的需求量.

1 相關(guān)假設(shè)與定義

首先，對(duì)物聯(lián)網(wǎng)進(jìn)行必要的假設(shè)和定義.

為了便于研究三維空間的覆蓋問(wèn)題，將連續(xù)空間覆蓋問(wèn)題轉(zhuǎn)化為離散空間覆蓋問(wèn)題.具體步驟為在三維空間S的3個(gè)方向X，Y，Z分別進(jìn)行等間隔劃分，等分線交叉形成的點(diǎn)構(gòu)成集合Ω，點(diǎn)的數(shù)量用‖Ω‖表示，每個(gè)點(diǎn)i的空間坐標(biāo)用Loc(i)=(xBi,yBi,zBi)表示，下標(biāo)B表示這些離散點(diǎn)為基準(zhǔn)點(diǎn)(benchmark points)，1≤i≤‖Ω‖.

對(duì)物聯(lián)網(wǎng)的假設(shè)如下：物聯(lián)網(wǎng)節(jié)點(diǎn)部署后位置不變，節(jié)點(diǎn)之間一旦建立連接，該連接在節(jié)點(diǎn)存活期內(nèi)不會(huì)中斷；物聯(lián)網(wǎng)的節(jié)點(diǎn)是同質(zhì)的，即具備相同的通信距離、感知距離和初始能量；節(jié)點(diǎn)s的感知距離為r，感知范圍是以節(jié)點(diǎn)所在位置(xs,ys,zs)為中心的球體；設(shè)節(jié)點(diǎn)的通信距離為d，當(dāng)兩節(jié)點(diǎn)之間的歐氏距離不大于d時(shí)，兩節(jié)點(diǎn)可以建立通信.

對(duì)物聯(lián)網(wǎng)的定義如下：在三維空間S中部署m個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)構(gòu)成集合V，節(jié)點(diǎn)之間的相互連接(稱為無(wú)向邊)構(gòu)成集合E，節(jié)點(diǎn)和邊構(gòu)成圖G=(V,E).

定義1 連通性.如果圖G=(V,E)中任何兩節(jié)點(diǎn)之間都存在一條路徑，那么物聯(lián)網(wǎng)是連通的.節(jié)點(diǎn)連通率φ(m)定義為監(jiān)控空間部署m個(gè)節(jié)點(diǎn)后圖G的最大連通圖的節(jié)點(diǎn)數(shù)與圖G的全部節(jié)點(diǎn)數(shù)的比率.設(shè)G′=(V′,E′)表示圖G的最大連通子圖，那么

(1)

節(jié)點(diǎn)連通率坡度φ′(m,n)定義為

(2)

式中:φ(m)和φ(n)分別表示監(jiān)控空間部署m和n個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)連通性；φ′(m,n)表示部署不同數(shù)量的節(jié)點(diǎn)連通性的相對(duì)變化，將作為迭代尋找節(jié)點(diǎn)需求量的終止依據(jù).

定義2k-覆蓋的定義.如果空間中某點(diǎn)i位于至少k個(gè)節(jié)點(diǎn)的感知范圍內(nèi)，那么該點(diǎn)i是k-覆蓋的.當(dāng)k=1時(shí)，點(diǎn)i是1-覆蓋的.如果三維空間S中任何一點(diǎn)都是k-覆蓋的，那么空間S是k-覆蓋的.

三維空間中部署的節(jié)點(diǎn)i的坐標(biāo)為(xi,yi,zi)，1≤i≤m.每個(gè)節(jié)點(diǎn)i能夠監(jiān)測(cè)的離散點(diǎn)集合用SR(i,r)表示，集合Ω中滿足k-覆蓋的點(diǎn)集用Ωk表示.

k-覆蓋率ηk(m)定義為監(jiān)控空間部署m個(gè)節(jié)點(diǎn)后集合Ω中滿足k-覆蓋的節(jié)點(diǎn)占的比例，表示為

(3)

(4)

定義3k-覆蓋問(wèn)題.在三維空間中至少需要多少個(gè)節(jié)點(diǎn)以滿足監(jiān)控目標(biāo)空間是k-覆蓋的條件，并且要保證這些節(jié)點(diǎn)是連通的.k覆蓋問(wèn)題用數(shù)學(xué)描述如下：

maxy=f(X)=[ηk(m),φ(m)]，

(5)

式中：ηk≤1；φ≤1；X={(x1,y1,z1), (x2,y2,z2), …, (xm,ym,zm)}，表示所部署節(jié)點(diǎn)的坐標(biāo)的集合，m∈Z+.

2 k-覆蓋節(jié)點(diǎn)數(shù)量的計(jì)算方法

三維空間的k-覆蓋問(wèn)題最優(yōu)化已被證明是NP優(yōu)化問(wèn)題，本課題提出了一種近似最優(yōu)化方法來(lái)解決這個(gè)問(wèn)題.

2.1 基本方法

在給定的三維空間S中，當(dāng)部署的節(jié)點(diǎn)數(shù)量較少時(shí)，只有部分節(jié)點(diǎn)能連通且只有部分空間是k-覆蓋的.隨著部署節(jié)點(diǎn)數(shù)量的增加，節(jié)點(diǎn)的連通率和監(jiān)控空間的k-覆蓋率都會(huì)得到改善.節(jié)點(diǎn)的連通率和空間的覆蓋率是影響節(jié)點(diǎn)需求量的主要因素,為區(qū)分這兩個(gè)因素對(duì)節(jié)點(diǎn)選擇的影響，節(jié)點(diǎn)數(shù)量的計(jì)算分3個(gè)階段進(jìn)行.

(1)僅根據(jù)節(jié)點(diǎn)連通率計(jì)算節(jié)點(diǎn)需求量

節(jié)點(diǎn)連通率主要與節(jié)點(diǎn)的通信距離有關(guān)，與節(jié)點(diǎn)的覆蓋距離沒(méi)有關(guān)系.可以預(yù)見，為達(dá)到一定的節(jié)點(diǎn)連通率，隨著節(jié)點(diǎn)通信距離的增加，節(jié)點(diǎn)數(shù)的需求量將減少，這個(gè)階段獲得的節(jié)點(diǎn)數(shù)量記為mconn.

計(jì)算mconn的問(wèn)題可分解為兩個(gè)子問(wèn)題：①充分性問(wèn)題，即盡快找到一個(gè)節(jié)點(diǎn)數(shù)量，能夠滿足節(jié)點(diǎn)連通率φ(m)等于1或接近1；②必要性問(wèn)題，即最低需要部署多少個(gè)節(jié)點(diǎn)才能夠滿足條件.

圖1 節(jié)點(diǎn)需求量的計(jì)算流程Fig.1 Flow chart for computing node demand

(2)僅根據(jù)空間覆蓋率計(jì)算節(jié)點(diǎn)需求量

(3)綜合考慮節(jié)點(diǎn)連通率和空間覆蓋率來(lái)計(jì)算節(jié)點(diǎn)需求量

令mcomplete=max(mconn,mcover).當(dāng)監(jiān)控空間S部署mcomplete個(gè)節(jié)點(diǎn)后，可以同時(shí)實(shí)現(xiàn)節(jié)點(diǎn)連通率和空間k-覆蓋率等于100%或接近100%.

2.2 方法分析

將節(jié)點(diǎn)需求量的計(jì)算過(guò)程分為3個(gè)階段，主要考慮不同因素對(duì)計(jì)算的影響，也便于有針對(duì)性地分析影響因素.

在第1階段第(1)步，找到滿足條件的節(jié)點(diǎn)數(shù)，節(jié)點(diǎn)數(shù)的增長(zhǎng)方法有多種選擇，如線性增加、指數(shù)增加等.若采用線性增加方法，需要事先確定每次增加的節(jié)點(diǎn)數(shù)，即步長(zhǎng).如果步長(zhǎng)選取過(guò)小，需要多次迭代才能滿足要求；若步長(zhǎng)過(guò)大，雖然迭代次數(shù)減少，但依然存在冗余.因此，步長(zhǎng)的合理選擇存在一定的困難.采用指數(shù)增加的方法，即使初始節(jié)點(diǎn)選取較小，由于每次迭代節(jié)點(diǎn)數(shù)量成倍增加，也可以迅速找到滿足條件的節(jié)點(diǎn)數(shù).因此，指數(shù)增加的方式相對(duì)于線性增加具有一定的優(yōu)勢(shì).

在第1階段第(2)步，在[nmin,nmax]中搜索節(jié)點(diǎn)必要值，可以選擇線性搜索、分治策略等.和線性搜索相比，分治策略搜索的計(jì)算量比較小.

通過(guò)引入最大循環(huán)變量LOOP和誤差系數(shù)ε，在滿足一定精確度的同時(shí)，提升了程序的穩(wěn)定性.

第1階段的算法復(fù)雜度主要由計(jì)算節(jié)點(diǎn)連通率決定，而計(jì)算節(jié)點(diǎn)連通率的復(fù)雜度主要由計(jì)算最大連通子圖決定.第2階段的算法復(fù)雜度主要由計(jì)算空間k-覆蓋率決定，其算法復(fù)雜度為Θ(n2).

3 實(shí)驗(yàn)

新算法能夠計(jì)算出不同k-覆蓋對(duì)應(yīng)的節(jié)點(diǎn)需求量.k取值由1增加到5，步長(zhǎng)為1,不同k值對(duì)應(yīng)的節(jié)點(diǎn)需求量如圖3所示.從圖3可以看出，隨著k值的增加，節(jié)點(diǎn)需求量也逐漸增加，但增長(zhǎng)率低于k.

圖2 節(jié)點(diǎn)數(shù)量mconn與的關(guān)系曲線Fig.

圖3 節(jié)點(diǎn)數(shù)量mcover與k值的關(guān)系曲線Fig.3 Number of nodes mcover vs k

表與k，的關(guān)系表

4 結(jié)語(yǔ)

[1] ZHU C,ZHENG C,SHU L,et al.A survey on coverage and connectivity issues in wireless sensor networks[J].Journal of Network and Computer Applications，2012,35(2):619-632.

[2] ALAM S M,HAAS Z J.Topology control and network lifetime in Three-dimensional wireless sensor networks[J].Networking and Internet Architecture，2006(1):1-18.

[3] 鐘永信，黃建國(guó)，韓晶.三維傳感器網(wǎng)絡(luò)部署、覆蓋和連接問(wèn)題研究[J].控制與決策，2011,26(10):1447-1451.

[4]POMPILID,MELODIAT,AKYILDIZIF.Three-dimensionalandtwo-dimensionaldeploymentanalysisforunderwateracousticsensornetworks[J].AdHocNetworks，2009,7(4):778-790.

[5] 凡高娟，王汝傳，黃海平，等.基于容忍覆蓋區(qū)域的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)調(diào)度算法[J].電子學(xué)報(bào)，2011,39(1):89-94.

A calculation method of node demand in internet of things

HE Li, LI Bo

(CollegeofComputer,HenanUniversityofEngineering,Zhengzhou451191,China)

In Internet of Things (IOT) node comprehensive coverage and connectivity are related to whether the physical space can be effectively monitored. Coverage problem in two-dimensional space has been studied deeply. However, with the IOT applications extend into the air and water, coverage problem in 3D space needs to be solved. Since the recent methods of solvingk-coverage in 3D space are extended from the methods of solving 1-coverage, there are limitations. In summing up the current status of research on coverage problem, a novel and fast method was presented to calculate the node demand to meet thek-coverage conditions in 3d space. Exponential growth model is applied to find the sufficient value of node demand, and the divide-and-conquer strategy is used to quickly locate the necessary value of node demand. The experiments results show the adaptability of the new method is stronger and realistic.

k-coverage; divide-and-conquer strategy; coverage problem in 3D space

2016-11-18

河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(17A520026)；河南工程學(xué)院博士基金(D2012016)

何莉(1982-)，男，江西萍鄉(xiāng)人，講師，博士,主要研究方向?yàn)槲锫?lián)網(wǎng)與智能計(jì)算.

TP311

A

1674-330X(2017)01-0057-05