在無線感測器網路的環境下，由於 sensor具有儲存以及溝通的能力，我們可以把無線感測器網路視為一個大型且分散式的資料庫.
在感測器網路中追蹤移動物體依然是個很重要的應用，並且也越來越多人在關心如何取得移動物體的位置資訊.
舉例來說，在戰場上的士兵們在沒有通訊設備的狀況下，依舊可以藉由感測器網路來連絡友軍或是找到敵方的位置.
然而，由於這群移動物體的位置變動很頻繁，不停地移動會導致大量的更新訊息在感測器網路中傳遞.
本篇論文提出了一個索引的架構，能夠分散式的紀錄移動物體的位置. 當物體移動的時候只需要少量 sensor 之間的溝通，就可以解決大量更新的問題，減少頻繁地傳輸訊息的代價.
另外，對於感測器網路中的 hole，我們也有完善的處理. 物體在 hole裡面時，我們亦可以提供他所在的區域範圍，而不至於失去他的蹤跡.
根據實驗的結果顯示，我們的演算法在更新及查詢等不同的情況下都有好的表現.

Abstract
In　the　wireless　sensor　networks,　due　to　the　storage　and　communication
ability　of　sensors,　wireless　sensor　networks　can　be　considered　as　a
huge　distributed　databases.　Tracking　moving　object　is　still　an　important
applications　in　wireless　sensor　networks,　and　there　are　more　and
more　people　concern　about　how　to　get　locations　of　moving　objects.　For
example,　soldiers　in　the　situations　of　lack　of　communication　equipment
can　still　contact　with　their　army　or　find　locations　of　the　enemy　by　the
sensor　networks.　However,　the　locations　of　those　moving　objects　change
very　frequently,　continuously　mobility　of　a　moving　object　leads　to　a　huge
number　of　update　messages　forwarding　in　the　wireless　sensor　networks.
This　paper　proposed　an　index　structure　which　recoreds　the　location　of
moving　objects　distributedly.　There　are　just　a　few　communucations　between
sensors　that　can　solve　the　problem　of　the　huge　number　of　update
messages　and　decrease　the　cost　of　frequently　message-transmitting　when
the　moving　object　moves.　We　also　have　a　maturity　process　for　the　hole
of　the　sensor　networks.　When　the　moving　object　goes　into　the　hole,　we
can　provid　the　region　which　the　moving　object　stays　and　will　not　lose　the
trace　of　it.　The　performance　results　show　that　the　algorithm　we　proposed
performs　good　in　the　different　situations　of　update　and　search.

[1]　Dina　Goldin,　Mingjun　Song,　Ayferi　Kutlu,　Huayan　Gao,　Hardik
Dave,　”Georouting　and　Delta-gathering:　Efficient　Data　Propagation
Techniques　for　GeoSensor　Networks,”GeoSensor　Networks　(GSN’03)
Workshop　,　Portland,　Maine,　Oct　2003.

[2]　Chih-Yu　Lin,　Yu-Chee　Tseng,　”Structures　for　In-Network　Moving
Object　Tracking　in　Wireless　Sensor　Networks,”In　Proceedings　of
First　International　Conference　on　Broadband　Networks　(BROADNETS’
04),　San　Jose,　California,　USA,　October　2004,　pp.718-727.

[3]　Xin　Li,　Young　Jin　Kim,　Ramesh　Govindan,　Wei　Hong,　”Multidimensional
Range　Queries　in　Sensor　Networks,”In　Proceedings　of　the
First　ACM　International　Conference　on　Embedded　Networked　Sensor
Systems　(SenSys’03)　Los　Angeles,　California,　USA,　November　2003,
pp.63-75.

[4]　Benjamin　Greenstein,　Deborah　Estrin,　Ramesh　Govindan,　Sylvia
Ratnasamy,　Scott　Shenker,　”DIFS:　A　Distributed　Index　for　Features
in　Sensor　Networks,”In　Proceedings　of　First　IEEE　International
Workshop　on　Sensor　Network　Protocols　an　Applications　(SNPA
2003),　Anchorage,　Alaska,　USA,　May　11,　2003.

[5]　Murat　Demirbas,　Hakan　Ferhatosmanoglu,　”Peer-to-Peer　Spatial
Queries　in　Sensor　Networks,”Third　International　Conference　on
Peer-to-Peer　Computing　(P2P’03),　Linkopings,　Sweden,　September
2003,　pp.32-39.

[6]　Jie　Gao　and　Leonidas　J.　Guibas　and　John　Hershberger　and　Li　Zhang,
”Fractionally　cascaded　information　in　a　sensor　network,”Proceedings
of　the　third　international　symposium　on　Information　processing　in
sensor　networks　(IPSN’04),　Berkeley,　California,　USA,　April　2004,
pp.311-319.

