Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19909
標題: 在無線感測與隨意網路上服務搜索機制之研究
The Study of Service Discovery Schemes in Wireless Sensor and Mobile Ad-hoc Networks
作者: 陳石坤
Chen, Shyr-Kuen
關鍵字: 任播機制;控制閘道;Any-K服務機制;恢復點;虛擬位址儲存區域;空間知覺
出版社: 資訊科學與工程學系
引用: References [1] M. Al-Harbawi, M. F. A. Rasid, and N. K. Noordin, "Improved Tree Routing (ImpTR) Protocol for ZigBee Network," International Journal of Computer Science and Network Security, vol.9, no.10, Oct. 2009. [2] S. Basagni, I. Chlamtac, V.R. Syrotiuk, and B.A. Woodward, "A distance routing effect algorithm for mobility (dream)," Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, Dallas, Texas, pp.76-84, Oct. 1998. [3] E. Basturk, R. Engel, R. Haas, V. Peris, and D. Saha, "Using Network Layer Anycast for Load Distribution in the Internet," IBM Technology Report, 1997. [4] S. Bhattacharjee, M. H. Ammar, E. W. Zegura, V. Shah, and Z. Fei, "Application-layer Anycasting," Proceedings of IEEE Computer and Communications Societies Conference (INFOCOM ''97), Japan, Apr. 1997. [5] M. Chen and W. Mao, "Anycast by DNS Over Pure IPv6 Network," Project Report, University of California Berkeley, 2001. [6] S.K. Chen, T.Y. Chen, and P.C. Wang, "Spatial aware location service for mobile ad hoc networks," Proceedings of the IEEE 13th International Symposium on Consumer Electronics, Kyoto, Japan, pp.164-168, May 2009. [7] R. R. Choudhury and N. H. Vaidya, "MAC-layer Anycasting in Wireless Ad Hoc Networks," National Science Foundation (NSF) Technical Report, Jul. 2003. [8] D. Cypher and N. Chevrollier and N. Montavont and N. Golmie, " Prevailing over Wires in Healthcare Environments: Benefits and Challenges," IEEE COMMUNICATIONS MAGAZINE, vol. 44, no. 4, pp. 56-63, 2006. [9] S.M. Das, H. Pucha, and Y.C. Hu, "Performance comparison of scalable location services for geographic ad hoc routing," Miami, Florida, pp.1228-1239, Mar. 2005. [10] S. Deering and R. Hinden, "IP Version 6 Addressing Architecture," IETF RFC 2373, Jul. 1998. [11] S. Doi, S. Ata, H. Kitamura, M. Murata, and H. Miyahara, "Protocol Design for Anycast Communication in IPv6 Network," Proceedings of IEEE Pacific Rim Conference (PACRIM ''03), vol. 1, pp. 470-473, Aug. 2003. [12] C. R. Dow, S. F. Hwang, W. L. Horng, J. H. Lin, and K. T. Chen, "A Cluster-based Virtual Backbone Establishment and Maintenance for Ad-hoc Wireless Networks," Proceedings of 7th Mobile Computing Workshop, pp. 123-129, Mar. 2001. [13] Z. Fei, S. Bhattacharjee, E. W. Zegura, and M. Ammar, "A Novel Server Selection Technique for Improving the Response Time of a Replicated Server," Proceedings of IEEE Computer and Communications Societies Conference (INFOCOM ''98), 1998. [14] S. Giordano and M. Hamdi, "Mobility management: The virtual home region," Tech. Rep. SSC/1999/037, University of Wisconsin - Madison Computer Sciences Department, Oct. 1999. [15] Z.J. Haas and B. Liang, "Ad hoc mobility management with uniform quorum systems," IEEE/ACM Transactions on Networking, vol.7, no.2, pp.228-240, Apr. 1999. [16] K. M. Hanna, B.N. Levine, and N. Natarajan, "Evaluation of a Novel Two-step Server Selection Metric," Proceedings of International Conference on Network Protocols (IEEE ICNP ''01), Nov. 2001. [17] T.C. Hou and V. Li, "Transmission range control in multihop packet radio networks," IEEE Transactions on Communications, vol.34, no.1, pp.38-44, Jan. 1986. [18] H. Ikeda, H. Miura, K. Nishimura, and M. K. Yamamoto, "A Network-supported Server Load Balancing Method: Active Anycast," IEICE Transaction Communication, vol. E84.B, no. 6, Jun. 2001. [19] C. Intanagonwiwat and D. D. Lucia, "The Sink-based Anycast Routing Protocol for Ad Hoc Wireless Sensor Networks," Technical Report 99-698, Department of Computer Science, University of Southern California, Jan. 1999. [20] W. Jia and D. Xuan, "Distributed Admission Control for Anycast Flows with QoS Requirements," Proceedings of IEEE International Conference on Distributed Computing Systems, 2001. [21] W. Jia, D. Xuan, W. Zhao, and H. W. Zhu, "A Routing Protocol for Anycast Message," IEEE Transactions on Parallel and Distributed Systems, vol. 11, no. 6, pp. 571-588, Jun. 2000. [22] D.B. Johnson and D.A. Maltz, "Dynamic source routing in ad hoc wireless networks," Mobile Computing, pp.153-181, Kluwer Academic Publishers, 1996. [23] B. 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, pp.243-254, Aug. 2000. [24] D. Katabi and J. Wroclawski, "A Framework for Scalable Global IP Anycast (GIA)," Proceedings of Special Interest Group on Data Communications (SIGCOMM ''00), Stockholm, Sweden, 2000. [25] T. Kim, D. Kim, N. Park, S. Yoo, and T. S. Lopez, "Shortcut Tree Routing in ZigBee Networks," Proceedings of ISWPC ''07, Feb. 2007. [26] Y.B. Ko and N.H. Vaidya, "Location-aided routing (lar) in mobile ad hoc networks," Wireless Networks, vol.6, no.4, pp.307-321, Jul. 2000. [27] J. Li, J. Jannotti, D.S.J. De Couto, D.R. Karger, and R. Morris, "A scalable location service for geographic ad hoc routing," Proceedings of the 6th annual international conference on Mobile computing and networking, Boston, Massachusetts, pp.120-130, Aug. 2000. [28] T. Li, S. Hazra, and W. Seah, "A position-based routing protocol for metropolitan bus networks," Proceedings of the IEEE 61st Semiannual Vehicular Technology Conference, Stockholm, Sweden, pp.2315-2319, May 2005. [29] C. R. Lin and M. Gerla, "Adaptive Clustering for Mobile Wireless Networks," IEEE Journal on Selected Areas in Communications, vol. 15, no. 7, pp. 1265-1275, Sep. 1997. [30] J. H. Lin, C. R. Dow, S. F. Hwang, and Y. W. Wang, "An Efficient Distributed Clustering Scheme for Ad-hoc Wireless Networks," Proceedings of 6th Mobile Computing Workshop, Mar. 2000. [31] X. Lu and J. Wang, "Route Recovery Based on Anycast Policy in Mobile Ad-hoc Networks," Proceedings of International Conference Communication Technology (ICCT ''03), Apr. 2003. [32] J. Luo and J.P. Hubaux, "A survey of inter-vehicle communication," tech. rep., School of Computer and Communication Sciences, EPFL, 2004. [33] M. Mauve, A. Widmer, and H. Hartenstein, "A survey on position-based routing in mobile ad hoc networks," IEEE Network, vol.15, no.6, pp.30-39, Jun. 2001. [34] K. Mehlhorn, "A Faster Approximation Algorithm for the Steiner Problem in Graphs," Information Processing Letters, vol. 27, pp. 125-128, Mar. 1988. [35] T. Mendez, W. Milliken, and C. Partridge, "Host Anycasting Service," IETF RFC 1546, Nov. 1993. [36] D. L. Mills, "The network time protocol (NTP) distribution," http://www.eecis.udel.edu/˜mills/ntp/html/. [37] H. Miura and M. K. Yamamoto, "Server Selection Policy in Active Anycast," IEICE Transaction Communication, vol. E84.B, no. 10, Oct. 2001. [38] F.L. Mobile, C.T. Cheng, H.L. Lemberg, S.J. Philip, E.V.D. Berg, and T. Zhang, "Slalom: A scalable location management scheme for large mobile ad-hoc networks," Proceedings of Wireless Communications and Networking Conference, Orlando, Florida, pp.574-578, Mar. 2002. [39] R. Nelson and L. Kleinrock, "The spatial capacity of a slotted ALOHA multihop packet radio network with capture," IEEE Transactions on Communications, vol.32, no.6, pp.684-694, Jun. 1984. [40] J. Nzouonta, N. Rajgure, G. Wang, and C. Borcea, "Vanet routing on city roads using real-time vehicular traffic information," IEEE Transactions on Vehicular Technology, vol.58, no.7, pp.3609-3626, Sep. 2009. [41] M. Oe and S. Yamaguchi, "Implementation and Evaluation of IPv6 Anycast," Proceedings of 10th Annual Internet Society Conference, Yokoham, Japan, Jul. 2000. [42] C.E. Perkins and P. Bhagwat, "Highly dynamic destination sequenced distance-vector routing (dsdv) for mobile computers," SIGCOMM Computer Communication Review, vol.24, no.4, pp.234-244, Apr. 1994. [43] C.E. Perkins and E.M. Royer, "Ad-hoc on-demand distance vector routing," Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, Louisiana, pp.90-100, Feb. 1999. [44] S. Philip and C. Qiao, "Elf: effcient location forwarding in ad hoc networks, " Proceedings of the IEEE Global Telecommunications Conference, vol. 2, pp. 913-918, 2003. [45] B.C. Seet, Y. Pan, W.J. Hsu, and C.T. Lau, "Multi-home region location service for wireless ad hoc networks: An adaptive demand-driven approach," Proceedings of the Second Annual Conference on Wireless On-demand Network Systems and Services, St. Moritz, Switzerland, pp.258-263, Jan. 2005. [46] I. Stojmenovic, "Home agent based location update and destination search schemes in ad hoc wireless networks," tech. rep., 1999. [47] I. Stojmenovic and B. Vukojevic, "A routing strategy and quorum based location update scheme for ad hoc wireless networks," tech. rep., 1999. [48] H. Takagi and L. Kleinrock, "Optimal transmission ranges for randomly distributed packet radio terminals," IEEE Transactions on Communications, vol.32, no.3, pp.246-257, Mar. 1984. [49] C. H. Tsai, M. S. Pan, Y. C. Lu, and Y. C. Tseng, "Self-Learning Routing for ZigBee Wireless Mesh Networks," IEEE Asia-Pacific Wireless Communications Symposium (APWCS), 2009. [50] J. Wang, Y. Zheng, and W. Jia, "An AODV-based Anycast Protocol in Mobile Ad Hoc Network," Proceedings of 14th IEEE 2003 International Symposium on Personal, Indoor and Mobile Radio Communication, vol. 1, pp. 221-225, Sep. 2003. [51] S. Weber and L. Cheng, "A Survey of Anycast in IPv6 Networks," IEEE Communications Magazine, vol. 42, no. 1, pp. 127-132, Jan. 2004. [52] S.C.M. Woo and S. Singh, "Scalable routing protocol for ad hoc networks," Wireless Networks, vol.7, no.5, pp.513-529, Sep. 2001. [53] Z. D. Wu, C. Noble, and D. Huang, "Optimal Video Distribution Using Anycasting Service," Proceedings of Internet Global Summit (INET ''99), Jun. 1999. [54] X. Wu, "Vpds: Virtual home region based distributed position service in mobile ad hoc networks," Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, Columbus, Ohio, pp.113-122, Jun. 2005. [55] J. Yoon, M. Liu, and B. Noble, "Random waypoint considered harmful," Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, pp.1312-1321, Apr. 2003. [56] M. G. Zapata. "Shortcut detection and route repair in ad hoc networks," Pervasive Computing and Communications Workshops, IEEE International Conference on, pp. 237-242, 2005. [57] "Jn5139 datasheet." http://www.jennic.com/. [58] OMNeT++ Community Site." http://www.omnetpp.org/, Accessed 2005. [59] "TI MSP430F1611 datasheet," http://focus.ti.com/docs/toolsw/folders/ print/msp430-3p-tegh-cm1611-devbd.html#Features. [60] "Ubec UZ2400 datasheet," http://www.coretk.com/CataLog/cata img/FILE/183366731/UBEC/168/168 176 1146034480.pdf.
摘要: 
在無線網路中對於資料的傳遞,主要可分為以拓撲為基礎(topology-based)的路由,和以位址資訊為基礎(position-based)的路由協定。以拓撲為基礎的路由方式其種種缺陷主要來自於節點之間並沒有相對位置與方向等資訊,所以必須以對整個網路做探測訊息廣播的方式來建立彼此的路由資訊,當在尋找網路資源時經常依賴廣播和群播機制取得資訊,因此會造成大量的資料流。相對以位址資訊為基礎的路由協定使用了節點的位址(location)作為封包遞送方向的重要依據,若在目標節點的位址已知的情況下,可以有方向性地限制廣播的範圍,可大幅減少對整個網路做氾濫式廣播和無須維護路由資訊。但有一挑戰是當節點要送出封包之前,必須要先知道其目標節點的位址,才能完成封包遞送的決策,在不使用集中管理設施的情況下,最簡單的方式就是每個節點都須週期性地將自己的位址資訊以氾濫廣播的方式傳送給其他所有節點,如此同樣會面臨廣播成本浩大的問題。有鑑於此,本論文將探討在無線網路中提供一個有效服務資源的搜索機制(The Study of Service Discovery Schemes in Wireless Sensor and Mobile Ad-hoc Networks),於SDS中將探討以下三個主題:(1)建立低流量搜索任播樹機制有效控制搜索封包的轉遞傳輸、(2)提供穩健傳送機制及(3)建立分散式位址服務策略。
為了要解決上述所提topology-based問題,能夠減少封包傳遞又可確保資源獲得,我們提出一個任播(Anycast)機制,利用建立控制閘道(ControlGate)的做法,允許最近一個服務資源或路由器來作回應,不僅可有效減少遞送需求封包(RREQ)至整個網路上,更可大量減少因重覆收到需求封包所產生的回應資料流(RREP)。另外我們機制也支援Any-K服務機制,允許分配K個服務資源回應至傳送端,不僅可達到備援資源搜尋且有效減少遞送封包。
雖然任播機制可以有效減少網路封包的傳遞,但對於無線網路資料傳遞的不穩定性一直是該面臨的挑戰,因此本論文再提出以控制閘道節點為恢復點(Recovery Point),建立資料恢復和重新路由機制,達到資料穩健的傳遞。當傳遞的路徑或節點產生異常導致傳輸中斷時,於傳輸路徑的最近控制閘道節點將選擇下一接收節點(Next Hop),並恢復中斷前相關封包傳遞,對原始傳送者無須再尋找路徑或重傳尚未完成封包,因此可確保資料的傳遞且可縮短因網路傳遞不穩定所造成的延遲。
與其上述以拓撲為基礎(Topology-based)的路由協定相比之下,如能得知目標節點的位址,則路由協定將以位址資訊為基礎(Position-based),不需要持續維護路徑和產生大量的訊息廣播,即可擁有好的規模可變性(Scalability)以及較低的控制訊息負載量。而位址服務(Location Service)則是此類方法最重要的核心,在傳送封包之前,需要由位址服務的機制來提供目標節點的位址,才能將封包正確送達到目標節點。 因此本論文提出二個機制:(1)Distributed Virtual Home Region with Spatial Awareness (DVHR-SA),以VHR為基礎的位址服務方法,利用節點自身位址反映出的空間位置來選擇不同的VHR作更新與詢問,達到縮短更新與查詢路徑的長度。(2) An Efficient Location Forwarding with Shortcut Schemes (ELFS), 以ELF為基礎的位址服務方法,採用直接廣播更新的方式和具有方向性之往前遞送方式,可降低整體網路負載的流量。
最後,展示實驗結果(1) 利用建立的任播樹和閘道控制機制,經實驗結果其數據顯示和傳統搜尋機制Flooding和Multicast作比較,可大幅減少封包的遞送和回應封包,尤其是當網路節點一多且提供資源也多時,傳統搜尋機制將會造成大量的網路資料流,而我們的機制不僅可更快速獲得服務資源,且不會受所提供的服務資源多而造成大量的網路資料流。(2) 同時在ZigBee無線網路環境中提供任播機制,並加強資料傳輸的穩健性,經實驗結果其資料傳遞時間和資料重傳或重新路由時間皆比傳統搜尋機制短,且可達到穩健資料傳輸。(3) 建立階層式的位址伺服器,有效提供位址資訊的更新與詢問,其實驗的結果顯示可縮短位址資訊更新與查詢路徑的長度。

