Rozprawy doktorskie na temat „Wireless scheduling protocols”

The coverage and energy issues are the fundamental problems which prevent the development of wireless sensor networks. In order to accurately evaluate the monitoring quality (coverage), one needs to model the interactive of sensors, phenomenons and the environment. Furthermore, in collaborative with scheduling algorithm and computer optimization, protocols can improve the overall monitoring quality and prolong the lifetime of network. This thesis is an investigation of coverage problem and its relative applications in the wireless sensor networks. We first discuss the realistic of current boolean sensing model and propose an irregular sensing model used to determine the coverage in the area with obstacles. We then investigate a joint problem of maintaining the monitoring quality and extending the lifetime of network by using scheduling schemes. Since the scheduling problem is NP hard, genetic algorithm and Markov decision process are used to determine an achievable optimal result for the joint problem of coverage-preserving and lifetime-prolong. In order to avoid the cost of centralized or distributed scheduling algorithms, a localized coverage-preserving scheduling algorithm is proposed by exploring the construction process of Voronoi diagram. Besides exploring the coverage characteristic in a static wireless sensor network, we investigate the coverage problem when the mobile elements are introduced into network. We consider the single-hop mobile data gathering problem with the energy efficiency and data freshness concerns in a wireless sensor network where the connectivity cannot be maintained. We first investigate the upper/lower bound of the covering time for a single collector to cover the monitoring area. Through our investigation we show that for a bounded rectangle area a hexagon walk could explore the area more efficiently than a random walk when the edges of area are known. We then propose a virtual force mobile model (VFM) in which the energy consumption for data transmission is modeled as a virtual elastic force and used to guide of mobile collectors to move to optimal positions for energy saving.

Wireless Body Area Network (WBAN) facilitates efficient and cost-effective e-health care and well-being applications. The WBAN has unique challenges and features compared to other Wireless Sensor Networks (WSN). In addition to battery power consumption, the vulnerability and the unpredicted channel behavior of the Medium Access Control (MAC) layer make channel access a serious problem. MAC protocols based on Time Division Multiple Access (TDMA) can improve the reliability and efficiency of WBAN. However, conventional static TDMA techniques adopted by IEEE 802.15.4 and IEEE 802.15.6 do not sufficiently consider the channel status or the buffer requirements of the nodes within heterogeneous contexts. Although there are some solutions that have been proposed to alleviate the effect of the deep fade in WBAN channel by adopting dynamic slot allocation, these solutions still suffer from some reliability and energy efficiency issues and they do not avoid channel deep fading. This thesis presents novel and generic TDMA based techniques to improve WBAN reliability and energy efficiency. The proposed techniques synchronise nodes adaptively whilst tackling their channel and buffer status in normal and emergency contexts. Extensive simulation experiments using various traffic rates and time slot lengths demonstrate that the proposed techniques improve the reliability and the energy efficiency compared to the de-facto standards of WBAN, i.e. the IEEE 802.15.4 and the IEEE 802.15.6. In normal situations, the proposed techniques reduce packet loss up to 61% and 68% compared to the IEEE 802.15.4 and IEEE 802.15.6 respectively. They also reduce energy consumption up to 7.3%. In emergencies, however, the proposed techniques reduce packets loss up to 63.4% and 90% with respect to their counterparts in IEEE 802.15.4 and 802.15.6. The achieved results confirm the significant enhancements made by the developed scheduling techniques to promote the reliability and energy efficiency of WBAN, opening up promising doors towards new horizons and applications.

Providing access to telecommunication services in rural areas is of paramount importance for the development of any country. Since the cost is the main inhibiting factor, any technical solution for access in sparsely populated rural areas has to be reliable, efficient, and deployable at low-cost. This thesis studies the utilization of Multihop Wireless Networks (MWN) as an appealing alternative for rural communication. MWN are designed with a self-configuring capability and can adapt to the addition or removal of network radio units (nodes). This makes them simple to install, allowing unskilled users to set up the network quickly. To increase the performance and cost-efficiency, this thesis focuses on the use of Advanced Antenna Systems (AAS) in rural access networks. AAS promise to increase the overall capacity in MWN, improving the link quality while suppressing or reducing the multiple access interference. To effectively exploit the capabilities of AAS, a proper design of Medium Access Control (MAC) protocols is needed. Hence, the results of system level studies into MAC protocols and AAS are presented in this thesis. Two different MAC protocols are examined: Spatial Time Division Multiple Access (STDMA) and Carrier Sense Multiple Access Collision Avoidance (CSMA/CA) with handshaking. The effects of utilizing advanced antennas on the end-to-end network throughput and packet delay are analyzed with routing, power control and adaptive transmission data rate control separately and in combination. Many of the STDMA-related research questions addressed in this thesis are posed as nonlinear optimization problems that are solved by the technique called "column generation" to create the transmission schedule using AAS. However, as finding the optimal solution is computationally expensive, we also introduce low-complexity algorithms that, while simpler, yield reasonable results close to the optimal solution. Although STDMA has been found to be very efficient and fair, one potential drawback is that it may adapt slower than a distributed approach like CSMA/CA to network changes produced e.g. by traffic variations and time-variant channel conditions. In CSMA/CA, nodes make their own decisions based on partial network information and the handshaking procedure allows the use of AAS at the transmitter and the receiver. How to effectively use AAS in CSMA/CA with handshaking is addressed in this thesis. Different beam selection policies using switched beam antenna systems are investigated. Finally, we demonstrate how the proposed techniques can be applied in a rural access scenario in Nicaragua. The result of a user-deployed MWN for Internet access shows that the supported aggregated end-to-end rate is higher than an Asymmetric Digital Subscriber Line (ADSL) connection.
QC 20100908

When designing architectures and protocols for data traffic requiring real-time services, one of the major design goals is to guarantee that traffic deadlines can be met. However, many real-time applications also have additional requirements such as high throughput, high reliability, or energy efficiency. High-performance embedded systems communicating heterogeneous traffic with high bandwidth and strict timing requirements are in need of more efficient communication solutions, while wireless industrial applications, communicating control data, require support of reliability and guarantees of real-time predictability at the same time. To meet the requirements of high-performance embedded systems, this thesis work proposes two multi-wavelength high-speed passive optical networks. To enable reliable wireless industrial communications, a framework in­corporating carefully scheduled retransmissions is developed. All solutions are based on a single-hop star topology, predictable Medium Access Control algorithms and Earliest Deadline First scheduling, centrally controlled by a master node. Further, real-time schedulability analysis is used as admission control policy to provide delay guarantees for hard real-time traffic. For high-performance embedded systems an optical star network with an Arrayed Waveguide Grating placed in the centre is suggested. The design combines spatial wavelength re­use with fixed-tuned and tuneable transceivers in the end nodes, enabling simultaneous transmis­sion of both control and data traffic. This, in turn, permits efficient support of heterogeneous traf­fic with both hard and soft real-time constraints. By analyzing traffic dependencies in this mul­tichannel network, and adapting the real-time schedulability analysis to incorporate these traffic dependencies, a considerable increase of the possible guaranteed throughput for hard real-time traffic can be obtained. Most industrial applications require using existing standards such as IEEE 802.11 or IEEE 802.15.4 for interoperability and cost efficiency. However, these standards do not provide predict­able channel access, and thus real-time guarantees cannot be given. A framework is therefore de­veloped, combining transport layer retransmissions with real-time analysis admission control, which has been adapted to consider retransmissions. It can be placed on top of many underlying communication technologies, exemplified in our work by the two aforementioned wireless stan­dards. To enable a higher data rate than pure IEEE 802.15.4, but still maintaining its energy saving properties, two multichannel network architectures based on IEEE 802.15.4 and encompassing the framework are designed. The proposed architectures are evaluated in terms of reliability, utiliza­tion, delay, complexity, scalability and energy efficiency and it is concluded that performance is enhanced through redundancy in the time and frequency domains.

