構(gòu)造信息勢(shì)場(chǎng)的一個(gè)偏微分方程模型

周 彬,穆春來(lái),姚 衛(wèi),魏 嵬

(1.西安科技大學(xué)理學(xué)院,陜西西安 710054;2.重慶大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,重慶 400030;3.河北科技大學(xué)理學(xué)院,河北石家莊 050018;4.西安交通大學(xué)電信學(xué)院,陜西西安 710049)

構(gòu)造信息勢(shì)場(chǎng)的一個(gè)偏微分方程模型

周 彬1,穆春來(lái)2,姚 衛(wèi)3,魏 嵬4

(1.西安科技大學(xué)理學(xué)院,陜西西安 710054;2.重慶大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,重慶 400030;3.河北科技大學(xué)理學(xué)院,河北石家莊 050018;4.西安交通大學(xué)電信學(xué)院,陜西西安 710049)

提出了用于構(gòu)造傳感器網(wǎng)絡(luò)中的信息位勢(shì)場(chǎng)的一個(gè)偏微分方程模型。一個(gè)拋物方程被引入并用于確定這個(gè)位勢(shì)場(chǎng);有限差分法則被用于數(shù)值求解。求解得到的位勢(shì)場(chǎng)保留了大部分對(duì)實(shí)際應(yīng)用有利的節(jié)點(diǎn)特征。歸功于偏微分方程所具有的良好性質(zhì),多個(gè)信息位勢(shì)場(chǎng)能夠很自然地被聚合起來(lái)。

傳感器網(wǎng)絡(luò);信息勢(shì)場(chǎng);有限差分法;移動(dòng)最小二乘;拋物方程

傳感器的研究進(jìn)展顯示了其巨大的潛在用途,在和現(xiàn)實(shí)世界的相互作用過(guò)程中,能徹底影響和改變?nèi)藗兩畹氖澜?。分布式?shù)據(jù)采集系統(tǒng)中,一些初步的應(yīng)用情景由于具備低成本等優(yōu)點(diǎn),已經(jīng)超越了傳統(tǒng)的集中式傳感器系統(tǒng)[1-2]。隨著技術(shù)的逐步成熟和傳感器網(wǎng)絡(luò)規(guī)模擴(kuò)大,人們期望傳感器網(wǎng)絡(luò)可以超越原有的軍事部署用途,可以在動(dòng)物或人類(lèi)的工作和生活的地方進(jìn)行監(jiān)測(cè)。例如:家庭、建筑、道路棲息地等,在上述場(chǎng)所中的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)和用戶(hù)身處同一個(gè)網(wǎng)絡(luò)物理空間從而進(jìn)行交互式對(duì)話(huà)。此外,這種對(duì)話(huà)還要求低延遲地提供相關(guān)信息的傳輸[3],從而可以讓用戶(hù)能及時(shí)響應(yīng)。例如在第一響應(yīng)時(shí)間內(nèi),作出災(zāi)難恢復(fù)方案[4]。在找到可自行設(shè)定高查詢(xún)頻率的可擴(kuò)展方法之前,信息導(dǎo)航也已被探索研究中。

很多基于梯度的研究方法都是使用物理現(xiàn)象的梯度也就是物理量的分布來(lái)說(shuō)明的[5-7],因?yàn)楹芏辔锢砹康目臻g分布具有很大的類(lèi)似,例如熱量的傳導(dǎo)就是遵循自然的擴(kuò)散法則。然而,梯度是被自然規(guī)律所影響的,不是可以完全依賴(lài)的法則。當(dāng)存在局部極值區(qū)域,會(huì)迫使信息來(lái)引導(dǎo)用戶(hù)隨機(jī)地走動(dòng)。

筆者嘗試使用嵌入式傳感器網(wǎng)絡(luò),通過(guò)動(dòng)態(tài)的環(huán)境輔助信息來(lái)發(fā)現(xiàn)空位信息場(chǎng)而進(jìn)行導(dǎo)航。這個(gè)過(guò)程包括數(shù)據(jù)導(dǎo)航(即從任何節(jié)點(diǎn)回答用戶(hù)的查詢(xún))。當(dāng)手持設(shè)備與附近的傳感器節(jié)點(diǎn)通信時(shí),用戶(hù)可以獲得實(shí)時(shí)的導(dǎo)航信息。例如,路邊傳感器本身也可以用來(lái)監(jiān)測(cè)本地交通擠塞狀況和市中心區(qū)域的空停車(chē)場(chǎng),還可在每個(gè)停車(chē)位部署傳感器,用來(lái)實(shí)時(shí)跟蹤具體情況。

