成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	許智程 Hsu, Chih-Cheng
論文名稱：	在隨意型感測器網路下對移動物體搜尋最近鄰居之研究 Nearest Neighbor Search for Moving Objects in Ad-hoc Sensor Networks
指導教授：	陳朝鈞 Chen, Chao-Chun 李強 Lee, Chiang
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2006
畢業學年度：	94
語文別：	中文
論文頁數：	83
中文關鍵詞：	移動物體、演算法、查詢處理、最近鄰居搜尋、無線感測器網路
外文關鍵詞：	query processing, NN search query, ireless sensor network, moving object, algorithm
相關次數：	點閱：122 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

　　近來在無線通訊與電子技術的進展下，使得無線感測器　(wireless　sensor　node)　這種低成本，低耗電的多功能偵測儀器逐漸的普及開來。藉由一大群的無線感測器部署在環境周遭形成無線感測器網路　(wireless　sensor　network)　來收集環境資料，透過彼此的互相溝通傳輸可以把資料傳回特定的位置以供使用者查詢感興趣的資訊。因此無線感測器網路常被應用在　Location　Based　Service　(LBS)　上面，使用者可以在任何時間以及地點，透過無線感測器網路來查詢感興趣移動物體　(moving　object)　的位置。所以本論文主要是在無線感測器網路上解決　LBS　中一個極為重要的問題類型，稱之為　nearset　nieghbor　search　query。因為無線感測器有限的電力來源，使得有效率的能源管理成為在處理　NN　search　query　極為重要的考量;　而且移動物體的位置會隨著時間而變動，所以必須在能源節省的前提下持續地維持所儲存物體位置資訊的正確性。本論文提出了一個在移動物體位置變動率很高的情況下，有效率處理　NN　search　query　的演算法，以及分散式的　moving　object　位置資訊儲存機制。最後我們也以實驗結果證明我們所提出的方法在多數的情況下對於能源節省都有很好的表現。

　　With　the　rapid　development　of　wireless　communications　and　electronics　technologies,　wireless　sensor　nodes　have　emerged　as　a　promising　solution　for　a　wide　range　of　various　applications.　A　wireless　sensor　network　is　constructed　of　a　large　number　of　tiny　sensor　nodes　scattered　in　an　area　of　monitoring,　and　we　can　forward　queries　to　find　the　features　of　interest.　Wireless　sensor　networks　have　been　widely　used　for　Location　Based　Service　(LBS).　Users　can　query　the　locations　of　moving　objects　through　wireless　sensor　network　at　anytime　and　anywhere.　In　this　paper,　we　address　one　of　the　most　important　classes　of　LBS,　called　nearset　nieghbor　search　query,　for　moving　objects　in　wireless　sensor　networks.　Due　to　the　limited　power　supply　for　sensor　nodes,　energy　efficiency　is　a　critical　consideration　in　the　design　of　NN　search　algorithm.　Because　the　locations　of　moving　objects　change　over　time,　we　must　maintain　the　accuracy　of　stored　location　information.　In　this　paper,　we　propose　an　energy　efficient　NN　search　algorithm　and　a　distributed　object　location　storage　for　moving　objects　in　wireless　sensor　networks.　Experimental　results　show　that　our　algorithms　can　save　significiant　energy　under　various　conditions.