Wireless Sensor Networks (WSNs) are composed of a large number of battery-powered sensor nodes that have the ability to sense the physical environment, compute the obtained information and communicate using the radio interfaces. Because sensor nodes are generally deployed on a large and wild area, they are powered by embedded battery. And it is difficult to change or recharge the battery, thus to reduce the energy consumption when sensors and protocols are designed is very important and can extend the lifetime of WSNs. So sensor nodes transmit packets with a lower transmission power (e.g. OdBm). With this transmission power, a packet can only be transmitted dozens of meters away. Therefore, when a sensor detects an event, a packet is sent in a multi-hop, ad-hoc manner (without fixed infrastructure and each sensor is able to relay the packet) to the sink (specific node which gathers information and reacts to the network situation). In this thesis, we first give an elaborate state of the art of WSNs. Then the impacts of duty-cycle and unreliable links or the performances of routing layer are analyzed. Based on the analytical results, we then propose three new simple yet effective methods to construct virtual coordinates under unreliable links in WSNs. By further taking the duty-cycle and real-time constraints into consideration we propose two cross-layer forwarding protocols which can have a greater delivery ratio and satisfy the deadline requirements. In order to have protocols for the WSNs that have dynamic topology, we then propose a robust forwarding protocol which can adapt its parameters when the topology changes. At last, we conclude this thesis and give some perspectives.

This work starts from the proposition that it is beneficial to conserve communication energy in Wireless Sensor Networks (WSNs). For WSNs there is an added incentive for energy-efficient communication. The power supply of a sensor is often finite and small. Replenishing the power may be impractical and is likely to be costly. Wireless Sensor Networks are an important area of research. Data about the physical environment may be collected from hostile or friendly environments. Data is then transmitted to a destination without the need for communication cables. There are power and resource constraints upon WSNs, in addition WSN networks are often application specific. Different applications will often have different requirements. Further, WSNs are a shared medium system. The features of the MAC (Medium Access Control) protocol together with the application behaviour shape the communication states of the node. As each of these states have different power requirements the MAC protocol impacts upon the operation and power consumption efficiency. This work focuses on the development of an energy conservation protocol for WSNs where direct communication between sources and a base station is feasible. Whilst the multi-hop approach has been regarded as the underlying communication paradigm in WSNs, there are some scenarios where direct communication is applicable and a significant amount of communication energy can be saved. The Power & Reliability Aware Protocol has been developed. Its main objectives are to provide efficient data communication by means of energy conservation without sacrificing required reliability. This has been achieved by using direct communication, adaptive power adaptation and intelligent scheduling. The results of simulations illustrate the significance of communication energy and adaptive transmission. The relationship between Received Signal Strength Indicator (RSSI) and Packet Reception Rate (PRR) metrics is established and used to identify when power adaptation is required. The experimental results demonstrate an optimal region where lower power can be used without further reduction in the PRR. Communication delays depend upon the packet size whilst two-way propagation delay is very small. Accurate scheduling is achieved through monitoring the clock drift. A set of experiments were carried out to study benefits of direct vs. multi-hop communication. Significant transmitting current can be conserved if the direct communication is used. PoRAP is compared to Sensor-MAC (S-MAC), Berkeley-MAC (B-MAC) and Carrier Sense Multiple Access (CSMA). Parameter settings used in the Great Duck Island (GDI) a production habitat monitoring WSNs were applied. PoRAP consumes the least amount of energy.

A aplicação de redes sem fio vem crescendo consideravelmente nos últimos anos. Protocolos baseados nesta tecnologia estão sendo desenvolvidos para uma grande variedade de aplicações. A confiabilidade é um dos principais requisitos dos protocolos de comunicação nos ambientes industriais. Interferências, ambiente ruidoso e o grande risco das aplicações industriais que são monitoradas são fatores que elevam os níveis de exigência no que se refere à confiabilidade, redundância e segurança do protocolo. O protocolo WirelessHART é um padrão de comunicação sem fio desenvolvido especificamente para monitoramento e controle de processos com os requisitos necessários para ser utilizado em ambientes industriais. A norma do WirelessHART define diversos aspectos técnicos a serem utilizados no desenvolvimento de algoritmos. Os algoritmos de roteamento e escalonamento de mensagens são de grande relevância para o cumprimento dos requisitos temporais, de confiabilidade e segurança. Requisitos de roteamento e escalonamento são especificados, porém, os algoritmos a serem utilizados não são definidos. O objetivo nessa dissertação é analisar alguns dos principais algoritmos que tem sido propostos especificamente para o protocolo WirelessHART e apresentar um conjunto capaz de ser aplicado nesse protocolo. Análises e comparações entre os algoritmos são realizadas proporcionando um estudo aprofundado sobre seus impactos no desempenho do protocolo.
The application of wireless networks has grown considerably in recent years. Protocols based on this technology are being developed for a great variety of applications. Reliability is one of the main requirements for communication protocols in industrial environments. Interferences, noisy environment and high risk processes that are monitored are factors that increase the levels of requirements in terms of reliability, redundancy and security of the protocol. The WirelessHART protocol is a wireless communication standard specifically designed for process monitoring and control applications with the necessary requirements for to be used in industrial environments. The WirelessHART standard defines several technical aspects to be used in the development of the algorithms. The algorithms of routing and scheduling messages are highly relevant to meeting the timing requirements of reliability and safety. Routing and scheduling strategies are specified, however, the routing and scheduling algorithms are not defined for use. The goal of this dissertation is to analyze some of the main algorithms that have been proposed specifically for the WirelessHART protocol and to present a set able to be applied in this protocol. Analyzes and comparisons between algorithms are realized by providing a detailed study of their impacts on the protocol performance.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior
A evoluÃÃo no desenvolvimento de novos dispositivos, cada vez mais baratos e eficientes, expandiu o uso das Redes Sensores Sem Fio (RSSF) e incentivou a criaÃÃo de novas aplicaÃÃes, no cenÃrio contemporÃneo da ComputaÃÃo UbÃqua e Pervasiva. No entanto, a limitaÃÃo de energia continua sendo um desafio na Ãrea de RSSF. Essa situaÃÃo à agravada ainda mais pela a inviabilidade de recarga de energia jà que, em muitos casos, as RSSF sÃo utilizadas em ambientes inacessÃveis. Com o barateamento dos dispositivos utilizados nas RSSFs, ficou mais fÃcil empregar redes muito densas e de larga escala nos ambientes a serem monitorados. O emprego de redes densas, que apresentam alto grau de redundÃncia dos nÃs, permite que a rede continue funcional mesmo com a exaustÃo de alguns nÃs. AlÃm de oferecer tolerÃncia a falhas, o uso de redes muito densas oferece a oportunidade da implementaÃÃo de mecanismos de escalonamento dos nÃs redundantes, de forma que o tempo de vida da rede seja ainda melhor otimizado. Assumindo um cenÃrio com rede muito densas, este trabalho descreve a implementaÃÃo de um mecanismo de escalonamento autonÃmico, simples, robusto e escalÃvel, com o objetivo de melhorar ainda mais os resultados jà apresentados pelo BiO4SeL, um protocolo de roteamento baseado em ColÃnia de Formigas e desenvolvido para maximizar o tempo de vida da rede. Os resultados mostram que o novo esquema de escalonamento efetivamente melhora o tempo de vida de uma RSSF baseada no BiO4SeL em cenÃrios densos.
he evolution and development of new devices, increasingly cheaper and more efficient, expanded the use of Wireless Sensor Networks (WSN) and encouraged the creation of new applications in the contemporary scenery of Ubiquitous and Pervasive Computing. However, energy limitation remains a challenge in the field of WSN. This situation is aggravated even more by the infeasibility of energy recharge since, in many cases, WSN are used in inaccessible enviroments. With cheapness devices used in WSN, became easier to employ dense and large-scale networks in environments that will be monitored. The use of dense networks, which have a high degree redundancy of nodes, allows the network remains functional even with the exhaustion of some nodes. In addition to provide fault tolerance, the use of very dense networks offer the opportunity of implementing scheduling mechanisms for redundant nodes, in a way that the network lifetime is even better optimized. Assuming a scenery with very dense networks, this dissertation describes the implementation of an autonomic scheduling mechanism, simple, robust and scalable, in order to further improve the results already presented by BiO4SeL, which is a routing protocol based on Ant Colony and designed to maximize the network lifetime. The results show that the new scheduling scheme effectively improves the WSN lifetime based on BiO4SeL in dense scenarios.

