Theses supervised by Yrd. Doç. Dr. İbrahim Körpeoğlu
11 theses · İhsan Doğramacı Bilkent University
Bluetooth tabanlı sensor ağları için enerji etkin scatternetlerin oluşturulması
ABSTRACTCONSTRUCTING ENERGY EFFICIENT BLUETOOTHSCATTERNETS FOR WIRELESS SENSORNETWORKSSain SaginbekovM.S. in Computer EngineeringËSupervisor: Assist. Prof. Dr. Ibrahim Kürpeoğluo gAugust, 2004The improvements in the area of wireless communication and micro-sensor tech-nology have made the deployment of thousands, even millions, of low cost andlow power sensor nodes in a region of interest a reality. After deploying sensornodes in a target region of interest, which can be inaccessible by people, peoplecan collect useful data from the region remotely. The sensor nodes use wirelesscommunication and can collaborate with each other. However, sensor nodes arebattery powered and therefore they have limited energy and lifetime. This makesenergy as the main resource problem in sensor networks. The design process forsensor networks has to consider energy constraints as the main factor to extendthe lifetime of the network.The wireless technology used for communication among sensor nodes can af-fect the lifetime of the network, since diï¬erent technologies have diï¬erent energyconsumption parameters. Bluetooth, being low power and low cost, is a goodcandidate for being the underlying wireless connectivity technology for sensornetworks tailored for various applications. But in order to build a large networkof Bluetooth-enabled sensor nodes, we have to ï¬rst form a Bluetooth scatter-net. The topology of the Bluetooth scatternet aï¬ects the routing scheme to beused over that topology to collect and route informaton from sensor nodes to abase station. And routing scheme, in turn, aï¬ects how much energy is consumedduring transport of information. Therefore, it is important to build a Bluetoothscatternet wisely to reduce and balance the energy consumption, hence extendthe lifetime of a sensor network.In this thesis work, we propose a new Bluetooth scatternet formation algo-rithm to be used in Bluetooth-based sensor networks. Our algorithm is based oniiiivï¬rst computing a shortest path tree from the base station to all sensor nodes andthen solving the degree constraint problem so that the degree of each node in thenetwork is not greater than seven (a Bluetooth constraint). We also propose abalancing algorithm over the degree constrained tree to balance the energy con-sumption of the nodes that are closer to the base station. The closer nodes arethe nodes that will consume more energy in the network since all traï¬c has tobe forwarded over these nodes. Our simulation results show that our proposedalgorithm improves the lifetime of the network by trying to reduce the energyconsumed during data transfer and also by balancing the load among the nodes.Keywords: Wireless Sensor Networks, Bluetooth, Scatternet, Routing, ShortestPath Tree.
Bant genişliğini verimli kullanan bluetooth serpme ağlarının dağınık oluşturulması ve bakımı
ABSTRACTDISTRIBUTED CONSTRUCTION ANDMAINTENANCE OF BANDWIDTH-EFFICIENTBLUETOOTH SCATTERNETSMetin TekkalmazM.S. in Computer EngineeringËSupervisor: Assist. Prof. Dr. Ibrahim Kürpeoğluo gAugust, 2004Bluetooth is currently the mainstream technology used for short range wirelesscommunication due to its low power and low cost properties. In order to com-municate, Bluetooth enabled devices can form networks called piconets, whichconsist of at most eight members. To construct larger Bluetooth networks, whichare called scatternets, any number of piconets can be combined. Although pi-conet construction process is standardized by Bluetooth Special Interest Group,scatternet construction policies and algorithms are not yet clariï¬ed.There have been many solution proposals for the scatternet construction prob-lem each of which focuses on diï¬erent aspects of it like the eï¬ciency of the con-struction algorithm, ease of routing in the resulting scatternet and number ofpiconets that constitute it. Although various considerations came into picture,bandwidth eï¬ciency of the resulting scatternet topology, which depends on theplacement of nodes and communication demand among them, did not take muchattention.In this thesis, we provide a distributed and adaptive algorithm that constructsa scatternet and based on collected traï¬c ï¬ow information, modiï¬es it to min-imize the overall bandwidth usage. As consequences of eï¬cient use of availablebandwidth, reduce in average latency and total energy consumption as well asincrease in available bandwidth for new communication demand are also aimed.Moreover, performance of the proposed algorithm is presented, based on the eval-uation criteria described.Keywords: Bluetooth, Scatternet Construction, Bandwidth-Eï¬cient Topologies.iii
Kablosuz mobil tasarsız ağlarda gerçek zamanlı trafik desteği veren bağ durumu tabanlı isteğe dayalı yol atama protokolü
Wireless ad hoc networks have gained a lot of popularity since their intro-duction and as many wireless network interface cards provide support for ad hocnetworking, such networks have also seen real-life deployment for non-specializedpurposes. Wireless mobile ad hoc networks (MANETs) are currently the mostcommon type of ad hoc networks, and such networks are especially esteemed fortheir mobility support and ease of deployment due to their ad hoc nature. Asmost common network applications, such as the Web, FTP, email, and instantmessaging, are data-centric and do not operate under strict time constraints,MANETs have been deployed to enable such non-real-time applications in thepast. However, with the increasing use of real-time applications over ad hocnetworks, such as teleconferencing, VoIP, and security and tracking applicationswhere timeliness is of importance, real-time traï¬c support in multi-hop wirelessmobile ad hoc networks has become an issue.We propose an event-driven, link-state based, on-demand routing protocol toenable real-time traï¬c support in such multi-hop wireless mobile ad hoc net-works. Our protocol, which is named Elessar, is based on link-state topologydissemination, but instead of the more common periodic link-state messagingscheme, we employ event-driven link-state messages in Elessar, where topologychanges are the events of interest. Through such an approach, we aim to lower theoverhead of our protocol, especially for low-mobility cases, which is currently themost commonly encountered case with ad hoc networks deployed with machinesdirectly interacting with humans, such as PDAs and laptops. Due to its link-statenature, our protocol is able to support non-real-time traï¬c without any furtheraction. In order to support real-time traï¬c, however, we employ a direct costiiiivdissemination mechanism, which only operates on-demand when there are one ormore real-time ï¬ows in the network. We aim to provide soft quality-of-service(QoS) guarantees to real-time ï¬ows through intelligent path selection, withoutany resource reservation. We also aim to provide such QoS guarantees through-out the lifetime of a real-time ï¬ow, even in the face of node failures and mobility,by dynamic path adaptation during the lifetime of the ï¬ow. Elessar is able tosupport real-time and non-real-time traï¬c concurrently, as well as various diï¬er-ent types of concurrent real-time traï¬c, such as delay- and loss-sensitive traï¬c.Our protocol, therefore, does not aim to support a single type of real-time traï¬c,but rather a plethora of diï¬erent types of real-time traï¬c. Elessar is completelydistributed, dynamic and adaptive, and does not require the underlying MACprotocol to be QoS-aware.We analyse our design choices and the performance of our protocol throughrealistic simulation experiments conducted on the OMNeT++ discrete event sim-ulation platform, using the INET framework. We have used the IEEE 802.11bMAC protocol during our simulations and have employed the random waypointmobility model to simulate mobility. Our experimental results show that Elessaris able to eï¬ciently provide real-time traï¬c support for diï¬erent types of traf-ï¬c ï¬ows, even in the face of mobility. Our protocol operates best for small-to-medium-sized networks where mobility rates are low-to-medium. Once themobility rate exceeds a certain threshold, intelligent path selection cannot copesatisfactorily with the high dynamism of the environment and the overhead ofElessar exceeds acceptable levels due to its event-driven link-state nature.Keywords: Wireless ad hoc networks, routing protocol, real-time traï¬c support,quality-of-service (QoS).
Tasarsız ve algılayıcı ağlarda yer belirleme algoritmalarının değerlendirilmesinde kullanılan metrikler üzerine bir araştırma
In ad-hoc and sensor networks, the location of a sensor node making an observationis a vital piece of information to allow accurate data analysis. GPS is anestablished technology to enable precise position information. Yet, resource constraintsand size issues prohibit its use in small sensor nodes that are designed tobe cost efficient. Instead, most positions are estimated by a number of algorithms.Such estimates, inevitably introduce errors in the information collected from thefield, and it is very important to determine the error in cases where they leadto inaccurate data analysis. After all, many components of the application relyon the reported locations including decision making processes. It is, therefore,vital to understand the impact of errors from the applications? point of view. Todate, the focus on location estimation was on individual accuracy of each sensor?sposition in isolation to the complete network. In this thesis, we point out theproblems with such an approach that does not consider the complete networktopology and the relative positions of nodes in comparison to each other. Wethen describe the existing metrics, which are used in the literature, and also proposesome novel metrics that can be used in this area of research. Furthermore,we run simulations to understand the behavior of the existing and proposed metrics.After having discussed the simulation results, we suggest a metric selectionmethodology that can be used for wireless sensor network applications.
Kablosuz algılayıcı ağlarında paket önceliğine göre zamanlama ve güç yönetimi destekli gerçek zamanlı yönlendirme
Many wireless sensor network applications require real-time communication, and real-time applications require packets to reach destination on time. However, applications may send packets with different priorities and hence delay bounds for packets may vary significantly. Therefore packet differentiation in the network is essential for meeting the deadline requirements. We propose a routing protocol that supports real-time communication by utilizing transmit power adjustment in order to meet the deadline of urgent packets and use energy efficiently. Our protocol also provides packet scheduling and gives precedence to urgent packets. We have conducted experiments on our sensor network testbed to observe the effects of transmit power on end-to-end delay. As expected, increasing transmit power increases the range and link quality, and reduces the number of hops to reach destination. Therefore adjusting transmit power has a great effect on delivery time and can reduce the end-to-end delay. Our protocol, Real-time Routing with Priority Scheduling and Power Adjustment, uses different levels of transmit power for packets with different priorities. It sends urgent packets with maximum power to minimize end-to-end delay and lower priority packets with reduced power to save energy and balance the load on nodes. Simulation results show that our routing protocol increases the deadline meet ratio of packets and reduces the transmit energy spent per packet when compared to routing protocols that use fixed transmit power. Additionally, results indicate that our approach lessens the interference on sensor nodes that are caused by other transmissions and helps balancing the load on the nodes.
E-Sense: Kapalı alanlarda ortamı gözleme amaçlı kablosuz algılayıcı ağı test alanı ve sistemi
Wireless sensor networks consist of small, smart and battery-powered devicessuitable for widespread deployment to monitor an environment by taking physicalmeasurements. Wireless sensor nodes are deployed over an area in a randommanner. They need to self-establish a wireless multi-hop network and routingpaths from all sensor nodes to a central base station. In this thesis, we presentour E-Sense system, a wireless sensor network testbed consisting of MICA2 sensornodes which can be used to monitor an indoor environment like oce buildingsand homes. The testbed can be accessed through the Internet and provides a webbasedinterface to the sensor network. The users of the network can be locatedat any point in the Internet. Via the web based interface, the users can submitvarious types of queries to the sensor network and get the replies including thephysical measurement results.The E-Sense system also includes a distributed and energy-aware routing protocolthat we designed and implemented. The protocol aims ecient and balancedusage of energy in the sensor nodes to prolong the lifetime of the network. Therouting protocol is based on a many-to-one routing tree where each node independentlydetermines its next parent depending on the values of RSSI (ReceivedSignal Strength Indicator). The protocol can also adjust the transmit power tofurther decrease the energy spent in each sensor node. The testbed will be usefulfor experimental studies at both application and network levels.
Telsiz algılayıcı ağlarda ağ ömrünü geliştirmek için çıkış düğümü yer değişimi konusunda algoritmalar
A wireless sensor network (WSN) consists of hundreds or thousands of sensor nodes organized in an ad-hoc manner to achieve a predefined goal. Although WSNs have limitations in terms of memory and processor, the main constraint that makes WSNs different from traditional networks is the battery problem. Since sensor nodes are generally deployed to areas with harsh environmental conditions, replacing the exhausted batteries become practically impossible. This requires to use the energy very carefully in both node and network level. Different approaches are proposed in the literature for improving network lifetime, including data aggregation, energy efficient routing schemes and MAC protocols, etc. Main motivation for these approaches is to prolong the network lifetime without sacrificing service quality. Sink (data collection node) mobility is also one of the effective solutions in the literature for network lifetime improvement.In this thesis, we focus on the controlled sink mobility and present a set of algorithms for different parts of the problem, like sink sites determination, and movement decision parameters. Moreover, a load balanced topology construction algorithm is given as another component of network lifetime improvement. Experiment results are presented which compare the performance of different components of the mobility scheme with other approaches in the literature, and the whole sink mobility scheme with random movement and static sink cases. As a result, it is observed that our algorithms perform better than random movement and static cases for different scenarios.
Çok radyolu kablosuz örgü ağlarda kanal tahsisi ve yönlendirme
Wireless Mesh Network is a promising technology since it extends the range of wireless coverage by multi-hop transmission between routers. However, in multihop networks the total throughput decreases with increasing number of nodes and hops. To increase the total throughput, some mesh routers are equipped with multiple radios to use the available bandwidth of multiple non-overlapping channels. However, channel assignment should be done carefully to effectively use this available bandwidth. Moreover, the optimal channel assignment algorithm is NP-hard. In this thesis, we propose a joint channel assignment and routingsolution to effectively use the available bandwidth for multi-radio wireless mesh networks with given network topology and traffic profile. Initially, we predict the final routes of the flows and estimate the loads on the links using these path predictions and given traffic profile. Then three different heuristics determine the assignment order of the links. Then the least busy channel among the available channels is assigned to the link. Finally, our routing algorithm routes the flows such that the selected path is the least busy path among the alternatives. We evaluated our channel assignment and routing algorithm using ns-2 simulator which supports multiple channels and multiple radios per node and we compared our results with single channel WMNs, and different algorithms for multi-radio multi-channel WMNs. The results show that our joint algorithm successfully achieves up to 5 times more throughput than single channel WMN with using just 2 radios and 3 channels. Our algorithms also out-performs other comparedchannel assignment algorithms for multi-radio multi-channel WMNs.
Örgüsel ağlarda OLSR-duyarlı katmanlar arası kanal erişim planlaması
A wireless mesh network (WMN) is a communications network in which the nodes are organized to form a mesh topology. WMNs are expected to resolve the limitations and signifıcantly improve the performance of wireless ad-hoc, local area, personal area, and metropolitan area networks, which is the reason thatthey are experiencing fast-breaking progress and deployments. WMNs typically employ spatial TDMA (STDMA) based channel access schemes which are suitable for the high traffıc demands of WMNs. Currentresearch trends focus on using loosening the strict layered network implementation in order to look for possible ways of performance improvements. In this thesis, we propose two STDMA-based cross-layer OLSR-Aware channel access scheduling schemes (one distributed, one centralized) that aim better utilizingthe network capacity and increasing the overall application throughput by using OLSR-specifıc routing layer information in link layer scheduling. The proposed centralized algorithm provides a modifıcation of the traditional vertex coloring algorithm while the distributed algorithm is a fully distributed pseudo-randomalgorithm in which each node makes decisions using local information. Proposed schemes are compared against one another and against their Non-OLSR-Aware versions via extensive ns-2 simulations. Our simulation results indicate that MAC layer can obtain OLSR-specifıc information with no extra control overhead and utilizing OLSR-specifıc information signifıcantly improves the overall network performance both in distributed and centralized schemes. We further show that link layer algorithms that target the maximization of concurrent slot allocations do not necessarily increase the application throughput.
Kablosuz çoklu ortam algılayıcı ağlarında bant genişliği bilinçli ve enerji idareli veri akışı çoğa gönderim protokolleri
In recent years, the interest in wireless sensor networks has grown and resultedin the integration of low-power wireless technologies with cameras and microphonesenabling video and audio transport through a sensor network besidestransporting low-rate environmental measurement-data. These sensor networksare called wireless multimedia sensor networks (WMSN) and are still constrainedin terms of battery, memory and achievable data rate. Hence, delivering multimediacontent in such an environment has become a new research challenge.Depending on the application, content may need to be delivered to a single destination(unicast) or multiple destinations (multicast). In this work, we considerthe problem of eciently and eectively delivering a multimedia stream to multipledestinations, i.e. the multimedia multicasting problem, in wireless sensornetworks. Existing multicasting solutions for wireless sensor networks provideenergy eciency for low-bandwidth and delay-tolerant data. The aim of thiswork is to provide a framework that will enable multicasting of relatively highrateand long-durational multimedia streams while trying to meet the desiredquality-of-service requirements. To provide the desired bandwidth to a multicaststream, our framework tries to discover, select and use multicasting paths that gothrough uncongested nodes and in this way have enough bandwidth, while alsoconsidering energy eciency in the sensor network. As part of our framework,we propose a multicasting scheme, with both a centralized and distributed version,that can form energy-ecient multicast trees with enough bandwidth. Weevaluated the performance of our proposed scheme via simulations and observedthat our scheme can eectively construct such multicast trees.
Gecikme dirençli ağlarda süreli bağlantılar için yönlendirme
In delay tolerant networks (DTNs), the network may not be fully connected at any instance of time, but connections occurring between nodes at different times make the network connected through the entire time continuum. In such a case, traditional routing methods fail to operate as there are no contemporaneous end-to-end paths between sources and destinations. This study examines the routing in DTNs where connections arise in a periodic nature. Various levels of periodicity are analyzed to meet requirements of different network models. We propose various routing algorithms for periodic connections. Our proposed methods can find routes that can guarantee earliest delivery and minimum hop count. We evaluate our routing schemes via extensive simulation experiments and also compare them to some other popular routing approaches proposed for delay tolerant networks. Our evaluations show the feasibility and effectiveness of our schemes as alternative routing methods for delay tolerant networks.