Abstract　..........................................................　i
Acknowledgements　................................................　iii
Table　of　Contents　..............................................　iv
Table　of　Figures　..............................................　vii
Table　of　Tables　................................................　ix
1　Introduction　...................................................　1
2　Related　Work　..................................................　7
　2.1　NN　Search　Algorithm　in　centralized　system　.............　7
　2.2　NN　Search　Algorithm　in　WSN　.............................　9
　　2.2.1　KPT　....................................................　9
　　2.2.2　DNN　...................................................　10
3　Problem　Formulation　..........................................　12
　3.1　Object　Tracking　Sensor　Network　Environment　............　12
　3.2　Application　Requirements　and　Metrics　...................　14
　3.3　Basic　Ideas　Behind　Proposed　Algorithm　.................　15
　3.4　CanonicalMethods　..........................................　16
4　A　Framework　for　NN　Search　Query　..........................　20
　4.1　SystemOverview　............................................　20
　4.2　Cell　Partition　...........................................　22
5　In-network　Cost-bound　NN　Search(ICNNS)　.....................　26
　5.1　Pruning　Approach　.........................................　27
　　5.1.1　Prediction-based　NN　Candidate　Selecting　Technic　...　27
　　5.1.2　Gathering　Technic　....................................　30
　5.2　Cost-bound　Searching　Approach　...........................　35
　　5.2.1　Inner-outter　Determining　Technic　....................　35
　　5.2.2　Ring-based　Routing　Technic　..........................　38
　5.3　RecoveryMechanism　.........................................　42
6　Two-level　Distributed　Location　Storage　(TDLS)　.............　43
　6.1　StorageMechanism　..........................................　43
　6.2　V-cell　Hand　Off　.........................................　46
7　Query　Optimization　...........................................　48
　7.1　QuadrangleGatheringOptimization　...........................　48
　　7.1.1　Quadrangle　Gathering　Optimization　Algorithm　........　48
　　7.1.2　Analysis　..............................................　49
　7.2　HypothesisGatheringOptimization　...........................　54
8　Performance　Evaluation　.......................................　57
　8.1　Metrics　and　Settings　....................................　57
　　8.1.1　Wireless　Sensor　Network　Setup　......................　57
　　8.1.2　ObjectMovingModel　.....................................　58
　　8.1.3　ComparedApproaches　....................................　59
　8.2　Impact　of　Query　Optimization　...........................　59
　8.3　Impact　of　β　.............................................　60
　8.4　Impact　of　Number　of　V-cells　...........................　62
　8.5　Impact　of　Query　Rate　...................................　64
　8.6　Impact　of　Number　of　Objects　...........................　68
　8.7　Impact　ofMaximumSpeed　of　Objects　.......................　72
　8.8　Workload　for　Sensor　Nodes　..............................　74
9　Conclusions　...................................................　76
Bibliography　.....................................................　77
Biography　........................................................　82
                                    