Oliveira, Camila Helena Souza. Gerenciamento Autonômico de Energia em Redes de Sensores Sem Fio Através do Escalonamento de Atividade dos Nós. 2011. 103 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2011.
Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-07T17:01:05Z No. of bitstreams: 1 2011_dis_chsoliveira.htm: 516 bytes, checksum: 5f53d35c4f0938cf35fd9c5325cc0b3c (MD5)
Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-07T17:01:23Z (GMT) No. of bitstreams: 1 2011_dis_chsoliveira.htm: 516 bytes, checksum: 5f53d35c4f0938cf35fd9c5325cc0b3c (MD5)
Made available in DSpace on 2016-06-07T17:01:23Z (GMT). No. of bitstreams: 1 2011_dis_chsoliveira.htm: 516 bytes, checksum: 5f53d35c4f0938cf35fd9c5325cc0b3c (MD5) Previous issue date: 2011
he evolution and development of new devices, increasingly cheaper and more efficient, expanded the use of Wireless Sensor Networks (WSN) and encouraged the creation of new applications in the contemporary scenery of Ubiquitous and Pervasive Computing. However, energy limitation remains a challenge in the field of WSN. This situation is aggravated even more by the infeasibility of energy recharge since, in many cases, WSN are used in inaccessible enviroments. With cheapness devices used in WSN, became easier to employ dense and large-scale networks in environments that will be monitored. The use of dense networks, which have a high degree redundancy of nodes, allows the network remains functional even with the exhaustion of some nodes. In addition to provide fault tolerance, the use of very dense networks offer the opportunity of implementing scheduling mechanisms for redundant nodes, in a way that the network lifetime is even better optimized. Assuming a scenery with very dense networks, this dissertation describes the implementation of an autonomic scheduling mechanism, simple, robust and scalable, in order to further improve the results already presented by BiO4SeL, which is a routing protocol based on Ant Colony and designed to maximize the network lifetime. The results show that the new scheduling scheme effectively improves the WSN lifetime based on BiO4SeL in dense scenarios.
A evolução no desenvolvimento de novos dispositivos, cada vez mais baratos e eficientes, expandiu o uso das Redes Sensores Sem Fio (RSSF) e incentivou a criação de novas aplicações, no cenário contemporâneo da Computação Ubíqua e Pervasiva. No entanto, a limitação de energia continua sendo um desafio na área de RSSF. Essa situação é agravada ainda mais pela a inviabilidade de recarga de energia já que, em muitos casos, as RSSF são utilizadas em ambientes inacessíveis. Com o barateamento dos dispositivos utilizados nas RSSFs, ficou mais fácil empregar redes muito densas e de larga escala nos ambientes a serem monitorados. O emprego de redes densas, que apresentam alto grau de redundância dos nós, permite que a rede continue funcional mesmo com a exaustão de alguns nós. Além de oferecer tolerância a falhas, o uso de redes muito densas oferece a oportunidade da implementação de mecanismos de escalonamento dos nós redundantes, de forma que o tempo de vida da rede seja ainda melhor otimizado. Assumindo um cenário com rede muito densas, este trabalho descreve a implementação de um mecanismo de escalonamento autonômico, simples, robusto e escalável, com o objetivo de melhorar ainda mais os resultados já apresentados pelo BiO4SeL, um protocolo de roteamento baseado em Colônia de Formigas e desenvolvido para maximizar o tempo de vida da rede. Os resultados mostram que o novo esquema de escalonamento efetivamente melhora o tempo de vida de uma RSSF baseada no BiO4SeL em cenários densos.

Furthermore, we show that geometric retransmission algorithm is intrinsically unstable for large population sizes. On the other hand, exponential backoff algorithm is more robust and scalable. Even for infinity population sizes, the stable throughput and bounded delay region still exists under certain conditions.
In the light of the concern, we propose a queueing model of the general CSMA protocol with probability-based backoff scheduling algorithm. The input buffer of each node is modeled as a Geo/G/1 queue, in which the service time distribution of each individual head-of-line (HOL) packet can be described by a Markov chain. By means of this queueing model, we can obtain the characteristic equation of throughput, the packet queueing delay as well as the stable conditions with admissible input traffic. We also specify stable throughput and bounded delay regions with respect to the retransmission factor and input rate.
Last but not least, the proposed queueing model can be systematically generalized to investigate various types of MAC protocols, such as ALOHA, CSMA protocols, IEEE 802.11 protocols. Specifically, we illustrate the methodology by full analyses of the non-persistent CSMA and 1-persistent CSMA protocols in this thesis.
Medium Access Control (MAC) protocols have been continuously updated to keep up with the emerging new services and QoS requirements. Despite of the rapid changes of MAC protocols, a comprehensive performance analysis of any MAC protocol remains an open issue for over several decades.
Most of existing analysis of MAC protocols focused on the network throughput and packet access delay under the assumption that the network is saturated which is not realistic. We know very little about the stability of MAC protocol under the normal network operation for lack of a systematic model that can be adaptively applied to various MAC protocols with different service requirements and backoff scheduling algorithms.
Other than the probability-based backoff algorithm, this thesis also includes the study of window-based backoff algorithm. It is shown that the probability-based and window-based backoff algorithms are equivalent to each other. Moreover, we find that the characteristic equation of network throughput is invariant to backoff scheduling algorithms.
Wong, Pui King.
Adviser: Tony T. Lee.
Source: Dissertation Abstracts International, Volume: 73-06, Section: B, page: .
Thesis (Ph.D.)--Chinese University of Hong Kong, 2011.
Includes bibliographical references (leaves 125-133).
Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Abstract also in Chinese.