[7]　W.　Zhang,　G.　Cao,　T.L.　Porta,　”Data　Dissemination　with　Ring-
Based　Index　for　Wireless　Sensor　Networks,”Proceedings　of　the　forth
international　symposium　on　Information　processing　in　sensor　networks
(IPSN’03),　Atlanta,　Georgia,　USA,　November　2003.

[8]　Soon-Young　Park,　Hae-Young　Bae,　”A　distributed　spatial　index
for　time-efficient　aggregation　query　processing　in　sensor　networks,”
Proceedings　of　the　international　conference　on　computational
science(ICCS’05),　Atlanta,　USA,　May　2005.

[9]　H.　T.　Kung　,　D.　Vlah,　”Efficient　Location　Tracking　Using　Sensor
Networks,”Proceedings　of　2003　IEEE　Wireless　Communications　and
Networking　Conference　(WCNC),　New　Orleans,　Louisiana,　USA,
March　2003.

[10]　Qing　Fang,　Jie　Gao,　Leonidas　J.　Guibas,　”Locating　and　Bypassing
Routing　Holes　in　Sensor　Networks,”Proceedings　of　IEEE　INFOCOM’
04,　Hong　Kong,　March　2004.

[11]　Ahmed　N.　,　Kanhere　S.　and　Jha　S.,　”The　Holes　Problem　in　Wireless
Sensor　Networks:　A　survey,”Proceedings　of　ACM　SIGMOBILE　Mobile
Computing　and　Communications　Review,　April　2005,　pp.4-18.

[12]　B.　Karp　and　H.T.　Kung,　”GPSR:　Greedy　Perimeter　Stateless　Routing
for　Wireless　Networks,”Proceedings　of　The　Sixth　Annual　International
Conference　on　Mobile　Computing　and　Networking,　Massachusetts,
Boston,　August　2000.

[13]　Yingqi　Xu,　Wang-Chien　Lee,　”On　Localized　Prediction　for　Power
Efficient　Object　Tracking　in　Sensor　Networks,”Proceedings　of　23rd
International　Conference　on　Distributed　Computing　Systems　Workshops
(ICDCSW’03)　,　Providence,　Rhode　Island,　USA,　May　2003,
p434.

[14]　Yingqi　Xu,　Julian　Winter,　Wang-Chien　Lee,　”Prediction-based
Strategies　for　Energy　Saving　in　Object　Tracking　Sensor　Networks,”
Proceedings　of　2004　IEEE　International　Conference　on　Mobile
Data　Management　(MDM’04)　,　Berkeley,　California,　USA,　January
2004,　p346.

[15]　Yingqi　Xu,　Julian　Winter,　Wang-Chien　Lee,　”Dual　Prediction-based
Reporting　for　Object　Tracking　Sensor　Networks,”Proceedings　of　First
Annual　International　Conference　on　Mobile　and　Ubiquitous　Systems:
Networking　and　Services　(MobiQuitous’04)　,　Cambridge,　Massachusetts
USA,　August　2004,　pp.　154-163.

[16]　Rahul　Gupta,　Samir　R.　Das,　”Tracking　Moving　Targets　in　a
Smart　Sensor　Network,”Proc.　VTC　Fall　2003　Symposium　,　Orlando,
Florida,　USA,　Oct　2003.

[17]　Simonas　Saltenisy,　Christian　S.　Jensen,　Scott　T.　Leutenegger,　Mario
A.　Lopez,　”Indexing　the　positions　of　continuously　moving　objects,”in
SIGMOD　Conference　,　Dallas,　Texas,　United　States　,　2000,　pp.331-
342.

[18]　Mong-Li　Lee,　Wynne　Hsu,　Christian　S.　Jensen,　Bin　Cui,　Keng
Lik　Teo,　”Supporting　Frequent　Updates　in　R-Trees:　A　Bottom-Up
Approach,”In　Proceedings　of　the　International　Conference　on　Very
Large　Data　Bases(VLDB’03)　,　Berlin,　Germany,　2003,　pp.　608–619.

[19]　Yuni　Xia,　Sunil　Prabhakar,　”Q+Rtree:　Efficient　Indexing　for　Moving
Object　Databases　,”In　Proceedings　the　8th　International　Conference
on　Database　Systems　for　Advanced　Applications　(DASFAA’03)　,　Kyoto,
Japan,　2003.

[20]　Christian　S.　Jensen,　Dan　Lin,　Beng　Chin　Ooi,　”Query　and　Update
Efficient　B+-Tree　Based　Indexing　of　Moving　Objects,”In　Proceedings
of　the　Thirtieth　International　Conference　on　Very　Large　Data　Bases
(VLDB’04),　Toronto,　Canada,　August　2004.