Title page for 92532002


[Back to Results | New Search]

Student Number 92532002
Author Zhone-Chen Shu(³\¥ò¨°)
Author's Email Address No Public.
Statistics This thesis had been viewed 1525 times. Download 10 times.
Department Executive Master of Computer Science and Information Engineering
Year 2004
Semester 2
Degree Master
Type of Document Master's Thesis
Language English
Title Search-Tree-Based Routing Algorithm on Wireless Sensor Networks
Date of Defense 2005-07-13
Page Count 79
Keyword
  • data source
  • flooding
  • Search tree
  • sensor network
  • Abstract For the progress in processing, memory, and radio techniques, sensor nodes with the integration of sensing, wireless communication, and computation have been developed. The network of such nodes can be coordinated to sense specific environmental phenomena such as thermo, light, and sound, etc. In this paper, a routing algorithm based on search tree is proposed to achieve efficient and real-time coordination. In general, the routing algorithm for sensor networks sends first query message from the sender to the data source node by flooding, for the lack of the location of the data source. Once the data source receives a message from the sender, the location information is generated in the sensor nodes among the sender and the data source. The data source then sends back the data with the location information to the sender. The proposed routing algorithm is able to support real-time transmissions for sensor networks. First, the tree-based sensor network is constructed. Then, a unique address is assigned to each node to build the tree as search tree. With the search tree architecture and the address assignment, sensor nodes decide the next hop for a message by node¡¦s address information. The proposed routing algorithm does not need to build up location information for each message transmission from the source node to the sender and thus messages can be delivered efficiently. In the simulation, the proposed algorithm performs well in both different network size and workload. The proposed algorithm is also implemented in the automatic parking system which is an application designed in sensor network.
    Table of Content 1.Introduction1
    1.1Overview1
    1.2Motivation and Contribution2
    1.3Thesis Organization4
    2.Related Work5
    2.1Directed Diffusion5
    2.2TreeCast7
    3.Search-Tree-Based Routing Algorithm10
    3.1Assumption10
    3.2Concept11
    3.3Tree Construction14
    3.3.1Communication Link to Graph14
    3.3.2Graph to Tree16
    3.4Address Assignment18
    3.4.1Prototype assignment18
    3.4.2Multiple Expansion Assignment20
    3.5Routing Messages22
    3.5.1Query and Response23
    3.5.2Response with Level Forwarding24
    3.6Tree Maintenance26
    3.6.1Protocol26
    3.6.2Node Addition27
    3.6.3Node Failure32
    4.Simulation Results and Discussions33
    4.1Goals, Metrics, and Methodology33
    4.2Network Size35
    4.3Workload38
    4.4Level Assignment42
    4.5Routing under Failures44
    4.6Maintenance49
    5.Application53
    5.1Auto Parking System Overview53
    5.2System Architecture53
    5.3Emulation58
    5.3.1Hardware58
    5.3.2Parking Lot Deployment to Search Tree60
    6.Conclusions and Future Work62
    References63
    Reference [1]I.F. Akyildiz, Weilian Su, Y. Sankarasubramaniam, and E. Cayirci, ¡§A survey on sensor network,¡¨ Communication Magazine IEEE, vol. 40, iss 8, pp. 102-114, Aug. 2002.
    [2]M. A. M. Vieira, C. N. Coelho. Jr, D.C. da Silva. Jr., and, J.M. da Mata, ¡§Survey on wireless sensor network devices,¡¨ Proceedings of IEEE Conference on Emerging Technologies and Factory Automation 2003, ETFA 2003, vol. 1, iss 6, pp. 537-533, 16-19 Sep. 2003.
    [3]S.Sense Wireless Sensors. http://www.digitalsun.com/html/products.html.
    [4]http://www.sensicast.com.
    [5]http://www.senera.com.
    [6]Ting Yan, Tian He, and John A. Stankovic, ¡§Differentiated surveillance for sensor networks,¡¨ Proceedings of the 1st International Conference on Embedded Networked Sensor System, pp. 51-62, 5-7 Nov. 2003.
    [7]W. Steveb Cornet, Jasmeet Chhabra, Mark Yarvis, and Laskshman Krishnamurthy, ¡§Experimental evaluation of synchronization and topology control for in-building sensor network applications,¡¨ Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications, pp. 38-49, 19 Sep., 2003.
    [8]Robert Szewczyk, Eric Osterwei, joseph Polastre, Michael Hamilton, Alan Mainwaring, and Deborah Estrin, ¡§Habitat monitoring with sensor networks,¡¨ Communications of the ACM, pp. 38-49, 19 Sep., 2003.
    [9]Lee Joo-Ho and H. Hashimoto, ¡§Controlling mobile robots in distributed intelligent sensor network,¡¨ IEEE transactions on Industrial Electronics, vol. 50, iss 5, pp. 890-902, Oct., 2003.
    [10]Choi. Jonghwa, Shin. Dongkyoo, and Shin. Dongil, ¡§Research and implementation of the context-aware middleware for controlling home applications,¡¨ International Conference on Comsumer Electronics, 2005, ICCE. 2005 Digest of Technical Papers, pp. 161-162, 8-12 Jan. 2005.
    [11]Anastassia Ailamaki, Christos Faloutos, Paul S. Fischbeck, Mitchell J. Small, and Jeanne VanBriesen, ¡§An environmental sensor network to determine drinking water quality and security,¡¨ ACM SIGMON Record, vol. 32, iss 4, pp. 47-52, Dec., 2003.
    [12]J-L C. Wu. and S-T Wang, ¡§Comparison of power saving schemes for sink nodes in wireless sensor networks,¡¨ Proceedings of the 18th International Conference on Advanced Information Networking and Applications, 2004, AINA 2004, vol. 2, pp. 339-342, 2004.
    [13]D-H Chane, H-H Han, K-S Lim, K-H Seo, K-H Won, W-D Cho, and S-H An, ¡§Power saving mobility protocol for sensor network,¡¨ Proceedings of the 2nd IEEE Workshop on Software Technologies for Future Embedded and Ubiquitous Systems, 2004, pp. 122-126, 11-12 May, 2004.
    [14]C. Guettier, G. Le Lann, and J.-F. Hermant, ¡§Ad hoc sensor networks, constraint programming and distributed agreement,¡¨ Proceedings of International Conference on Information Technology: Research and Education, 2003, ITRE 2003, pp. 286-290, 11-13 Aug., 2003.
    [15]M. Demirbas and H. Ferhatosmanoglu, ¡§Peer-to-peer spatial queries in sensor networks,¡¨ Proceedings of the 3rd International Conference on Peer-to-Peer Computing, 2003, pp. 32-39, 1-3 Sep., 2003.
    [16]S. Ray, D. Starobinski, A. Trachtenberg, and R. Ungrangsi, ¡§Robust location detection with sensor networks,¡¨ IEEE journal on Selected Areas in Communications, vol. 22, iss 6, pp. 1016-1025, Aug., 2004.
    [17]T.C. Karalar, S. Yamashita, M. Sheets, and I. Rabaey, ¡§An Integrated, low power localization system for sensor networks,¡¨ The 1st Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, 2004, MOBIQUITOUS 2004, pp. 24-30, 22-26 Aug., 2004.
    [18]J. Liu, Zhao Feng, and D. Petrovic, ¡§Information-directed routing in ad hoc sensor networks,¡¨ IEEE journal on Selected Areas in Communications, vol. 23, iss 4, pp. 851-861, Apr., 2005.
    [19]H. Sabbineni and K. Chakrabarty, ¡§Location-aided flooding: an energy- efficient data dissemination protocol for wireless sensor networks,¡¨ IEEE Transactions on Computers, vol. 54, iss 1, pp. 36-46, Jan., 2005.
    [20]I. Stojmenovic, A. Nayak, and J. Kuruvila, ¡§Design guidelines for routing protocols in ad hoc and sensor networks with a realistic physical layer,¡¨ IEEE Communications Magazine, vol. 43, iss 3, pp. 101-106, Mar., 2005.
    [21]J. N. Al-karaki and A. E. Kamal, ¡§Routing techniques in wireless sensor networks: a survey,¡¨ IEEE Wireless Communications, vol. 11, iss 6, pp. 6-28, Dec. 2004.
    [22]Jiang Qiangfeng and D. Manivannan, ¡§Routing protocols for sensor networks,¡¨ 1st IEEE Consumer Communications and Networking Conference, 2004, CCNC 2004, pp. 93-98, 5-8 Jan., 2004.
    [23]D. Niculescu, ¡§Communication paradigms for sensor networks,¡¨ IEEE Communications Magazine, vol. 43, iss 3, pp. 116-122, Mar., 2005.
    [24]D. Niculescu, ¡§Positioning in ad hoc sensor networks,¡¨ IEEE Network vol. 18, iss 4, pp. 24-29, Jul.-Aug. 2004.
    [25]C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, ¡§Directed diffusion for wireless sensor networking,¡¨ IEEE/ACM Transactions on Networking, vol. 11, pp. 2-16, Feb. 2002.
    [26]J. Kulik, W. R. Heinzelman, and H. Balakrishnan, ¡§Negotiation-based protocols for disseminating information in wireless sensor networks,¡¨ Wireless Networks, vol. 8, iss 2/3, pp. 169-185, 2002.
    [27]D. Braginsky and D. Estrin, ¡§Rumor routing algorithm for sensor networks,¡¨ Proceedings of the 1s Workshop on Sensor Networks and Applications, Atlanta, GA, USA, pp. 22-31, Oct. 2002.
    [28]Brad Karp and H.T. Kung, ¡§GPSR: greedy perimeter stateless routing for wireless networks,¡¨ Proceedings of the 6th annual international conference on Mobile computing and networking, Boston, Massachusetts, USA, pp. 243-254, 6-11, Aug., 2000.
    [29]S. P. Chaudhuri, S. Du, A. K. Saha, and D. B. Johnson, ¡§TreeCast: a stateless addressing and routing architecture for sensor networks,¡¨ Proceedings of the 18th International Parallel and Distributed Processing Symposium, pp. 221, 26-30 April, 2004.
    [30]T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, McGraw Hill Press, pp.449, 2001.
    Advisor
  • Li-Der Chou(©P¥ß¼w)
  • Files
  • 92532002.pdf
  • disapprove authorization
    Date of Submission 2005-07-22

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have dissertation-related questions, please contact with the NCU library extension service section.
    Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.