D. Tech. Electrical Engineering.
Discusses the protocol design in VANETs is very challenging due to their low latency and high data rate requirements in a high mobility environment. Hence, the central metrics of QoS such as throughput, reliability and delays are critical to the design of protocol in VANETs. Therefore, this project focuses on the scheduling and QoS enhancement algorithms. The QoS analytical model and multi-channel MAC protocol were completed; this was significant for the development of the VANETs.The anticipated benefits of this study may be described as: 1. The duty cycle adaptive MAC protocol could improve the QoS of VANET in the situation where the OBU is equipped with only one transceiver. 2. The results obtained from this model is significant for the designing and evaluation of the vehicular network. 3. Due to the characteristics of VANETs, the requirements of high throughput and low latency are critical in VANETs. An efficient multi-channel MAC protocol is a vital requirement in order to offer efficient, fair and stable channel access using the limited channel resources.

As more and more wireless applications/services emerge in the market, the already heavily crowded radio spectrum becomes much scarcer. Meanwhile, however,as it is reported in the recent literature, there is a large amount of radio spectrum that is under-utilized. This motivates the concept of cognitive radio wireless networks that allow the unlicensed secondary-users (SUs) to dynamically use the vacant radio spectrum which is not being used by the licensed primary-users (PUs). In this dissertation, we investigate protocol design for both the synchronous and asynchronous cognitive radio networks with emphasis on the medium access control (MAC) layer. We propose various spectrum sharing schemes, opportunistic packet scheduling schemes, and spectrum sensing schemes in the MAC and physical (PHY) layers for different types of cognitive radio networks, allowing the SUs to opportunistically utilize the licensed spectrum while confining the level of interference to the range the PUs can tolerate. First, we propose the cross-layer based multi-channel MAC protocol, which integrates the cooperative spectrum sensing at PHY layer and the interweave-based spectrum access at MAC layer, for the synchronous cognitive radio networks. Second, we propose the channel-hopping based single-transceiver MAC protocol for the hardware-constrained synchronous cognitive radio networks, under which the SUs can identify and exploit the vacant channels by dynamically switching across the licensed channels with their distinct channel-hopping sequences. Third, we propose the opportunistic multi-channel MAC protocol with the two-threshold sequential spectrum sensing algorithm for asynchronous cognitive radio networks. Fourth, by combining the interweave and underlay spectrum sharing modes, we propose the adaptive spectrum sharing scheme for code division multiple access (CDMA) based cognitive MAC in the uplink communications over the asynchronous cognitive radio networks, where the PUs may have different types of channel usage patterns. Finally, we develop a packet scheduling scheme for the PU MAC protocol in the context of time division multiple access (TDMA)-based cognitive radio wireless networks, which is designed to operate friendly towards the SUs in terms of the vacant-channel probability. We also develop various analytical models, including the Markov chain models, M=GY =1 queuing models, cross-layer optimization models, etc., to rigorously analyze the performance of our proposed MAC protocols in terms of aggregate throughput, access delay, and packet drop rate for both the saturation network case and non-saturation network case. In addition, we conducted extensive simulations to validate our analytical models and evaluate our proposed MAC protocols/schemes. Both the numerical and simulation results show that our proposed MAC protocols/schemes can significantly improve the spectrum utilization efficiency of wireless networks.

In the Internet of Things (IoT), devices such as sensors and actuators will almost invariably be connected to the Internet via wireless networks. The sensor and actuator devices in such systems will be resource challenged with constraints on the energy available to them, and on their computing, storage, and communication capabilities. Hence, the control strategies in such systems should be light-weight, and decentralised, requiring very little information exchange. With these observations in mind, the central theme of the work reported in this thesis is the development of wireless scheduling protocols, in a timeslotted setting, that require little state information and are amenable to decentralized implementation, while ensuring throughput optimality and even low mean packet delays in some cases. The thesis is divided into two parts. • In Part 1, – We study the problem of scheduling in collocated networks, wherein every node can listen to the transmissions of every other node. Motivated by a certain modification to the time slot structure that facilitates inferring activity on the channel, we derive a partial information framework within which we propose and analyse scheduling schemes. We then propose scheduling policies and analyse their stability and delay properties. – Next, we construct two completely decentralized protocols based on these results. Simulations show that the delay performance of the protocols is significantly better than that of existing protocols and, in fact, is very close to a centralized scheduler that has complete knowledge of the state of the system in every slot. This is important in light of the fact that our protocols are completely decentralized and also compute the schedule based on information gathered by the sensors only via sensing the channel for activity. – We also address the problem of short-term unfairness resulting from our low-delay scheduling policies and develop new policies to alleviate unfairness. We then propose modifications to our earlier protocols to handle alarm traffic (like uRLLC traffic being considered in the upcoming 5G standard) and show that the modified protocols provide low latency to such traffic, even in the presence of other data traffic in the system. part2 We move on to proposing reduced state scheduling policies for non-collocated networks. It should be noted that, while the scheduler that achieves minimum delay in collocated networks is known (in fact, it is not unique), such schedulers have been found for very few noncollocated networks. We begin by restricting our attention to a sub-class of scheduling policies, that take scheduling decisions based solely on the empty-nonempty status of the queues in the network. The state information for such networks is easy to disseminate (1 bit per queue) and hence makes them particularly suited to distributed implementation. – We begin by studying scheduling of transmissions on a class of networks called “path-graph networks.” These networks are characterized by interference graphs that are linear. We restrict ourselves to a further subclass of policies that are called Maximum Size Matching (MSM) policies and provide a complete characterization of the set of MSM policies for the case with N = 3 queues. As mentioned before, these policies do not require any information about the queues except their empty-nonempty status, which helps satisfy our reduced state space requirement. Our study has produced several interesting results about (in)stability and delay optimality. Specifically, we also show that the celebrated MaxWeight policy is not delay-optimal in such networks in a stochastic ordering sense (and hence, with respect to mean delay as well). – Continuing with path-graph networks, we later propose a “policy splicing” technique to combine policies for small networks to give rise to policies for larger networks. We use this technique to propose MSM scheduling policies for several such networks. We also provide an in-depth analysis of delay with MSM policies that culminates in a result which shows that there do not exist delay optimal MSM policies for such networks with N 4 queues. – Finally, we show how to extend our theory of MSM policies to schedule transmissions in a more general class of networks. We also propose and analyse multiple methods to further reduce the amount of state information (empty-nonempty statuses of the queues) that has to be exchanged across the network to make these protocols amenable to distributed implementation. Finally, we use this theory to propose a throughput optimal protocol wherein scheduling decisions are taken using only the information about activity on the channel (or lack thereof) that can be sensed by the nodes and study its stability performance in detail

碩士
國立暨南國際大學
電機工程學系
98
In this thesis, we propose a new medium access control protocol, named DS-MAC (Distributed-Scheduling MAC) for wireless sensor networks to reduce the end-to-end delay and consumed energy. Usually sensor nodes switch between sleep and active modes to reduce energy loss. As a result, the end-to-end delay of packets that travel many hops or pass a congested will be extremely high. Similar to the well-known S-MAC, DS-MAC has two phases in each cycle: listen and sleep periods. In the first phase, each node contends by the commonly used RTS/CTS mechanism for channel access at the second phase. We use the DURATION field in a RTS/CTS packet to record the packet schedule of the considered packet. All nodes in communication range of the RTS/CTS packet can update their packet schedule. During the first phase, each node updates its own packet schedule upon sending or receiving RTS/CTS packets and the packet schedules of all nodes are created in a distributed manner. In the second phase, each node just follows its packet schedule to send or receive a packet. The major advantage of DS-MAC is that a node can serve multiple packets in a cycle. We have compared the DS-MAC with others in terms of end-to-end delay, average throughput and energy consumption. The simulation results show that the DS-MAC has better performance, especially for high traffic loading.