[1]　C.　Buragohain,　D.　Agrawal,　S.　Suri,　“Power　aware　routing　for　sensor　databases,”In　Proceedings　of　IEEE　Infocom’05　,　March　2005.
[2]　Samuel　Madden,　Michael　J.　Franklin,　Joseph　M.　Hellerstein,　Wei　Hong,　“The　Design　of　an　Acquisitional　Query　Processor　for　Sensor　Networks,”In　Proceedings　of　the　2003　ACM　SIGMOD　International　Conference　on　Management　of　Data　(SIGMOD’03),　June　2003,　pp.　491-502.
[3]　James　Newsome,　Dawn　Song,　“GEM:　Graph　EMbedding　for　Routing　and　DataCentric　Storage　in　Sensor　NetworksWithout　Geographic　Information,　”In　Proceedings　of　the　First　ACM　International　Conference　on　Embedded　Networked　Sensor　Systems　(SenSys’03),　November　2003,　pp.　76-88.
[4]　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),　November　2003,　pp.　63-75.
[5]　Aram　Galstyan,　Bhaskar　Krishnamachari,　Kristina　Lerman,　Sundeep　Pattem,　“Distributed　Online　Localization　in　Sensor　Networks　Using　a　Moving　Target,”　In　Proceedings　of　the　third　international　symposium　77　BIBLIOGRAPHY　78　on　Information　processing　in　sensor　networks(IPSN’04),　April　2004,　pp.　61-70.
[6]　N.　Bulusu,　J.　Heidemann,　D.　Estrin,　“GPS-Less　Low　Cost　Outdoor　Localization　for　Very　Small　Devices,”　In　IEEE　Personal　Communications　Magazine,　Special　Issue　on　Smart　Spaces　and　Environments,　October　2000.
[7]　L.　Girod,　D.　Estrin,　“Robust　Range　Estimation　using　Acoustic　and　Multimodal　Sensing,”　In　Proceedings　of　the　IEEE/RSJ　Conference　on　Intelligent　Robots　and　Systems,　October　2001.
[8]　N.　Priyantha,　A.　Chakraborty,　H.　Balakrishnan,　“The　Cricket　Location　Support　System,”　In　Proceedings　of　the　Sixth　Annual　ACM/IEEE　International　Conference　on　Mobile　Computing　and　Networking　(Mobicom　2000),　August　2000.
[9]　N.　Priyantha,　A.　Liu,　H.　Balakrishnan,　S.　Teller,　“The　Cricket　Compass　for　Context-Aware　Mobile　Applications,”　In　Proceedings　of　the　Seventh　Annual　ACM/IEEE　International　Conference　on　Mobile　Computing　and　Networking　(Mobicom　2001),　July　2001.
[10]　A.　Savvides,　C.-C.　Han,　M.　B.　Srivastava,　“Dynamic　Fine-Grain　Localization　in　Ad　Hoc　Networks　of　Sensors,”　In　Proceedings　of　the　Seventh　Annual　ACM/IEEE　International　Conference　on　Mobile　Computing　and　Networking　(Mobicom　2001),　July　2001.
[11]　I.F.　Akyildiz,　W.　Su,　Y.　Sankarasubramaniam,　E.　Cayirci,　“A　survey　on　sensor　networks,”　In　IEEE　Communication　Magazine,　40(8),　August　2002,　pp.　102-114.　BIBLIOGRAPHY　79
[12]　L.　Clare,　G.　Pottie,　J.　Agre,　“Self-organizing　distributed　sensor　networks,”　In　The　International　Society　for　Optical　Engineering,　Orlando,　FL,　April　1999,　pp.　229-237.
[13]　G.　Pei,　C.　Chien,　“Low　power　TDMA　in　large　wireless　sensor　networks,”　In　Military　Communications　Conference,　2001.
[14]　K.　Sohrabi,　G.　J.　Pottie,　“Performance　of　a　novel　selforganization　protocol　for　wireless　ad-hoc　sensor　networks,”　In　IEEE　Vehicular　Technology　Conference,　volume　2　,　1999,　pp.　1222-1226.
[15]　Dragos　Niculescu,　Badri　Nath,　“Ad　Hoc　Positioning　System　(APS)　Using　AOA,”　GLOBECOM　2001　-　IEEE　Global　Telecommunications　Conference,　No.　1,　NOV　2001,　pp.　2926-2931.
[16]　N.　Malhotra,　M.　Krasniewski,　C.　Yang,　S.Bagchi,　W.　Chappell,　“Location　Estimation　in　Ad-Hoc　Networks　with　Directional　Antennas,”　Proceeding　of　the　2005IEEE　International　Conference　on　Distributed　Computing　Systems　(ICDCS’05),　June　2005,　pp.　633-642.
[17]　Sylvia　Ratnasamy,　Brad　Karp,　Scott　Shenker,　Deborah　Estrin,　Ramesh　Govindan,　Li　Yin,　Fang　Yu,　“Data-Centric　Storage　in　Sensornets　with　GHT,　A　Geographic　Hash　Table,”　Proc.　Mobile　Networks　and　Applications　(MONET),　the　Journal　of　SPECIAL　ISSUES　on　Mobility　of　Systems,　Users,　Data　and　Computing,　August　2003,　pp.　427-442.
[18]　Yingqi　Xu,　Julian　Winter,　Wang-Chien　Lee,　“Prediction-based　Strategies　for　Energy　Saving　in　Object　Tracking　Sensor　Networks,”　Proceeding　of　the　2004　IEEE　International　Conference　on　Mobile　Data　Management,　January　2004,　pp.　346-357.　BIBLIOGRAPHY　80
[19]　Wei-Peng　Chen,　Jennifer　C.　Hou,　Lui　Sha,　“Dynamic　Clustering　for　Acoustic　Target　Tracking　inWireless　Sensor　Networks,”　Mobile　Computing,　IEEE　Transactions　on　Volume:03,　Issue:3　,　July　2004,　pp.　258-271.
[20]　Julian　Winter,　Wang-Chien　Lee,　“KPT:　a　dynamic　KNN　query　processing　algorithm　for　location-aware　sensor　networks,”　Proceeedings　of　the　1st　international　workshop　on　Data　management　for　sensor　networks,　2004,　pp.　119-124.
[21]　M.　Demirbas,　“Peer-to-peer　spatial　queries　in　sensor　networks,”　Proceedings　of　the　3rd　IEEE　International　Conference　on　Peer-to-Peer　Computing,　Linkoping,　Sweden,　September　2003.
[22]　Julian　Winter,　Yingqi　Xu,　Wang-Chien　Lee,　“Energy　Efficient　Processing　of　K　Nearest　Neighbor　Queries　in　Location-aware　Sensor　Networks,”　Proceeedings　of　the　2nd　Annual　International　Conference　on　Mobile　and　Ubiquitous　Systems　(MobiQuitous　2005),　17-21　July　2005,　San　Diego,　California,　USA,　pp.　281-292.
[23]　Samuel　Madden,　Michael　J.　Franklin,　Wei　Hong,　Joseph　M.　Hellerstein,　“TAG:　a　Tiny　AGgregation　Service　for　Ad-Hoc　Sensor　Networks,”　Proceedings　of　the　5th　Symposium　on　Operation　Systems　Design　and　Implementation　(OSDI’02),　December　2002,　pp.　131-146.
[24]　Yuxia　Yao,　Xueyan　Tang,　Ee-Peng　Lim　,“In-Network　Processing　of　Nearest　Neighbor　Queries　for　Wireless　Sensor　Networks,”　Proceedings　of　the　11th　International　Conference　on　Database　Systems　for　Advanced　Applications　(DASFAA’06),　April　2006.　BIBLIOGRAPHY　81
[25]　Adam　Smith,　Hari　Balakrishnan,　Michel　Goraczko,　Nissanka　Priyantha,　“Tracking　moving　devices　with　the　cricket　location　system,”　Proceedings　of　the　2nd　international　conference　on　Mobile　systems,　applications,　and　services　(MobiSys’04),　June　6-9　2004,　pp.　190-202.
[26]　Jianliang　Xu,　Xueyan　Tang,　Wang-Chien　Lee,　“EASE:　An　Energy-　Efficient　In-Network　Storage　Scheme　for　Object　Tracking　in　Sensor　Networks,”　Proceedings　of　the　Second　Annual　IEEE　Communications　Society　Conference　on　Sensor　and　Ad　Hoc　Communications　and　Networks　(SECON’05),　September　26-29　2005.
[27]　Jason　Hill,　“System　Architecture　for　Wireless　Sensor　Networks,”　PhD　thesis,　University　of　California,　Berkeley,　Spring　2003.
[28]　Markde　Berg,　Otfried　Schwarzkopf,　Marcvan　Kreveld,　Mark　Overmars,　“Computational　Geometry:　Algorithms　and　Applications,　chapter　7,”　Springer-Verlag,　2000.
[29]　Glenn　Iwerks,　Hanan　Samet,　and　Ken　Smith,　“Continuous　K-Nearest　Neighbor　Queries　for　Continuously　Moving　Points　with　Updates,”　in　International　Conference　on　Very　Large　Data　Bases,　Berlin,　Germany,　September　9-12　2003.
[30]　Yufei　Tao,　Dimitris　Papadias,　and　Qiongmao　Shen,　“Continuous　Nearest　Neighbor　Search,”　in　International　Conference　on　Very　Large　Data　Bases,　Hong　Kong,　China,　August　20-23　2002,　pp　279-290.
[31]　Nick　Roussopoulos,　Stephen　Kelley,　and　Fr’ed’eric　Vincent,　“Nearest　neighbor　queries,”　in　Proceedings　of　ACM　Sigmod,　1995,　pp　71-79.　BIBLIOGRAPHY　82
[32]　Simonas　Saltenis,　Christian　S.　Jensen,　Scott　T.　Leutenegger,　and　Mario　A.　Lopez,　“Indexing　the　Positions　of　Continuously　Moving　Objects,”　in　SIGMOD　Conference,　2000,　pp　331-342.
[33]　A.　Guttman,　“R-Trees:　A　Dynamic　Index　Structure　for　Spatial　Searching,”　in　ACM　SIGMOD　Conf,　1984,　pp　47-57.
[34]　Zhexuan　Song　and　Nick　Roussopoulos,　“K-Nearest　Neighbor　Search　for　Moving　Query　Point,”　in　Proceedings　of　7th　International　Symposium　on　Advances　in　Spatial　and　Temporal　Databases,　LNCS2121,　Redondo　Beach,　CA,　USA,　July　12-15　2001,　pp　79-96.
[35]　P.　Bonnet,　J.　Gehrke,　and　P.　Seshadri,　“Towards　sensor　database　systems,”　in　In　Proceedings　of　MDM,　Hong　Kong,　China,　January　2001,　pp　3-14.
[36]　R.　Govindan,　J.　Hellerstein,　W.Hong,　S.　Madden,　M.　Franklin,　and　S.　Shenker,　“The　sensor　network　as　a　database,”　in　Technical　Report　02-771,　Computer　Science　Department,　University　of　Southern　California,　September　2002.
[37]　Hanan　Samet,　“The　Design　and　Analysis　of　Spatial　Data　Structures,”　Addison-Wesley,　ISBN　0-201-50255-0,　1990.
[38]　Hanan　Samet,　“Application　of　Spatial　Data　Structure,”　Addison-　Wesley,　ISBN　0-201-50300-X,　1990.

校內：2008-08-02公開
校外：2008-08-02公開

簡易檢索 / 詳目顯示

相關論文