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

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

構造信息勢場的一個偏微分方程模型

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

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

提出了用于構造傳感器網絡中的信息位勢場的一個偏微分方程模型。一個拋物方程被引入并用于確定這個位勢場;有限差分法則被用于數值求解。求解得到的位勢場保留了大部分對實際應用有利的節(jié)點特征。歸功于偏微分方程所具有的良好性質,多個信息位勢場能夠很自然地被聚合起來。

傳感器網絡;信息勢場;有限差分法;移動最小二乘;拋物方程

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

很多基于梯度的研究方法都是使用物理現(xiàn)象的梯度也就是物理量的分布來說明的[5-7],因為很多物理量的空間分布具有很大的類似,例如熱量的傳導就是遵循自然的擴散法則。然而,梯度是被自然規(guī)律所影響的,不是可以完全依賴的法則。當存在局部極值區(qū)域,會迫使信息來引導用戶隨機地走動。

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

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

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

1 背景和基本原理

1.1 信息位勢場

位勢場被用于描述節(jié)點的信息分布,并應用于各種場景。這些應用場景能夠通過一些基于梯度的算法得到信息位勢場。對于這些算法來說,更重要的是建立一個合適的信息位勢場。更確切地說,獲得一個光滑并且保留主要原始特征的信息位勢場是必要的前提。光滑性將有利于梯度計算和算法實現(xiàn),而主要特征的保留則是目標能夠實現(xiàn)的必要保障。

很多數學方法和技術能夠被用于信息位勢場(曲面)的構造,比如:多項式擬合,非線性擬合,多項式插值,最小二乘擬合,徑向基插值等等。目前,這些方法已經被用于各種領域,隨著它們的發(fā)展,所構造曲面的誤差也越來越小,光滑性也逐漸提高。

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

如果信息位勢場是用傳統(tǒng)方法構造的,那么在進一步的實際應用中,比如停車場空閑車位導航,用戶在局部極值點附近將被低水平的梯度所導航,影響效率。

這意味著預期的位勢場在目標節(jié)點(局部極值點)附近,仍需保持較高的梯度模水平。

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

1.2 拉普拉斯方程

根據上述目的,文獻[4]把預期的位勢場u(x)假定為Ω中的一個調和函數,給出如下拉普拉斯方程這里Г=?Ω。

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

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

2 無網格法

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

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

據此,拉普拉斯方程(1)能夠被重新表示,從而建立相關的線性方程組。求解之后即可得到所需要的信息位勢場。

3 算例與仿真

圖3 由三個節(jié)點確定的信息位勢場Fig.3 Potential field determined by three nodes

算例2 圖4a)給出了一個隨機生成的傳感器網絡中的信息分布。相關拉普拉斯問題的邊界條件設置類似于算例1。通過計算,能夠得到預期的信息位勢場,如圖4b)所示。該信息位勢場足夠平滑,且保留了原有信息分布的主要特征,能夠用于各種場景。

圖4 由隨機信息分布所確定的信息位勢場Fig.4 Potential field determined by a random distribution

4 結 語

提出了用于構造傳感器網絡中的信息位勢場的一個新模型。一個保留了原有信息分布主要特征的平滑信息位勢場能夠由拉普拉斯方程所確定,并通過無網格方法進行求解。這樣的信息位勢場對于很多傳感器網絡的應用是很有幫助的,比如:停車場導航、環(huán)境監(jiān)控等等[12-13]。第3節(jié)的數值算例驗證了方法的有效性和穩(wěn)定性。結果表明本文提出的方法能夠很方便地應用于傳感器網絡中,用戶可以通過手持設備和周邊節(jié)點交互,獲得實時的導航信息;道路傳感器監(jiān)控當地的交通阻塞信息;各個停車場的空閑車位信息能夠被監(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]張東凱,田貴辰,鞏增泰,等.二階模糊微分方程的數值解[J].河北科技大學學報(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;責任編輯:張 軍

國家自然科學基金資助項目(10771226,10926055)

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