碩士
靜宜大學
資訊工程學系
100
Energy conservation is one of the most important considerations in the deployment of a wireless sensor network. Among all methods, an efficient sleep and/or transmission schedule is undoubtedly the most helpful method for energy conservation. There have been many useful researches and solutions for sleep schedule, transmission schedule, or topology/routing creation. Nevertheless, very few of them can solve all of these problems in the same time. The DMAS protocol proposed by Chen et al should be the first one that can establish the network topology, the sleep/transmission schedule and the routing paths in a distributed way simultaneously. It gives significant contributions to energy conservation. However, the transmission delay still needs improvement. For this reason,this paper proposes a DMAS2 protocol that improves the transmission delay of the DMAS protocol. However, competition for transmission slots is more likely to happen for DMAS2, this will introduce another reason of packet delay. So, a resilient path mechanism is also proposed in the thesis to overcome the problem. The experimental results show that DMAS2 outperforms DMAS in transmission delay, packet arrival ratio and energy conservations.

碩士
國立中正大學
通訊工程研究所
100
Wireless Sensor Network (WSN) has gained much attention in recent years. After being deployed in the target region, sensor nodes sense information in the region and transmit it to the base station by wireless communication and network routing technology. Due to the small size of the sensor node, the hardware resources are limited; and further, it affects the capability of computing, storage space and power supply of nodes. However, the use of WSN in industrial automation is different from that in traditional WSN. WSN in industrial automation has low tolerance on end-to-end delay. Therefore, the design of data transmission needs to provide real-time QoS. In a real-time application, the predictable bounded delay is expected. In this thesis, we propose a chain-based transmission scheduling protocol. Through the setup of multiple chains, the order of node to send data packets follows the sequential positional order of the node in the chain and furthermore these chains can provide predictable bounded delay because the number of nodes in each chain is fixed. To improve the throughput, we let each chain operate in parallel. The simulations show that the bounded delays for each node are not the same due to the dependency on their position in the sink tree and the node number of the sub-chain. The bounded delay will increase as the node degree increases.

碩士
國立暨南國際大學
電機工程學系
101
In this thesis, we implement a new medium access control protocol, named DS-MAC (Distributed-Scheduling MAC) for wireless sensor networks to lower end-to-end packet delay and energy consumption. Usually, sensor nodes switch between sleep and active modes to decrease energy loss. As a result, the end-to-end delays of packets that travel many hops or is under congested traffic are excessively large. Similar to the well-known S-MAC protocol, the DS-MAC protocol has three periods in each cycle: Sync period, Control period, and Data/Sleep period. We divide Data/Sleep period into multiple mini-frames. Sender and receiver execute DATA/ACK handshake in the mini-frames. In Sync period, each node broadcast or receive Sync packets to maintain a synchronized network. In Control period, every node contends for the communication channel by utilising the CSMA/CA mechanism. We use the scheduling table and the mini-frame field in one RTS/CTS packet to establish and record the packet schedules. The mini-frame field in RTS/CTS is that receivers execute DATA/ACK handshake with senders by being based on the mini-frame which is given by senders. Senders update the packet schedules according as the mini-frame is given by receivers. Then, each node receives RTS/CTS not for myself in order that per node can know the situations of using mini-frames for neighbor nodes. The packet schedules of all nodes are established in a distributed manner. In Data/Sleep period, each sensor node merely follows the assigned mini-frame in its own scheduling table to send or receive a DATA packet. The major benefit of DS-MAC is that a node can serve multiple packets in one cycle. We have compared the DS-MAC protocol with the adaptive S-MAC protocol in terms of end-to-end packet delay and energy consumption. The simulation results show that the DS-MAC protocol has great performance, especially under high traffic load.

A wireless sensor network is a distributed network system consisting of miniature spatially distributed autonomous devices designed for using sensors to sense the environment and cooperatively perform a specific goal. Each sensor node contains a limited power source, a sensor and a radio through which it can communicate with other sensor nodes within its communication radius. Since these sensor nodes may be deployed in inaccessible terrains, it might not be possible to replace their power sources. The radio transceiver is the hardware component that uses the most power in a sensor node and the optimisation of this element is necessary to reduce the overall energy consumption. In the data link layer there are several major sources of energy waste which should be minimised to achieve greater energy efficiency: idle listening, overhearing, over-emitting, network signalling overhead, and collisions. Sleep scheduling utilises the low-power sleep state of a transceiver and aims to reduce energy wastage caused by idle listening. Idle listening occurs when the radio is on, even though there is no data to transmit or receive. Collisions are reduced by using medium reservation and carrier sensing; collisions occur when there are simultaneous transmissions from several nodes that are within the interference range of the receiver node. The medium reservation packets include a network allocation vector field which is used for virtual carrier sensing which reduces overhearing. Overhearing occurs when a node receives and decodes packets that are not destined to it. Proper scheduling can avoid energy wastage due to over-emitting; over-emitting occurs when a transmitter node transmits a packet while the receiver node is not ready to receive packets. A protocol stack is proposed that achieves an ultra-low duty cycle sleep schedule. The protocol stack is aimed at large nodal populations, densely deployed, with periodic sampling applications. It uses the IEEE 802.15.4 Physical Layer (PHY) standard in the 2.4 GHz frequency band. A novel hybrid data-link/network cross-layer solution is proposed using the following features: a global sleep schedule, geographical data gathering tree, Time Division Multiple Access (TDMA) slotted architecture, Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA), Clear Channel Assessment (CCA) with a randomised contention window, adaptive listening using a conservative timeout activation mechanism, virtual carrier sensing, clock drift compensation, and error control. AFRIKAANS : 'n Draadlose sensor-netwerk is 'n verspreide netwerk stelsel wat bestaan uit miniatuur ruimtelik verspreide outonome toestelle wat ontwerp is om in harmonie saam die omgewing te meet. Elke sensor nodus besit 'n beperkte bron van energie, 'n sensor en 'n radio waardeur dit met ander sensor nodusse binne hulle kommunikasie radius kan kommunikeer. Aangesien hierdie sensor nodusse in ontoeganklike terreine kan ontplooi word, is dit nie moontlik om hulle kragbronne te vervang nie. Die radio is die hardeware komponent wat van die meeste krag gebruik in 'n sensor nodus en die optimalisering van hierdie element is noodsaaklik vir die verminder die totale energieverbruik. In die data-koppelvlak laag is daar verskeie bronne van energie vermorsing wat minimaliseer moet word: ydele luister, a uistering, oor-uitstraling, oorhoofse netwerk seine, en botsings. Slaap-skedulering maak gebruik van die lae-krag slaap toestand van 'n radio met die doel om energie vermorsing wat veroorsaak word deur ydele luister, te verminder. Ydele luister vind plaas wanneer die radio aan is selfs al is daar geen data om te stuur of ontvang nie. Botsings word verminder deur medium bespreking en draer deteksie; botsings vind plaas wanneer verskeie nodusse gelyktydig data stuur. Die medium bespreking pakkies sluit 'n netwerk aanwysing vektor veld in wat gebruik word vir virtuele draer deteksie om a uistering te verminder. Afluistering vind plaas wanneer 'n nodus 'n pakkie ontvang en dekodeer maar dit was vir 'n ander nodus bedoel. Behoorlike skedulering kan energie verkwisting as gevolg van oor-uistraling verminder; oor-uistraling gebeur wanneer 'n sender nodus 'n pakkie stuur terwyl die ontvang nog nie gereed is nie. 'n Protokol stapel is voorgestel wat 'n ultra-lae slaap-skedule dienssiklus het. Die protokol is gemik op draadlose sensor-netwerke wat dig ontplooi, groot hoeveelhede nodusse bevat, en met periodiese toetsing toepassings. Dit maak gebruik van die IEEE 802.15.4 Fisiese-Laag standaard in die 2.4 GHz frekwensie band. 'n Nuwe baster datakoppelvlak/netwerk laag oplossing is voorgestel met die volgende kenmerke: globale slaap-skedulering, geogra ese data rapportering, Tyd-Verdeling-Veelvuldige-Toegang (TVVT) gegleufde argitektuur, Draer-Deteksie-Veelvuldige-Toegang met Botsing-Vermyding (DDVT/BV), Skoon-Kanaal-Assessering (SKA) met 'n wisselvallige twis-tydperk, aanpasbare slaap-skedulering met 'n konserwatiewe aktiverings meganisme, virtuele draer-deteksie, klok-wegdrywing kompensasie, en fout beheer. Copyright
Dissertation (MEng)--University of Pretoria, 2012.
Electrical, Electronic and Computer Engineering
unrestricted