作為一種有效的數(shù)值方法,有限元法能夠很方便的用于各種領(lǐng)域,但是在求解大變形問(wèn)題上仍然存在很多困難。復(fù)雜結(jié)構(gòu)的網(wǎng)格生成是困難并且耗時(shí)的[8]。最近,無(wú)網(wǎng)格法發(fā)展迅速并用于很多領(lǐng)域[9]。這是一種不依賴(lài)于節(jié)點(diǎn)的數(shù)值方法,它能有效克服上述困難。目前的無(wú)網(wǎng)格法(例如 EFG[10],PUM,Hp-Clouds,M LPG[8])大都是基于 Galerkin方法。數(shù)值積分對(duì)這類(lèi)方法來(lái)說(shuō)是必要的,但會(huì)導(dǎo)致巨大的運(yùn)算量,而且背景網(wǎng)格也需要被提前引入,而基于聚點(diǎn)法的無(wú)網(wǎng)格法不需要數(shù)值積分,具有較小的運(yùn)算量,但是精度較低,穩(wěn)定性較差。在最小二乘法基礎(chǔ)上,文獻(xiàn)[11]提出的無(wú)網(wǎng)格加權(quán)最小二乘法能夠克服上述缺點(diǎn),移動(dòng)最小二乘法是其中的關(guān)鍵環(huán)節(jié)。

在本文中,筆者將用無(wú)網(wǎng)格法構(gòu)造傳感器網(wǎng)絡(luò)中的信息位勢(shì)場(chǎng)。首先,用拉普拉斯方程確定一個(gè)平滑并且保留主要原有特征的信息位勢(shì)場(chǎng)。其次,用移動(dòng)最小二乘法求解相關(guān)的偏微分方程。得益于偏微分方程的良好性質(zhì),多個(gè)信息位勢(shì)場(chǎng)能夠被自然地融合。本文方法能夠更有效地獲得合適的信息位勢(shì)場(chǎng)。

1 背景和基本原理

1.1 信息位勢(shì)場(chǎng)

位勢(shì)場(chǎng)被用于描述節(jié)點(diǎn)的信息分布,并應(yīng)用于各種場(chǎng)景。這些應(yīng)用場(chǎng)景能夠通過(guò)一些基于梯度的算法得到信息位勢(shì)場(chǎng)。對(duì)于這些算法來(lái)說(shuō),更重要的是建立一個(gè)合適的信息位勢(shì)場(chǎng)。更確切地說(shuō),獲得一個(gè)光滑并且保留主要原始特征的信息位勢(shì)場(chǎng)是必要的前提。光滑性將有利于梯度計(jì)算和算法實(shí)現(xiàn),而主要特征的保留則是目標(biāo)能夠?qū)崿F(xiàn)的必要保障。

很多數(shù)學(xué)方法和技術(shù)能夠被用于信息位勢(shì)場(chǎng)(曲面)的構(gòu)造,比如:多項(xiàng)式擬合,非線(xiàn)性擬合,多項(xiàng)式插值,最小二乘擬合,徑向基插值等等。目前,這些方法已經(jīng)被用于各種領(lǐng)域,隨著它們的發(fā)展,所構(gòu)造曲面的誤差也越來(lái)越小,光滑性也逐漸提高。

然而,這些方法不能直接應(yīng)用在此場(chǎng)景中。如圖1a)所示,傳統(tǒng)方法獲得的位勢(shì)曲面具有較好的光滑性和較高的節(jié)點(diǎn)準(zhǔn)確性,但是梯度模在靠近極值點(diǎn)處迅速衰減為0,圖1b)顯示了相應(yīng)的梯度模場(chǎng)。

如果信息位勢(shì)場(chǎng)是用傳統(tǒng)方法構(gòu)造的,那么在進(jìn)一步的實(shí)際應(yīng)用中,比如停車(chē)場(chǎng)空閑車(chē)位導(dǎo)航,用戶(hù)在局部極值點(diǎn)附近將被低水平的梯度所導(dǎo)航,影響效率。