Two types of ad-hoc routing protocols are proposed in the current work to address the issue of packet delivery: topology based and position based (or geographic based) routing protocols. In topology-based routing protocols, each node broadcasts control messages to build up routes directed to itself. It maintains a routing table to record routes to the other nodes in the mobile ad-hoc network (MANET). When searching for services on networks, the system often depends on the broadcast or multicast mechanism to acquire information, which usually results in a large overhead. In contrast to topology-based routing protocols, position-based routing protocols are considered widely as a potentially scalable routing solution because they do not need to maintain routing tables. However, the challenge involved is the determination by the source node of the position of the destination before sending a packet. The simplest method for retrieving a destination node''s position is flooding. However, the flooding-based approach usually leads to heavy signaling traffic and power consumption for the MANET. Hence, the present dissertation designs and proposes the Design and Implementation of a Services Discovery Scheme in Wireless Sensors and Mobile Ad-hoc Networks (SDS). Three issues on SDS needed to be considered: (1) construction of a minimum-cost tree for routing protocols, (2) development of a reliable transmission protocol, and (3) construction of efficient distributed location services with shortcut schemes for position-based routing.
To address topology-based routing protocol problems and to reduce the amount of request/reply packets, we propose an anycasting scheme for ad-hoc wireless networks. In this scheme, an anycast tree is established, and control-gates are used to reduce the control overhead. When a client node sends out a service request message to the anycast tree, the nearest or best server responds to the client. The other responses of service providers are discarded by the control-gate. Therefore, the anycasting scheme can reduce the control overhead and is suitable for large-scale ad-hoc wireless networks. It also supports any K service; it can be used for backup or fault tolerance.
Our proposed anycast scheme can reduce the control overhead. However, a major challenge involved is the unstable forwarding path in wireless networks. Therefore, we present a recovery point (RP) and rerouting scheme to increase the reliability of packet transmission. The retransmit packet work is handed over to the nearest RP node by the receiver, and the sender does not need to retransmit the lost packets. The transmission path is rebuilt from the last node before the failure link. Therefore, the latency of path recovery is shorter than that for unicast-based approaches that must rebuild their path from the source node.
In the current literature, position-based routing protocols are regarded to have better scalability and lower control overhead than topology-based routing protocols. Location services are the most critical part of position-based routing protocols, so we present two multi-home-region schemes. First is the Distributed Virtual Home Region with Spatial Awareness (DVHR-SA) scheme, which aims to improve the performance of location service. This scheme selects different update and query procedures adaptively according to the location of the source node. Second is the Efficient Location Forwarding with Shortcuts (ELFS) scheme, which uses the idea of shortcut to decrease the frequency of global updates and has packet forwarding with direction awareness. This scheme aims to reduce the path lengths of messages and to improve the cost of transmitting location information.
Finally, experimental results are shown as follows. First, the anycast scheme can reduce the number of transmitted packets regardless of the number of service providers, service requests, and the required service providers in one service instance. Second, a reliable scheme also has the capability of fast rerouting. Therefore, a broken path can be recovered in a short latency, and the reliability of the transmitted packets can be ensured. Finally, the DVHR-SA and ELFS schemes shorten the lengths of the update, query, and reply paths. Both schemes also reduce the overall network message overhead.
URI: http://hdl.handle.net/11455/19909
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.