碩士
淡江大學
資訊工程學系碩士在職專班
98
Wireless Sensor Networks is dispersed by a group composed of sensors and Base Stations. It can be used in various applications of remote monitoring system. Sensor nodes route the collected data to the Base Station via multi-hop wireless links. These sensors typically use batteries to operate, the battery cannot be replaced when the depletion of energy resources. Therefore, how to use energy-saving sensor networks to extend the overall working time efficiently is an important subject. Our research is base on “A Power Control Mechanism based on Sleep Scheduling for Wireless Sensor Networks”. We proposed a refined mechanism of routing protocol for wireless sensor networks with sleep scheduling. In wireless sensor network with sleep scheduling, active node adjusts its working time and even step in sleeping state earlier. In the multi-hop transmission mode, each node broadcasts the packet to confirm the receiving node. Therefore, we use routing information to reduce the number of broadcasting during transmission. When route node with low rest power cannot transfer, to remain completed route, we can execute interrupt handler procedure to reduce the package loss. Finally, to achieve power efficiency, we will simulate if the proposed algorithm can reduce energy consumption effectively in the data transmission procedure.

Advances in wireless technologies in the last ten years have created considerable opportunities as well as challenges for wireless body medical systems. The foremost challenge is how to build a reliable system connecting heterogeneous body sensors and actuators in an open system environment. In this dissertation, we present our work towards this goal. The system addresses four design issues: the underlying network architecture, the network scheduling disciplines, the location determination and tracking methods, and the embedded application execution architecture. We first present the design of an adaptive wireless protocol (MBStarPlus) to provide the basic wireless platform WBAN (Wireless Body Area Network). MBStarPlus is a real-time, secure, robust and flexible wireless network architecture. It is designed to utilize any low-power wireless radio as its physical layer. The TDMA mechanism is adopted for realtime data delivery. The time-slot length is adjustable for flexibility. Multiple technologies are utilized to provide reliability and security. We next investigate how to coordinate the body sensors/actuators that can optimally select from a range (maximum and minimum) of data rates. Two bandwidth scheduling algorithms are proposed. One is a greedy algorithm that works for sensors with limited computational capability. The other is the UMinMax scheduling algorithm that has better scalability and power-saving performance but is more computationally intensive. The third issue addressed in this proposal is how to achieve location determination and tracking by a mix of high-precision but expensive and lower-precision but cost-effective sensors. This is achieved by a novel collaborative location determination scheme ColLoc that can integrate different types of distance measurements into a location estimation algorithm by weighing them according to their precision levels. Through this, a localization service can be both cost-effective and sufficiently accurate. Fourth, in order to minimize the effects of long network latency when the body network scales up, we propose ControlInGateway, an architectural feature that allows a control application to be executed inside the network gateway without the host's involvement. With ControlInGateway, a wireless system could achieve the same control quality as a wired system.
text

碩士
國立中央大學
資訊工程研究所
97
In static wireless sensor networks, it is an important research issue to achieve effectively periodic data collection and prolong the network lifetime. In this thesis, a distributed k-load-balanced tree scheme is proposed to prolong the network lifetime for periodic data collection. A k-load-balanced tree is a tree that the difference of the number of children of each two non-leaf nodes in a network is less than k. Each node chooses the node with the least current number of children and number of neighbor as parent for avoiding that the difference of the number of children of each two non-leaf nodes in a network is more than k. Furthermore, based on the k-load-balanced tree, a distributed TDMA-based scheduling scheme is proposed to avoid packet collisions in wireless data transmissions. The simulation results show that our scheme can prolong the network lifetime and the network delay time is close to the result of centralized method.

碩士
國立臺灣科技大學
電機工程系
88
Wideband code-division multiple access （WCDMA） has been proposed as the backbone of third-generation technology. Distributed-Queueing Request Update Multiple Access （DQRUMA）, is a very efficient demand-assignment multiple access protocol. In future wireless multimedia networks, there will be a mixture of different traffic classes which have their own maximum tolerable bit error rate （BER）requirements. This character will cause different bandwidths with different traffic class in the CDMA environment. In this thesis, we combine the advantages of MC-CDMA and DQRUMA to propose a novel MAC algorithm which can provide a bandwidth-on-demand fair-sharing environment for wireless communications.

碩士
國立臺灣科技大學
電機工程系
90
With many excellent advantages in ATM network, it is viewed as the backbone of high-speed network in the future. Because of the more requirement of the wireless communication, using the excellence of ATM network to wireless ATM network becomes today the popular subject of research. The goal of designing wireless ATM network is building a wireless network by seamless and efficient ways, and extending the existed wired ATM network to wireless local loop by wireless interface. This paper discusses the performance of different flow types with distinct transmission rate using MC-CDMA/TDMA multiple-access protocol from mobile hosts to base stations, and schedules packets with similar bit error rate in the same time slot with identical power to be transmitted as far as possible. By improving the scheduling algorithm, we can increase the throughput and decrease the loss rate.

Wireless Sensor Networks (WSNs) have significant potential in many application domains, and are poised for growth in many markets ranging from agriculture and animal welfare to home and office automation. Although sensor network deployments have only begun to appear, the industry still awaits the maturing of this technology to realize its full benefits. The main constraints to large scale commercial adoption of sensor networks are the lack of available network management and control tools for determining the degree of data aggregation prior to transforming it into useful information, localizing the sensors accurately so that timely emergency actions can be taken at exact location, and scheduling data packets so that data are sent based on their priority and fairness. Moreover, due to the limited communication range of sensors, a large geographical area cannot be covered, which limits sensors application domain. Thus, we investigate a scalable and flexible WSN architecture that relies on multi-modal nodes equipped with IEEE 802.15.4 and IEEE 802.11 in order to use a Wi-Fi overlay as a seamless gateway to the Internet through WiMAX networks. We focus on network management approaches such as sensors localization, data scheduling, routing, and data aggregation for the WSN plane of this large scale multimodal network architecture and find that most existing approaches are not scalable, energy efficient, and fault tolerant. Thus, we introduce an efficient approach for each of localization, data scheduling, routing, and data aggregation; and compare the performance of proposed approaches with existing ones in terms of network energy consumptions, localization error, end-to-end data transmission delay and packet delivery ratio. Simulation results, theoretical and statistical analysis show that each of these approaches outperforms the existing approaches. To the best of our knowledge, no integrated network management solution comprising efficient localization, data scheduling, routing, and data aggregation approaches exists in the literature for a large scale WSN. Hence, we e±ciently integrate all network management components so that it can be used as a single network management solution for a large scale WSN, perform experimentations to evaluate the performance of the proposed framework, and validate the results through statistical analysis. Experimental results show that our proposed framework outperforms existing approaches in terms of localization energy consumptions, localization accuracy, network energy consumptions and end-to-end data transmission delay.