這意味著預(yù)期的位勢(shì)場(chǎng)在目標(biāo)節(jié)點(diǎn)(局部極值點(diǎn))附近,仍需保持較高的梯度模水平。

圖1 傳統(tǒng)方法的構(gòu)造結(jié)果Fig.1 Universal resultsof traditionalmethods

1.2 拉普拉斯方程

根據(jù)上述目的,文獻(xiàn)[4]把預(yù)期的位勢(shì)場(chǎng)u(x)假定為Ω中的一個(gè)調(diào)和函數(shù),給出如下拉普拉斯方程這里Г=?Ω。

由偏微分方程的理論易得,位勢(shì)函數(shù)在區(qū)域內(nèi)部的值能夠被它在邊界上的取值唯一確定。而且,根據(jù)極值原理,極值點(diǎn)必定位于邊界上。也就是說(shuō),位勢(shì)場(chǎng)函數(shù)可以通過(guò)求解拉普拉斯方程得到。圖2給出了2個(gè)非凸域上具有Dirichlet條件的Lap lace問(wèn)題求解結(jié)果。

圖2 非凸域上的拉普拉斯問(wèn)題Fig.2 Lap lace p roblem s in Non-convex regions

2 無(wú)網(wǎng)格法

有許多數(shù)值方法能夠被用于求解拉普拉斯問(wèn)題(1),比如:有限差分法(FDM),有限元法 (FEM)等等。作為一種有效的數(shù)值方法,有限元法能夠很便捷地被用于求解偏微分方程。然而,由于節(jié)點(diǎn)分布的不規(guī)則性,很難建立有限元方法所需要的網(wǎng)格。文獻(xiàn)[11]中提出的移動(dòng)最小二乘無(wú)網(wǎng)格法能夠克服這樣的困難。

若u(x)在區(qū)域Ω中的節(jié)點(diǎn)x I(I=1,2,…,N)上是已知的,且基函數(shù)為

據(jù)此,拉普拉斯方程(1)能夠被重新表示,從而建立相關(guān)的線(xiàn)性方程組。求解之后即可得到所需要的信息位勢(shì)場(chǎng)。

3 算例與仿真

圖3 由三個(gè)節(jié)點(diǎn)確定的信息位勢(shì)場(chǎng)Fig.3 Potential field determined by three nodes

算例2 圖4a)給出了一個(gè)隨機(jī)生成的傳感器網(wǎng)絡(luò)中的信息分布。相關(guān)拉普拉斯問(wèn)題的邊界條件設(shè)置類(lèi)似于算例1。通過(guò)計(jì)算,能夠得到預(yù)期的信息位勢(shì)場(chǎng),如圖4b)所示。該信息位勢(shì)場(chǎng)足夠平滑,且保留了原有信息分布的主要特征,能夠用于各種場(chǎng)景。

圖4 由隨機(jī)信息分布所確定的信息位勢(shì)場(chǎng)Fig.4 Potential field determined by a random distribution

4 結(jié) 語(yǔ)

提出了用于構(gòu)造傳感器網(wǎng)絡(luò)中的信息位勢(shì)場(chǎng)的一個(gè)新模型。一個(gè)保留了原有信息分布主要特征的平滑信息位勢(shì)場(chǎng)能夠由拉普拉斯方程所確定,并通過(guò)無(wú)網(wǎng)格方法進(jìn)行求解。這樣的信息位勢(shì)場(chǎng)對(duì)于很多傳感器網(wǎng)絡(luò)的應(yīng)用是很有幫助的,比如:停車(chē)場(chǎng)導(dǎo)航、環(huán)境監(jiān)控等等[12-13]。第3節(jié)的數(shù)值算例驗(yàn)證了方法的有效性和穩(wěn)定性。結(jié)果表明本文提出的方法能夠很方便地應(yīng)用于傳感器網(wǎng)絡(luò)中,用戶(hù)可以通過(guò)手持設(shè)備和周邊節(jié)點(diǎn)交互,獲得實(shí)時(shí)的導(dǎo)航信息;道路傳感器監(jiān)控當(dāng)?shù)氐慕煌ㄗ枞畔?各個(gè)停車(chē)場(chǎng)的空閑車(chē)位信息能夠被監(jiān)控并有效利用等等。

