Telsiz, tasarsız ve duyarga ağlar için kaynak-başlatmalı coğrafi veri akış yöntemi
Tasarsız (ad hoc) ve duyarga (sensör) ağlar, altyapısız ağlar olduğu için altyapılı ağlarda bol miktarda bulunan enerji, işlemci, bellek, bandgenişliği gibi kaynaklar kısıtlıdır ve özenle tüketilmelidir. Ağ elemanlarının boyutlarının çok küçük olması, enerjiyi en kısıtlı kaynak yapmaktadır. Ancak, kaynak ile varış arasında veri akışının sağlanması için kullanılan yöntemler enerji tüketimini arttırmaktadır. Bu nedenle, literatürde enerji-etkin yönlendirme protokolleri sunulmuştur. Bu protokollerden, coğrafi yer bilgisine dayanarak yönlendirme yapan protokoller, diğerlerine göre daha yüksek başarıma ve performans değerlerine sahiptir. Bu çalışmada, Durumsuz Ağırlıklı Yönlendirme (DAY) isimli bir özgün kaynak-başlatmalı veri akış tekniği sunulmaktadır. Düğümler sadece kendi sanal coğrafi yer bilgilerini bilmekte, ağ topololoji bilgisine ihtiyaç duymamaktadır. Her düğüm kendi ağırlığını hesaplamaktadır. Başlangıçta bu değer varışa olan mesafedir. Düğümler kendilerine gelen paketlerin içindeki ağırlık bilgilerine bakarak paketi tekrar göndermeye veya düşürmeye karar vermektedir. Bu karşılaştırma işlemi durumsuz olma özelliğini sağlamaktadır. Ağırlık parametresi sadece yer bilgisini içerebildiği gibi düğümün kalan enerjisi gibi Servis Kalitesi parametre bilgisini de içerebilir. Servis Kalite bilgisi sistemin yaşamömrünü arttırmaya yöneliktir. Durumsuz olma özelliği ile de, yönlendirme tablosu tutulan algoritmalarda görülen iletişim yükü büyük oranda azalmaktadır. DAY, aynı zamanda, güvenirliği sağlayan ve gerçek-zamanlı veri için de gerekli olan çoklu-yollar veya örülü çoklu-yollar kullanır. Tekrar-gönderimlerde eşik değerlerinin kullanımı, sistemde esnek ve enerji etkin bir veri akışı sağlar. Aynı zamanda, DAY, MACkatmanından bağımsız çalışan ilk durumsuz coğrafi yönlendirme tekniğidir.
Source-initiated geographical data flow approach for wireless ad hoc and sensor networks
Routing without tables can be achieved by using location information of the nodes retrieved from GPS (Global Positioning System) or by applying a localization algorithm. In geographic routing protocols, nodes know their actual or relative positions with respect to a reference point, and share this information with immediate neighbour nodes for routing process. Geographic routing protocols use only local topology information and do not have any update overhead. Therefore, they provide scalability in mobile networks with respect to conventional routing protocols. Geographic routing protocols use greedy scheme or beaconless scheme for routing. In greedy schemes, nodes select the best next node on the route by using the local topology information. Collecting local topology information in greedy schemes consumes more energy than beaconless schemes due to reduced transmissions in the latter one. On the other hand, beaconless routing protocols in the literature propose solutions to be implemented at the MAC (Medium Access Control) layer. In those solutions, RTS (Request To Send) and CTS (Clear To Send) packets are also used for implementing routing protocol that increases the complexity of the MAC layer. However, sorting routing problem at the MAC layer is against the well-defined communication architecture. Besides that, those solutions become dependent to the MAC layer they use. In this study, a novel stateless data flow approach and routing algorithm for wireless sensor networks is proposed which is completely MAC-layer independent. Nodes do not have to be aware of local or global topology information. Routing is achieved without keeping tables. Nodes’ geographical positions are sufficient for routing process. A new metric called weight that is derived from nodes’ own position is used in routing process. The position can be either geographical or relative to a reference point system wide. Instead of the position, the weight value of the transmitting node is inserted into the packet. Each node on the route involves in routing process by considering its weight and the information in the received packet. To limit the number of forwarding nodes, a threshold is set in terms of the weight metric. On a packet receive; a node broadcasts the packet if its weight is between the weights of the transmitting node and the destination node and if also its weight difference greater than the threshold value. Besides that, decision to transmit includes QoS parameters such as powerleft at the node to keep energy-limited nodes out of the route. The threshold value can be adjusted to save energy by limiting the number of retransmitting nodes. The threshold value can also be adjusted for reliability. More relaying in number causes the data to flow over multiple paths. Data transportation over multiple paths provides reliability. Reliability requirements challenge with the energy saving requirements. Therefore, threshold value can be used to balance these requirements as needs. Thirdly, the threshold value can be adjusted for void recovery. In case of void detection, the transmitting node decreases the threshold value allowing more nodes to be in data flow algorithm. By this way, nodes that may circumvent the void are forced to relay the data packets. Fourthly, the threshold value should be adjusted according to the node density in the network. In dense networks, the threshold value can be set to be high by default to limit the retransmitting nodes. In non-dense networks, the threshold value can be set to be low. The proposed algorithm, SWR, has the following properties: • SWR provides scalability by not using routing tables, and by not beaconing. • SWR simplifies routing process by using a weight metric and designing an appropriate algorithm for routing. • SWR decreases calculations, delay, and resource requirements (such as processor and memory) at nodes by using weight metric. • SWR decreases energy consumption by not beaconing, by using position-based routing based on threshold and considering the energy levels of the nodes. • SWR provides reliability by using multipaths. • SWR executes routing process completely in network layer, independent from the MAC layer used below.
___
- Akkaya K., Younis, M., (2005). A Survey of Routing Protocols in Wireless Sensor Networks, in the Elsevier Ad Hoc Network Journal, 3, 3, 325-349.
- Araujo, F., Rodrigues, L., (2006). Survey on Position-Based Routing, TR-01, Dept. of Comp. Science, University of Lisbon, Jun.
- Avin, C., (2005). Fast and efficient restricted delaunay triangulation in random geometric graphs, Workshop on Combinatorial and Alg. Aspects of Networking, Waterloo, Ontario, Canada, 13-14 Aug.
- Chawla, M., Goel, N., Kalaichelvan, K., Nayak, A., Stojmenovic, I., (2006). Beaconless position based routing with guaranteed delivery for wireless Ad-Hoc and sensor networks, IFIP 1st Int. Conf. on Ad-Hoc Networking at 19th IFIP World Computer Congress, Santiago, Chile, 20- 25 Aug.
- Fuessler, H., Widmer, J., Kasemann, M., Mauve, M., (2003). Beaconless position-based routing for mobile Ad-Hoc networks, TR-03-001, Dept. of Comp. Science, University of Mannheim, Feb.
- Giordano, S., Stojmenovic, I., Blazevic, L., (2004). Position based routing algorithms for Ad Hoc Networks: A Taxonomy, in: ‘Ad Hoc Wireless Networking’, Cheng, X., Huang, X. and Du, D.Z. (eds.), Kluwer, 103-136.
- Heissenbuttel, M., Braun, T., (2003). A novel position-based and beacon-less routing algorithm for mobile Ad Hoc Networks, 3rd Workshop on Applications and Services in Wireless Networks, ASWN’03, 197-210, Bern, 2-4 Jul.
- Heissenbuttel, M., Braun, T., Walchli, M., Bernoulli, T., (2006). Optimized stateless broadcasting in wireless multi-hop networks, IEEE Infocom 2006, Barcelona, Spain, 23-29 Apr.
- Karp, B., Kung, H.T., (2000). GPSR: Greedy perimeter stateless routing for wireless networks. 6th Annual International Conference on Mobile Computing and Networking, Mobicom 2000, Boston, Massachusetts, 6-11 Aug.
- Mauve, M., Widmer, J., Hartenstein, H, (2001). A Survey on Position-Based Routing in Mobile Ad- Hoc Networks, IEEE Network Magazine, 15, 6, 30-39, November.
- Son, D., Helmy, A., Krishnamachari, B., (2004). The effect of mobility-ınduced location errors on geo.routing in mobile ad hoc and sensor networks: Analysis and ımprovement using mobility prediction, IEEE Transactions on Mobile Computing, 3, 3, Jul-Sep, 233-245.
- Soyturk, M., Altilar, T., (2006). The challenges and the approaches for the geographic routing protocols in wireless sensor networks, IEEE TEHOSS, İstanbul, Oct.
- Yu, Y., Hong, B., Prasanna, V.K., (2005). On communication models for algorithm design in networked sensor ssytems: A case study, Elsevier Pervasive and Mobile Computing Journal, 1, 1, 95-122,Mar.