Benefiting from the constant and significant advancement of wireless communication technologies and networking protocols, Wireless Ad hoc NETwork (WANET) has played a more and more important role in modern communication networks without relying much on existing infrastructures. The past decades have seen numerous applications adopting ad hoc networks for service provisioning. For example, Wireless Sensor Network (WSN) can be widely deployed for environment monitoring and object tracking by utilizing low-cost, low-power and multi-function sensor nodes. To realize such applications, the design and evaluation of communication protocols are of significant importance. Meanwhile, the network performance analysis based on mathematical models is also in great need of development and improvement. This dissertation investigates the above topics from three important and fundamental aspects, including data collection protocol design, protocol modeling and analysis, and physical interference modeling and analysis. The contributions of this dissertation are four-fold. First, this dissertation investigates the synchronization issue in the duty-cycled, pipelined-scheduling data collection of a WSN, based on which a pipelined data collection protocol, called PDC, is proposed. PDC takes into account both the pipelined data collection and the underlying schedule synchronization over duty-cycled radios practically and comprehensively. It integrates all its components in a natural and seamless way to simplify the protocol implementation and to achieve a high energy efficiency and low packet delivery latency. Based on PDC, an Adaptive Data Collection (ADC) protocol is further proposed to achieve dynamic duty-cycling and free addressing, which can improve network heterogeneity, load adaptivity, and energy efficiency. Both PDC and ADC have been implemented in a pioneer open-source operating system for the Internet of Things, and evaluated through a testbed built based on two hardware platforms, as well as through emulations. Second, Linear Sensor Network (LSN) has attracted increasing attention due to the vast requirements on the monitoring and surveillance of a structure or area with a linear topology. Being aware that, for LSN, there is few work on the network modeling and analysis based on a duty-cycled MAC protocol, this dissertation proposes a framework for modeling and analyzing a class of duty-cycled, multi-hop data collection protocols for LSNs. With the model, the dissertation thoroughly investigates the PDC performance in an LSN, considering both saturated and unsaturated scenarios, with and without retransmission. Extensive OPNET simulations have been carried out to validate the accuracy of the model. Third, in the design and modeling of PDC above, the transmission and interference ranges are defined for successful communications between a pair of nodes. It does not consider the cumulative interference from the transmitters which are out of the contention range of a receiver. Since most performance metrics in wireless networks, such as outage probability, link capacity, etc., are nonlinear functions of the distances among communicating, relaying, and interfering nodes, a physical interference model based on distance is definitely needed in quantifying these metrics. Such quantifications eventually involve the Nodal Distance Distribution (NDD) intrinsically depending on network coverage and nodal spatial distribution. By extending a tool in integral geometry and using decomposition and recursion, this dissertation proposes a systematic and algorithmic approach to obtaining the NDD between two nodes which are uniformly distributed at random in an arbitrarily-shaped network. Fourth, with the proposed approach to NDDs, the dissertation presents a physical interference model framework to analyze the cumulative interference and link outage probability for an LSN running the PDC protocol. The framework is further applied to analyze 2D networks, i.e., ad hoc Device-to-Device (D2D) communications underlaying cellular networks, where the cumulative interference and link outage probabilities for both cellular and D2D communications are thoroughly investigated.
Graduate
0984
0544
tong1987fei@163.com

A wireless sensor network (WSN) is a collection of sensor nodes distributed over a geographical region to obtain the environmental data. It can have different types of applications ranging from low data rate event driven and monitoring applications to high data rate real time industry and military applications. Energy efficiency and reliability are the two major design issues which should be handled efficiently at all the layers of communication protocol stack, due to resource constraint sensor nodes and erroneous nature of wireless channel respectively. Media access control (MAC) is the protocol which deals with the problem of packet collision due to simultaneous transmissions by more than one neighboring sensor nodes. Time Division Multiple Access based (TDMA-based) and contention-based are the two major types of MAC protocols used in WSNs. In general, the TDMA-based channel access mechanisms perform better than the contention-based channel access mechanisms, in terms of channel utilization, reliability and power consumption, specially for high data rate applications in wireless sensor networks (WSNs). TDMA-based channel access employs a predefined schedule so that the nodes can transmit at their allotted time slots. Based on the frequency of scheduling requirement, the existing distributed TDMA-scheduling techniques can be classified as either static or dynamic. The primary purpose of static TDMA-scheduling algorithms is to improve the channel utilization by generating a schedule of smaller length. But, they usually take longer time to generate such a schedule, and hence, are not suitable for WSNs, in which the network topology changes dynamically. On the other hand, dynamic TDMA-scheduling algorithms generate a schedule quickly, but they are not efficient in terms of generated schedule length. We suggest a new approach to TDMA-scheduling for WSNs, that can bridge the gap between these two extreme types of TDMA-scheduling techniques, by providing the flexibility to trade-off between the schedule length and the time required to generate the schedule, as per the requirements of the underlying applications and channel conditions. The suggested TDMA-scheduling works in two phases. In the first phase, we generate a valid TDMA schedule quickly, which need not have to be very efficient in terms of schedule length. In the second phase, we iteratively reduce the schedule length in a manner, such that the process of schedule length reduction can be terminated after the execution of an arbitrary number of iterations, and still be left with a valid schedule. This step provides the flexibility to trade-off the schedule length with the time required to generate the schedule. In the first phase of above TDMA-scheduling approach, we propose two randomized, distributed and parallel TDMA-scheduling algorithms viz., Distributed TDMA Slot Scheduling (DTSS) and Randomized and Distributed TDMA (RD-TDMA) scheduling algorithm. Both the algorithms are based on graph coloring approach, which generate a TDMA schedule quickly with a fixed schedule length ( Colouring), where is the maximum degree of any node in the graph to be colored. The two algorithms differ in the channel access mechanism used by them to transmit control messages, and in the generated schedule for different modes of communication, i.e., unicast, multicast and broadcast. The novelty of the proposed algorithms lies in the methods, by which an uncolored node detects that the slot picked by it is different from the slots picked by all the neighboring nodes, and the selection of probabilities with which the available slots can be picked up. Furthermore, to achieve faster convergence we introduce the idea of dynamic slot-probability update as per which the nodes update their slot-probability by considering the current slot-probability of their neighboring nodes. Under the second phase of the proposed TDMA-scheduling approach, we provide two randomized and distributed schedule compaction algorithms, viz., Distributed Schedule Compaction (DSC) and Distributed Schedule Length Reduction (DSLR) algorithm, as the mechanism to trade-off the scheduling time with the generated schedule length. These algorithms start with a valid TDMA schedule and progressively compress it in each round of execution. Additionally, Furthermore, the execution of these algorithms can be stopped after an arbitrary number of rounds as per the requirements of underlying applications. Even though TDMA-based MAC protocols avoid packet loss due to collision, due to erroneous nature of wireless medium, they alone are not sufficient to ensure the reliable transmission in WSNs. Automatic Repeat reQuest (ARQ) is the technique commonly used to provide error control for unicast data transmission. Unfortunately, ARQ mechanisms cannot be used for reliable multicast/broadcast transmission in WSNs. To solve this issue, we propose a virtual token-based channel access and feedback protocol (VTCAF) for link level reliable multicasting in single-hop wireless networks. The VTCAF protocol introduces a virtual (implicit) token passing mechanism based on carrier sensing to avoid the collision between feedback messages. The delay performance is improved in VTCAF protocol by reducing the number of feedback messages. Besides, the VTCAF protocol is parametric in nature and can easily trade-off reliability with the delay as per the requirements of the underlying applications. Finally, by integrating all the works, viz., TDMA-scheduling algorithms (DTSS/RD-TDMA), schedule compaction algorithms and link layer feedback mechanism for reliable multicast/ broadcast, we propose a TDMA-based energy aware and reliable MAC protocol, named TEA-MAC for multi-hop WSNs. Similar to VTCAF, TEA-MAC protocol uses the combination of ACK-based and NACK-based approaches to ensure reliable communication. But, instead of using virtual token-based channel access, it uses contention-based channel access for NACK transmission. All the algorithms and protocols proposed in this thesis are distributed, parallel and fault tolerant against packet losses to support scalability, faster execution and robustness respectively. The simulations have been performed using Castalia network simulator to evaluate the performance of proposed algorithms/protocols and also to compare their performance with the existing algorithms/protocols. We have also performed theoretical analysis of these algorithms/protocols to evaluate their performance. Additionally, we have shown the correctness of proposed algorithms/protocols by providing the necessary proofs, whenever it was required. The simulation results together with theoretical analysis show that, in addition to the advantage of trading the runtime with schedule length, the proposed TDMA scheduling approach achieves better runtime and schedule length performance than existing algorithms. Additionally, the TEA-MAC protocol is able to considerably improve the reliability and delay performance of multicast communication in WSNs.