[1]A KYILD IZ I F,SU W,SAN KARASUBRAMAN IAM Y,et al.Wireless sensor netwo rks:A survey[J].Computer Netwo rks,2002,38(4):393-422.

[2]A KYILD IZ IF,M ELOD IA T,CHOWDHURY K R.A survey on w irelessmultimedia sensor netwo rks[J].Computer Networks,2007,51:921-960.

[3]KALAN TARIM,SHA YMAN M.Energy efficient routing in w ireless sensor netwo rks[A].Proceeding of Conference on Information Sciences and Systems[C].Princeton:NJ,2004.356-361.

[4]L IN H J,LU M H,M ILOSAVLJEV IC N,et al.Composable info rmation gradients in w ireless senso r netwo rks[A].Proceeding of the International Conference on Info rmation Processing in Senso r Netwo rks(IPSN’08)[C].Washington:IEEE Computer Society,2008.121-132.

[5]CHU M,HAUSSECKER H,ZHAO F.Scalable info rmation driven sensor querying and routing fo r ad hoc heterogeneous senso r networks[J].International Journal of High Performance Computing Applications,2002,16(3):293-313.

[6]FARUQUE J,HELM Y A,RUGGED B.Routing on fingerp rint gradients in sensor networks[A].IEEE International Conference on Pervasive Services(ICPS)[C].Lebanon:American University of Beirut,2004.179-188.

[7]FARUQUE J,PSOUN IS K,HELM Y A.Analysis of gradient based routing p rotocols in senso r netwo rks[J].Lecture Notes in Computer Science,2005,35:258-275.

[8]A TLURISN,ZHU T.A new meshless local Petrov-Galerkin(MLPG)app roach in computationalmechanics[J].Computational Mechanics,1998,22(2):117-127.

[9]BELYTSCHKO T,KRONGAUZ Y.Meshlessmethods:An overview and recent developments[J].Computer Methods in App lied Mechanics and Engineering,1996,139(1/4):3-47.

[10]ZHOU W Y,KOU X D.Meshlessmethod and its app lication in engineering[J].Journal of Mechanics,1998,14(2):193-202.

[11]ZHANG X,HU W,PAN X F.Weighted least squaresmeshlessmethod[J].Journal of M echanics,2003,14(4):425-431.

[12]L IU J,ZHAO F,PETROV IC D.Information-directed routing in ad hoc senso r netwo rks[J].IEEE Journal on Selected A reas in Communications,2005,23(4):851-861.

[13]張東凱,田貴辰,鞏增泰,等.二階模糊微分方程的數(shù)值解[J].河北科技大學(xué)學(xué)報(bào)(Journal of Hebei University of Science and Technology),2010,31(2):158-161.

PDEmodel fo r constructing potential fields in sensornets

ZHOU Bin1,MU Chun-lai2,YAO Wei3,WEIWei4
(1.School of Sciences,Xi′an University of Science and Technology,Xi′an Shaanxi 710054,China;2.School of Mathematics and Statistics,Chongqing University,Chongqing 400030,China;3.School of Sciences,Hebei University of Science and Technology,Shijiazhuang Hebei 050018,China;4.School of Electronic and Information Engineering,Xi′an Jiaotong University,Xi′an Shaanxi 710049,China)

A PDEmodel is p roposed in this paper to construct the info rmation potential fields in sensornets.A parabolic equation is introduced to determine the field and the finite differentialmethod is used to salve it.The solution p reservesmajor nodes’features w hich are advantageous to most app licationsof sensornets.Mo re than one pieceof information potentials fields can be intergraded together naturally due to the sound p roperty of the PDEs.Efficiency and stability of ourmethod are verified by several numerical examp les.

sensornets;potential fields;finite differentialmethod;moving least-square;parabolic equation

O175.2;TP393.17

A

1008-1542(2010)06-0492-05

2010-06-08;責(zé)任編輯:張 軍

國(guó)家自然科學(xué)基金資助項(xiàng)目(10771226,10926055)

周 彬(1982-),男,浙江浦江人,講師,博士研究生,主要從事偏微分方程應(yīng)用、傳感器網(wǎng)絡(luò)方面的研究。