A wireless sensor network (WSN) is a collection of sensor nodes distributed over a geographical region to obtain the environmental data. It can have different types of applications ranging from low data rate event driven and monitoring applications to high data rate real time industry and military applications. Energy efficiency and reliability are the two major design issues which should be handled efficiently at all the layers of communication protocol stack, due to resource constraint sensor nodes and erroneous nature of wireless channel respectively. Media access control (MAC) is the protocol which deals with the problem of packet collision due to simultaneous transmissions by more than one neighboring sensor nodes. Time Division Multiple Access based (TDMA-based) and contention-based are the two major types of MAC protocols used in WSNs. In general, the TDMA-based channel access mechanisms perform better than the contention-based channel access mechanisms, in terms of channel utilization, reliability and power consumption, specially for high data rate applications in wireless sensor networks (WSNs). TDMA-based channel access employs a predefined schedule so that the nodes can transmit at their allotted time slots. Based on the frequency of scheduling requirement, the existing distributed TDMA-scheduling techniques can be classified as either static or dynamic. The primary purpose of static TDMA-scheduling algorithms is to improve the channel utilization by generating a schedule of smaller length. But, they usually take longer time to generate such a schedule, and hence, are not suitable for WSNs, in which the network topology changes dynamically. On the other hand, dynamic TDMA-scheduling algorithms generate a schedule quickly, but they are not efficient in terms of generated schedule length. We suggest a new approach to TDMA-scheduling for WSNs, that can bridge the gap between these two extreme types of TDMA-scheduling techniques, by providing the flexibility to trade-off between the schedule length and the time required to generate the schedule, as per the requirements of the underlying applications and channel conditions. The suggested TDMA-scheduling works in two phases. In the first phase, we generate a valid TDMA schedule quickly, which need not have to be very efficient in terms of schedule length. In the second phase, we iteratively reduce the schedule length in a manner, such that the process of schedule length reduction can be terminated after the execution of an arbitrary number of iterations, and still be left with a valid schedule. This step provides the flexibility to trade-off the schedule length with the time required to generate the schedule. In the first phase of above TDMA-scheduling approach, we propose two randomized, distributed and parallel TDMA-scheduling algorithms viz., Distributed TDMA Slot Scheduling (DTSS) and Randomized and Distributed TDMA (RD-TDMA) scheduling algorithm. Both the algorithms are based on graph coloring approach, which generate a TDMA schedule quickly with a fixed schedule length ( Colouring), where is the maximum degree of any node in the graph to be colored. The two algorithms differ in the channel access mechanism used by them to transmit control messages, and in the generated schedule for different modes of communication, i.e., unicast, multicast and broadcast. The novelty of the proposed algorithms lies in the methods, by which an uncolored node detects that the slot picked by it is different from the slots picked by all the neighboring nodes, and the selection of probabilities with which the available slots can be picked up. Furthermore, to achieve faster convergence we introduce the idea of dynamic slot-probability update as per which the nodes update their slot-probability by considering the current slot-probability of their neighboring nodes. Under the second phase of the proposed TDMA-scheduling approach, we provide two randomized and distributed schedule compaction algorithms, viz., Distributed Schedule Compaction (DSC) and Distributed Schedule Length Reduction (DSLR) algorithm, as the mechanism to trade-off the scheduling time with the generated schedule length. These algorithms start with a valid TDMA schedule and progressively compress it in each round of execution. Additionally, Furthermore, the execution of these algorithms can be stopped after an arbitrary number of rounds as per the requirements of underlying applications. Even though TDMA-based MAC protocols avoid packet loss due to collision, due to erroneous nature of wireless medium, they alone are not sufficient to ensure the reliable transmission in WSNs. Automatic Repeat reQuest (ARQ) is the technique commonly used to provide error control for unicast data transmission. Unfortunately, ARQ mechanisms cannot be used for reliable multicast/broadcast transmission in WSNs. To solve this issue, we propose a virtual token-based channel access and feedback protocol (VTCAF) for link level reliable multicasting in single-hop wireless networks. The VTCAF protocol introduces a virtual (implicit) token passing mechanism based on carrier sensing to avoid the collision between feedback messages. The delay performance is improved in VTCAF protocol by reducing the number of feedback messages. Besides, the VTCAF protocol is parametric in nature and can easily trade-off reliability with the delay as per the requirements of the underlying applications. Finally, by integrating all the works, viz., TDMA-scheduling algorithms (DTSS/RD-TDMA), schedule compaction algorithms and link layer feedback mechanism for reliable multicast/ broadcast, we propose a TDMA-based energy aware and reliable MAC protocol, named TEA-MAC for multi-hop WSNs. Similar to VTCAF, TEA-MAC protocol uses the combination of ACK-based and NACK-based approaches to ensure reliable communication. But, instead of using virtual token-based channel access, it uses contention-based channel access for NACK transmission. All the algorithms and protocols proposed in this thesis are distributed, parallel and fault tolerant against packet losses to support scalability, faster execution and robustness respectively. The simulations have been performed using Castalia network simulator to evaluate the performance of proposed algorithms/protocols and also to compare their performance with the existing algorithms/protocols. We have also performed theoretical analysis of these algorithms/protocols to evaluate their performance. Additionally, we have shown the correctness of proposed algorithms/protocols by providing the necessary proofs, whenever it was required. The simulation results together with theoretical analysis show that, in addition to the advantage of trading the runtime with schedule length, the proposed TDMA scheduling approach achieves better runtime and schedule length performance than existing algorithms. Additionally, the TEA-MAC protocol is able to considerably improve the reliability and delay performance of multicast communication in WSNs.