s2fieldsofstudy:
Computer Science
Linguistics

text:
Wider Context by Using Bilingual Language Models in Machine Translation

In past Evaluations for Machine Translation of European Languages, it could be shown that the translation performance of SMT systems can be increased by integrating a bilingual language model into a phrase-based SMT system. In the bilingual language model, target words with their aligned source words build the tokens of an n-gram based language model. We analyzed the effect of bilingual language models and show where they could help to better model the translation process. We could show improvements of translation quality on German-to-English and Arabic-to-English. In addition, for the Arabic-to-English task, training an extra bilingual language model on the POS tags instead of the surface word forms led to further improvements.

Introduction
In many state-of-the art SMT systems, the phrasebased (Koehn et al., 2003) approach is used. In this approach, instead of building the translation by translating word by word, sequences of source and target words, so-called phrase pairs, are used as the basic translation unit. A table of correspondences between source and target phrases forms the translation model in this approach. Target language fluency is modeled by a language model storing monolingual n-gram occurrences. A log-linear combination of these main models as well as additional features is used to score the different translation hypotheses. Then the decoder searches for the translation with the highest score.
A different approach to SMT is to use a stochastic finite state transducer based on bilingual ngrams (Casacuberta and Vidal, 2004). This approach was for example successfully applied by Allauzen et al. (2010) on the French-English translation task. In this so-called n-gram approach the translation model is trained by using an n-gram language model of pairs of source and target words, called tuples. While the phrase-based approach captures only bilingual context within the phrase pairs, in the n-gram approach the n-gram model trained on the tuples is used to capture bilingual context between the tuples. As in the phrase-based approach, the translation model can also be combined with additional models like, for example, language models using log-linear combination.
Inspired by the n-gram-based approach, we introduce a bilingual language model that extends the translation model of the phrase-based SMT approach by providing bilingual word context. In addition to the bilingual word context, this approach enables us also to integrate a bilingual context based on part of speech (POS) into the translation model. When using phrase pairs it is complicated to use different kinds of bilingual contexts, since the context of the POS-based phrase pairs should be bigger than the word-based ones to make the most use of them. But there is no straightforward way to integrate phrase pairs of different lengths into the translation model in the phrase-based approach, while it is quite easy to use n-gram models with different context lengths on the tuples. We show how we can use bilingual POS-based language models to capture longer bilingual context in phrase-based translation systems.
This paper is structured in the following way: In the next section, we will present some related work. Afterwards, in Section 3, a motivation for using the bilingual language model will be given. In the following section the bilingual language model is described in detail. In Section 5, the results and an analysis of the translation results is given, followed by a conclusion.

Related Work
The n-gram approach presented in Mariño et al. (2006) has been derived from the work of Casacuberta and Vidal (2004), which used finite state transducers for statistical machine translation. In this approach, units of source and target words are used as basic translation units. Then the translation model is implemented as an n-gram model over the tuples. As it is also done in phrase-based translations, the different translations are scored by a log-linear combination of the translation model and additional models.
Crego and Yvon (2010) extended the approach to be able to handle different word factors. They used factored language models introduced by Bilmes and Kirchhoff (2003) to integrate different word factors into the translation process. In contrast, we use a log-linear combination of language models on different factors in our approach.
A first approach of integrating the idea presented in the n-gram approach into phrase-based machine translation was described in Matusov et al. (2006). In contrast to our work, they used the bilingual units as defined in the original approach and they did not use additional word factors. Hasan et al. (2008) used lexicalized triplets to introduce bilingual context into the translation process. These triplets include source words from outside the phrase and form and additional probability p(f |e, e ) that modifies the conventional word probability of f given e depending on trigger words e in the sentence enabling a context-based translation of ambiguous phrases.
Other approaches address this problem by integrating word sense disambiguation engines into a phrase-based SMT system. In Chan and Ng (2007) a classifier exploits information such as local col-locations, parts-of-speech or surrounding words to determine the lexical choice of target words, while Carpuat and Wu (2007) use rich context features based on position, syntax and local collocations to dynamically adapt the lexicons for each sentence and facilitate the choice of longer phrases.
In this work we present a method to extend the locally limited context of phrase pairs and n-grams by using bilingual language models. We keep the phrase-based approach as the main SMT framework and introduce an n-gram language model trained in a similar way as the one used in the finite state transducer approach as an additional feature in the loglinear model.

Motivation
To motivate the introduction of the bilingual language model, we will analyze the bilingual context that is used when selecting the target words. In a phrase-based system, this context is limited by the phrase boundaries. No bilingual information outside the phrase pair is used for selecting the target word. The effect can be shown in the following example sentence: Ein gemeinsames Merkmal aller extremen Rechten in Europa ist ihr Rassismus und die Tatsache, dass sie das Einwanderungsproblem als politischen Hebel benutzen.
Using our phrase-based SMT system, we get the following segmentation into phrases on the source side: ein gemeinsames, Merkmal, aller, extremen Rechten. That means, that the translation of Merkmal is not influenced by the source words gemeinsames or aller.
As shown in Figure 1 the translation for the first three words ein gemeinsames Merkmal into a common feature can be created by segmenting it into ein gemeinsames and Merkmal as done by the Figure 1: Alternative Segmentations phrase-based system or by segmenting it into ein and gemeinsames Merkmal. In the phrase-based system, the decoder cannot make use of the fact that both segmentation variants lead to the same translation, but has to select one and use only this information for scoring the hypothesis.
Consequently, if the first segmentation is chosen, the fact that gemeinsames is translated to common does effect the translation of Merkmal only by means of the language model, but no bilingual context can be carried over the segmentation boundaries.
To overcome this drawback of the phrase-based approach, we introduce a bilingual language model into the phrase-based SMT system. Table 1 shows the source and target words and demonstrates how the bilingual phrases are constructed and how the source context stays available over segment boundaries in the calculation of the language model score for the sentence. For example, when calculating the language model score for the word feature P ( fea-ture_Merkmal | common_gemeinsames) we can see that through the bilingual tokens not only the previous target word but also the previous source word is known and can influence the translation even though it is in a different segment.

Bilingual Language Model
The bilingual language model is a standard n-grambased language model trained on bilingual tokens instead of simple words. These bilingual tokens are motivated by the tuples used in n-gram approaches to machine translation. We use different basic units for the n-gram model compared to the n-gram approach, in order to be able to integrate them into a phrase-based translation system.
In this context, a bilingual token consists of a target word and all source words that it is aligned to. More formally, given a sentence pair e I 1 = e 1 ...e I and f J 1 = f 1 ...f J and the corresponding word alignment A = {(i, j)} the following tokens are created: Therefore, the number of bilingual tokens in a sentence equals the number of target words. If a source word is aligned to two target words like the word aller in the example sentence, two bilingual tokens are created: all_aller and the_aller. If, in contrast, a target word is aligned to two source words, only one bilingual token is created consisting of the target word and both source words.
The existence of unaligned words is handled in the following way. If a target word is not aligned to any source word, the corresponding bilingual token consists only of the target word. In contrast, if a source word is not aligned to any word in the target language sentence, this word is ignored in the bilingual language model.
Using this definition of bilingual tokens the translation probability of source and target sentence and the word alignment is then defined by: This probability is then used in the log-linear combination of a phrase-based translation system as an additional feature. It is worth mentioning that although it is modeled like a conventional language model, the bilingual language model is an extension to the translation model, since the translation for the source words is modeled and not the fluency of the target text. To train the model a corpus of bilingual tokens can be created in a straightforward way. In the generation of this corpus the order of the target words defines the order of the bilingual tokens. Then we can use the common language modeling tools to train the bilingual language model. As it was done for the normal language model, we used Kneser-Ney smoothing.

Comparison to Tuples
While the bilingual tokens are motivated by the tuples in the n-gram approach, there are quite some differences. They are mainly due to the fact that the tuples are also used to guide the search in the n-gram approach, while the search in the phrase-based approach is guided by the phrase pairs and the bilingual tokens are only used as an additional feature in scoring.
While no word inside a tuple can be aligned to a word outside the tuple, the bilingual tokens are created based on the target words. Consequently, source words of one bilingual token can also be aligned to target words inside another bilingual token. Therefore, we do not have the problems of embedded words, where there is no independent translation probability.
Since we do not create a a monotonic segmentation of the bilingual sentence, but only use the segmentation according to the target word order, it is not clear where to put source words, which have no correspondence on the target side. As mentioned before, they are ignored in the model.
But an advantage of this approach is that we have no problem handling unaligned target words. We just create bilingual tokens with an empty source side. Here, the placing order of the unaligned target words is guided by the segmentation into phrase pairs. Furthermore, we need no additional pruning of the vocabulary due to computation cost, since this is already done by the pruning of the phrase pairs. In our phrase-based system, we allow only for twenty translations of one source phrase.

Comparison to Phrase Pairs
Using the definition of the bilingual language model, we can again have a look at the introductory example sentence. We saw that when translating the phrase ein gemeinsames Merkmal using a phrase-based system, the translation of gemeinsames into common can only be influenced by either the preceeding ein # a or by the succeeding Merkmal # feature, but not by both of them at the same time, since either the phrase ein gemeinsames or the phrase gemeinsames Merkmal has to be chosen when segmenting the source sentence for translation. If we now look at the context that can be used when translating this segment applying the bilingual language model, we see that the translation of gemeinsames into common is on the one hand influenced by the translation of the token ein # a within the bilingual language model probability P (common_gemeinsames | a_ein, <s>).
On the other hand, it is also influenced by the translation of the word Merkmal into feature encoded into the probability P (feature_Merkmal | common_gemeinsames). In contrast to the phrasebased translation model, this additional model is capable of using context information from both sides to score the translation hypothesis. In this way, when building the target sentence, the information of aligned source words can be considered even beyond phrase boundaries.

POS-based Bilingual Language Models
When translating with the phrase-based approach, the decoder evaluates different hypotheses with different segmentations of the source sentence into phrases. The segmentation depends on available phrase pair combinations but for one hypothesis translation the segmentation into phrases is fixed. This leads to problems, when integrating parallel POS-based information. Since the amount of differ-ent POS tags in a language is very small compared to the number of words in a language, we could manage much longer phrase pairs based on POS tags compared to the possible length of phrase pairs on the word level.
In a phrase-based translation system the average phrase length is often around two words. For POS sequences, in contrast, sequences of 4 tokens can often be matched. Consequently, this information can only help, if a different segmentation could be chosen for POS-based phrases and for word-based phrases. Unfortunately, there is no straightforward way to integrate this into the decoder.
If we now look at how the bilingual language model is applied, it is much easier to integrate the POS-based information. In addition to the bilingual token for every target word we can generate a bilingual token based on the POS information of the source and target words. Using this bilingual POS token, we can train an additional bilingual POSbased language model and apply it during translation. In this case it is no longer problematic if the context of the POS-based bilingual language model is longer than the one based on the word information, because word and POS sequences are scored separately by two different language models which cover different n-gram lengths.
The training of the bilingual POS language model is straightforward. We can build the corpus of bilingual POS tokens based on the parallel corpus of POS tags generated by running a POS tagger over both source and target side of the initial parallel corpus and the alignment information for the respective words in the text corpora.
During decoding, we then also need to know the POS tag for every source and target word. Since we build the sentence incrementally, we cannot use the tagger directly. Instead, we store also the POS source and target sequences during the phrase extraction. When creating the bilingual phrase pair with POS information, there might be different possibilities of POS sequences for the source and target phrases. But we keep only the most probable one for each phrase pair. For the Arabic-to-English translation task, we compared the generated target tags with the tags created by the tagger on the automatic translations. They are different on less than 5% of the words.
Using the alignment information as well as the source and target POS sequences we can then create the POS-based bilingual tokens for every phrase pair and store it in addition to the normal phrase pairs. At decoding time, the most frequent POS tags in the bilingual phrases are used as tags for the input sentence and the translation is done based on the bilingual POS tokens built from these tags together with their alignment information.

Results
We evaluated and analyzed the influence of the bilingual language model on different languages. On the one hand, we measured the performance of the bilingual language model on German-to-English on the News translation task. On the other hand, we evaluated the approach on the Arabic-to-English direction on News and Web data. Additionally, we present the impact of the bilingual language model on the English-to-German, German-to-English and French-to-English systems with which we participated in the WMT 2011.

System Description
The German-to-English translation system was trained on the European Parliament corpus, News Commentary corpus and small amounts of additional Web data. The data was preprocessed and compound splitting was applied. Afterwards the discriminative word alignment approach as described in (Niehues and Vogel, 2008) was applied to generate the alignments between source and target words. The phrase table was built using the scripts from the Moses package (Koehn et al., 2007). The language model was trained on the target side of the parallel data as well as on additional monolingual News data. The translation model as well as the language model was adapted towards the target domain in a log-linear way.
The Arabic-to-English system was trained using GALE Arabic data, which contains 6.1M sentences. The word alignment is generated using EMDC, which is a combination of a discriminative approach and the IBM Models as described in . The phrase table is generated using Chaski as described in . The language model data we trained on the GIGAWord V3 data plus BBN English data. After splitting the corpus according to sources, individual models were trained. Then the individual models were interpolated to minimize the perplexity on the MT03/MT04 data.
For both tasks the reordering was performed as a preprocessing step using POS information from the TreeTagger (Schmid, 1994) for German and using the Amira Tagger (Diab, 2009) for Arabic. For Arabic the approach described in Rottmann and Vogel (2007) was used covering short-range reorderings. For the German-to-English translation task the extended approach described in Niehues et al. (2009) was used to cover also the long-range reorderings typical when translating between German and English.
For both directions an in-house phrase-based decoder (Vogel, 2003) was used to generate the translation hypotheses and the optimization was performed using MER training. The performance on the testsets were measured in case-insensitive BLEU and TER scores.

German to English
We evaluated the approach on two different test sets from the News Commentary domain. The first consists of 2000 sentences with one reference. It will be referred to as Test 1. The second test set consists of 1000 sentences with two references and will be called Test 2.

Translation Quality
In Tables 2 and 3 the results for translation performance on the German-to-English translation task are summarized.
As it can been seen, the improvements of translation quality vary considerably between the two different test sets. While using the bilingual language model improves the translation by only 0.15 BLEU and 0.21 TER points on Test 1, the improvement on Test 2 is nearly 1 BLEU point and 0.5 TER points.

Context Length
One intention of using the bilingual language model is its capability to capture the bilingual contexts in a different way. To see, whether additional bilingual context is used during decoding, we analyzed the context used by the phrase pairs and by the n-gram bilingual language model. However, a comparison of the different context lengths is not straightforward. The context of an ngram language model is normally described by the average length of applied n-grams. For phrase pairs, normally the average target phrase pair length (avg. Target PL) is used as an indicator for the size of the context. And these two numbers cannot be compared directly.
To be able to compare the context used by the phrase pairs to the context used in the n-gram language model, we calculated the average left context that is used for every target word where the word itself is included, i.e. the context of a single word is 1. In case of the bilingual language model the score for the average left context is exactly the average length of applied n-grams in a given translation. For phrase pairs the average left context can be calculated in the following way: A phrase pair of length 1 gets a left context score of 1. In a phrase pair of length 2, the first word has a left context score of 1, since it is not influenced by any target word to the left. The second word in that phrase pair gets a left context count of 2, because it is influenced by the first word in the phrase. Correspondingly, the left context score of a phrase pair of length 3 is 6 (composed of the score 1 for the first word, score 2 for the second word and score 3 for the third word). To get the average left context for the whole translation, the context scores of all phrases are summed up and divided by the number of words in the translation.
The scores for the average left contexts for the two test sets are shown in Tables 2 and 3. They are called avg. PP Left Context. As it can be seen, the context used by the bilingual n-gram language model is longer than the one by the phrase pairs. The average n-gram length increases from 1.58 and 1.57, respectively to 2.21 and 2.18 for the two given test sets.
If we compare the average n-gram length of the bilingual language model to the one of the target language model, the n-gram length of the first is of course smaller, since the number of possible bilingual tokens is higher than the number of possible monolingual words. This can also be seen when looking at the perplexities of the two language models on the generated translations. While the perplexity of the target language model is 99 and 101 on Test 1 and 2, respectively, the perplexity of the bilin-gual language model is 512 and 538.

Overlapping Context
An additional advantage of the n-gram-based approach is the possibility to have overlapping context. If we would always use phrase pairs of length 2 only half of the adjacent words would influence each other in the translation. The others are only influenced by the other target words through the language model. If we in contrast would have a bilingual language model which uses an n-gram length of 2, this means that every choice of word influences the previous and the following word.
To analyze this influence, we counted how many borders of phrase pairs are covered by a bilingual n-gram. For Test 1, 16783 of the 27785 borders between phrase pairs are covered by a bilingual ngram. For Test 2, 9995 of 16735 borders are covered. Consequently, in both cases at around 60 percent of the borders additional information can be used by the bilingual n-gram language model.

Bilingual N-Gram Length
For the German-to-English translation task we performed an additional experiment comparing different n-gram lengths of the bilingual language   model. To ensure comparability between the experiments and avoid additional noise due to different optimization results, we did not perform separate optimization runs for for each of the system variants with different n-gram length, but used the same scaling factors for all of them. Of course, the system using no bilingual language model was trained independently. In Tables 4 and 5 we can see that the length of the actually applied n-grams as well as the BLEU score increased until the bilingual language model reaches an order of 4. For higher order bilingual language models, nearly no additional n-grams can be found in the language models. Also the translation quality does not increase further when using longer n-grams.

Arabic to English
The Arabic-to-English system was optimized on the MT06 data. As test set the Rosetta in-house test set DEV07-nw (News) and wb (Web Data) was used.
The results for the Arabic-to-English translation task are summarized in Tables 6 and 7. The performance was tested on two different domains, translation of News and Web documents. On both tasks, the translation could be improved by more than 1 BLEU point. Measuring the performance in TER also shows an improvement by 0.7 and 0.5 points.
By adding a POS-based bilingual language model, the performance could be improved further. An additional gain of 0.2 BLEU points and decrease of 0.3 points in TER could be reached. Consequently, an overall improvement of up to 1.7 BLEU points could be achieved by integrating two bilingual language models, one based on surface word forms and one based on parts-of-speech.

System
Dev   As it was done for the German-to-English system, we also compared the context used by the different models for this translation direction. The results are summarized in Table 8 for the News test set and in Table 9 for the translation of Web data. It can be seen like it was for the other language pair that the context used in the bilingual language model is bigger than the one used by the phrase-based translation model. Furthermore, it is worth mentioning that shorter phrase pairs are used, when using the POS-based bilingual language model. Both bilingual language models seem to model the context quite good, so that less long phrase pairs are needed to build the translation. Instead, the more frequent short phrases can be used to generate the translation.

Shared Translation Task @ WMT2011
The bilingual language model was included in 3 systems built for the WMT2011 Shared Translation   Task evaluation. A phrase-based system similar to the one described before for the German-to-English results was used. A detailed system description can be found in Herrmann et al. (2011). The results are summarized in Table 10. The performance of competitive systems could be improved in all three languages by up to 0.4 BLEU points.

Conclusion
In this work we showed how a feature of the n-grambased approach can be integrated into a phrasebased statistical translation system. We performed a detailed analysis on how this influences the scoring of the translation system. We could show improvements on a variety of translation tasks covering different languages and domains. Furthermore, we could show that additional bilingual context information is used. Furthermore, the additional feature can easily be extended to additional word factors such as part-ofspeech, which showed improvements for the Arabicto-English translation task.


extfieldsofstudy:
Computer Science
Engineering
Medicine

text:
Data-Centric Multiobjective QoS-Aware Routing Protocol for Body Sensor Networks

In this paper, we address Quality-of-Service (QoS)-aware routing issue for Body Sensor Networks (BSNs) in delay and reliability domains. We propose a data-centric multiobjective QoS-Aware routing protocol, called DMQoS, which facilitates the system to achieve customized QoS services for each traffic category differentiated according to the generated data types. It uses modular design architecture wherein different units operate in coordination to provide multiple QoS services. Their operation exploits geographic locations and QoS performance of the neighbor nodes and implements a localized hop-by-hop routing. Moreover, the protocol ensures (almost) a homogeneous energy dissipation rate for all routing nodes in the network through a multiobjective Lexicographic Optimization-based geographic forwarding. We have performed extensive simulations of the proposed protocol, and the results show that DMQoS has significant performance improvements over several state-of-the-art approaches.

Introduction
Wireless Body Sensor Networks (BSNs) have been receiving more and more attention in academia and industry in recent years, especially under the impending healthcare crisis and due to the availability of much less expensive biomedical sensors (BMSs) with certain computation and communication capabilities. The primary target applications of BSN research, so far, are medical healthcare services, addressing the weaknesses of traditional patient data collection system, such as imprecision (qualitative observation) and undersampling (infrequent assessment) [1,2]. BSNs can offer a paradigm shift from managing illness to proactively managing wellness by focusing on prevention and early detection/treatment of diseases, thereby reducing healthcare costs. They can capture accurate and quantitative data from a variety of sensors (e.g., temperature, blood pressure, heart rate, electrocardiogram (ECG), etc.) for longer time periods. BSNs with real-time sensing capability would also help in protecting those exposed to potentially life-threatening environments, including soldiers, first responders, and deep-sea and space explorers [3]. Therefore, on-time and reliable data delivery to the control center is very important for BSN applications.
The Quality-of-Service (QoS) provisioning in BSNs is a challenging task, mainly due to two reasons. First, the dynamic network topology, time-varying wireless channel and scarcity of node energy, computation power and channel bandwidth pose challenges on the design of QoS support schemes in BSNs. Second, there exist wide variations in data generation rate and delay-and loss-tolerances amongst the data packets generated by different types of BMSs [2]. For example, some low data rate BMSs (e.g., heartbeat, blood pressure, electroencephalogram (EEG) sensors) may generate very time-critical data packets, which must be delivered at the destination sink within a guaranteed end-to-end delay deadline; data packets from some of these sensors might also require high reliability. In contrast, some high data rate BMSs (e.g., streaming of ECG signals) may allow a certain percentage of packet losses. Therefore, a scalable solution with data-centric QoS-aware routing that can provide a clear differentiation in route selection between data packets with multiobjective QoS requirements, is greatly required for BSNs.
In the literature, several mechanisms (outlined in Section 2) have been proposed to mitigate the problems of multiobjective QoS provisioning in wireless sensor networks. However, to the best of our knowledge, no effective solution to this problem has yet been proposed so far particularly for BSNs. The key contribution of this paper is the first complete design and evaluation of data-centric multiobjective QoS-aware routing for BSNs that has clear differentiation in route selection between multiple traffic types with respect to their QoS requirements. It also trades off the energy cost and protocol operation overheads while improving the network performance.
The proposed data-centric multiobjective QoS-aware routing protocol, DMQoS, uses modular architecture and it exploits geographic locations to implement localized routing. An important property of the proposed protocol is the end-to-end QoS-aware routing with local decisions at each intermediate node without end-to-end path discovery and maintenance. This property is important for scalability to large-scale sensor networks, self-adaptability to network dynamics, and appropriateness to multiple classes of traffic flows. The routings of delay-critical and reliability-critical packets are handled separately by employing independent modules for each, whereas for the most critical packets having both stringent delay and reliability constraints, the corresponding modules operate in coordination to guarantee the required service. While the delay control module chooses the next-hop router node offering higher velocity of data packets, the reliability control module injects minimal redundant information by exploiting high reliability links. A Lexicographic Optimization (LO) [4] based approach is used to tune trade-off between the geographic progress and the residual energy levels. Therefore, our model considers not only the QoS requirements, but also the energy cost optimality of the routing path to improve the overall network performance.
We evaluated our routing protocol in terms of end-to-end packet delays, packet delivery ratio, average energy consumption per packet, and routing overhead for variable source traffic loads and wireless link bit error rates. The results show that DMQoS demonstrates a substantial improvement in required data delivery services over several state-of-the-art approaches and we provide insights into the sources of the improvement.
The rest of the paper is organized as follows. In Section 2, we describe the key limitations of some existing QoS-aware routing protocols. Subsequently, we present a body area sensor network model and assumptions we have considered in Section 3. Section 4 presents the proposed DMQoS architecture in detail, followed by the performance evaluations using Network Simulator-2 [5] in Section 5. Finally, we conclude the paper in Section 6.

Related Works
Major challenges and open research issues on QoS provisioning in BSNs have been presented in [6] and a cross-layer QoS framework (that spans over three layers) for biomedical sensor networks has been proposed in [7]. In EDDD [8], an energy-efficient differentiated directed diffusion mechanism has been developed that provides with service differentiation between real time and best effort traffic. However, their designs are neither scalable nor adaptive to dynamic environment. In recent years, QoS routing in location-aware wireless sensor networks has received much research interests due to its inherent characteristics of (i) being scalable to large networks, (ii) making routing decisions based on local neighborhood information, and (iii) being very adaptive under dynamic changes and mobility as only a node's neighborhood is affected. In [9], a reinforcement learning-based routing model for BSNs is proposed that selects a QoS route via computing neighborhood node's Q-values and position information, but does not consider energy at all. Directional Geographic Routing (DGR) [10] constructs an application-specific number of multiple disjointed paths for routing real time video communications data in wireless sensor networks. MCMP [11] uses link delay and reliability as routing decision parameters, where data packets are duplicated at source nodes by solving optimization problem. But, this approach considers neither residual energy nor progress speed. Hence, packets may get routed to a node which is highly congested and/or energy critical. MMSPEED [12] also sends duplicate packets (probabilistically) toward multiple paths and multiple reliability-and delay-bound packets are considered for QoS provisioning. However, routing in MMSPEED fully avoids energy consideration, reducing its applicability for BSNs. A hybrid geographic routing (HGR) protocol has been designed in [13] to achieve an efficient tradeoff between energy efficiency and delay performance. A reliable and energy-efficient routing protocol (REER) has been developed in [14] exploiting geographic information and cooperative communications.
The proposals in DARA [15] and LOCALMOR [16] have some similarities with our DMQoS protocol. In DARA [15], a weighted aggregate routing metric consisting of geographic progress, delay and energy is considered for supporting critical and non-critical data packets through defining long-and short-range forwarding zones, respectively. However, the use of same routing function for both the packet types deteriorates the QoS performance. In LOCALMOR [16], the routing functions have been separated for multiple packet types; however, it uses fixed number of sinks (primary and secondary sinks) and all packets are blindly duplicated toward both the sinks, making it unscalable. Also, it increases the overhead of sending too many duplicate packets.
The distinguished features of our DMQoS protocol design from those of the above mentioned works are as follows. Its routing functions are distinct for different packet types based on their QoS requirements. Its architecture is modular and the routing modules cooperate to render enhanced QoS services to different traffic classes. It uses Lexicographic Optimization (LO) for trading-off energy and service.

Network Model and Assumptions
Network Model We assume that several biomedical sensors (BMSs) are attached to a human body, and that they acquire sensor data and transmit to a central node, namely body sensor mote (BSM), which is responsible for collecting raw data, processing (coding, aggregation, etc.) and forwarding them toward the sink node in multihop fashion, as shown in Figure 1. They might have one or more sensing devices as well. Note here that these central nodes, which are also considered in [16], are different from personal servers (e.g., PDA) as used in other works [17] and references therein. These sensor motes have relatively high energy and computing capability compared to tiny BMSs. We also assume that there may be several sink nodes S in the network and any sink node s ∈ S is primarily responsible for collecting and recording the patient's data and then uploading this data to the medical care server via the Internet. In this architecture, the master BSM node and the slave BMSs together form a cluster of a body sensor network. As in Figure 1(b), a set of such cluster heads N form the backbone of the network. The key idea used in this network architecture is to move much of the network and protocol complexity away from the power-constrained BMSs and into the much more capable cluster head node. Note that the above network architecture is not only suitable for medical healthcare applications as in [18] but also for sports, battlefield, rescue operations, etc., those require large number of sensor nodes to be deployed. We also assume that each cluster head node has equal initial energy e init , and the residual energy of any node i ∈ N is denoted by e res (i).
Geographic Information Consideration In many applications of BSNs, the knowledge of the location of an event is also desired. Hence, it is important that the location of the network cluster nodes be known. If the nodes know their global or relative coordinates, distributed or stateless routing schemes can be employed, mitigating the need for propagation and updating of routing tables across the network. Distributed routing schemes based on the geographic locations of the nodes have been proposed and widely examined in [12,15] and references therein. Like them, we also assume that the coordinates of the nodes are known locally, i.e., each node knows its own coordinates as well as those of its routing neighbors through execution of a HELLO protocol. All nodes would also know the coordinates of the sink(s).  Constraints We assume that every delay-sensitive packet has a lifetime t lif e , specified by the application layer, which indicates the time limit within what the packet should be delivered to the final recipient; otherwise, the information in the packet is useless. For the reliability-sensitive packets, the application layer also tags the required reliability level R with a packet. Moreover, routing of all data packets should be energy-aware in order to extend the network lifetime.
HELLO Protocol Each cluster head node broadcasts a HELLO packet, periodically or upon observing significant changes in some parameter values, including its current position, residual energy and average queuing delays of different packet types in the node. This HELLO protocol works in similar way as in [15,19]. Upon reception of a HELLO packet, the neighbor cluster head nodes update their neighbor table entries. A new entry is added into the neighbor table when a new node moves into vicinity, and an existing entry is deleted when a neighboring node moves away or breaks down, which can be determined when a HELLO packet is not received during a predefined period of time (timeout). Thus, HELLO packets make the neighborhood information available to each cluster head node at a cost of additional energy and bandwidth. Time between broadcasts represents a trade-off between overhead communications and outdated cost function parameters. Therefore, update frequency should be carefully chosen to maintain a proper balance between information freshness and cost. Figure 2 shows the components and their interconnections in our proposed data-centric multiobjective QoS-aware routing protocol, DMQoS. The DMQoS consists of five modules: the dynamic packet classifier, delay control, reliability control, energy-aware geographic routing and QoS-aware queuing and scheduling modules. The details of these modules are presented in the following subsections.

Dynamic Packet Classifier
The service differentiation paradigm used in this paper is as follows. We define four classes of data packets -ordinary data packets (OP), reliability-driven data packets (RP), delay-driven data packets (DP) and most critical data packets (CP). The CP packets are given the highest priority due to their stringent delay and reliability constraints, e.g., they may carry electroencephalogram (EEG) and electrocardiogram (ECG) monitoring information during a critical situation such as a surgery. The next higher priority is given to DP packets which should be delivered within a predefined deadline, but may tolerate reasonable packet loss, e.g., video streaming. The RP packets should be delivered without loss, but do not need to be immediate or within a hard deadline, such as vital signal monitoring, respiration monitoring and PH-level monitoring. The lowest priority is given to the OP packets that are corresponding to regular measurements of patient physiological parameters, like body temperature, heartbeat, etc., that typically indicate normal values.
As shown in Figure 2, on reception of data packets either from application layer or from neighbor nodes, the dynamic packet classifier (DPC) of a node assigns them to one of the proper aforementioned categories and feeds them into the respective module in first-come-first-serve (FCFS) manner.

Energy-Aware Geographic Forwarding
Rather than using traditional end-to-end path discovery-based routing, we use localized packet forwarding that implements hop-by-hop routing. This deferred choice gives each packet transmission multiple opportunities to make progress toward the destination.
Our goal is to select a downstream node that has comparatively higher residual energy and gives higher geographic progress toward the destination sink. Note that while the second criterion decreases the number of hops between the source and the destination, the first one attempts to balance the energy consumption among the candidate downstream nodes. Our proposed energy-aware geographic forwarding (EAGF) uses a multiobjective Lexicographic Optimization (LO) approach [4] to manage this trade-off. In LO, the objective functions are arranged according to their absolute importance and the most important objective function is maximized (or minimized) first subject to the original constraints. If this problem has a unique solution, it will solve the whole multiobjective optimization problem. Otherwise, the second most important objective function is maximized (or minimized). Now, in addition to the original constraints, a new constraint is added. This new constraint is imparted to guarantee that the most important objective function preserves its optimal value. If this problem has a unique solution, it solves the original problem; otherwise, the process goes on as above.
In solution to our problem, there are only two objective functions of which the first one, the maximization of the geographic progress, is the most important. Let the objective functions be arranged according to the lexicographic order, with the most important function being, , ∀(i, j) ∈ N , ∀s ∈ S, where dist(a, b) denotes the geometric distance between nodes a and b; and, the least important one being f 2 (j) = eres(j) e init . Thus, we write the lexicographic problem for any node i ∈ N as follows, where, N i is the list of i's single hop neighbor nodes. The above LO problem can be divided into two separate problems with different constraint sets. The first problem is formulated as and its solution j * 1 and f * 1 = (j * 1 ) is obtained; here, dist(i, j) is the average distance from node i to all neighbor nodes j. Then the second problem is formulated as and the solution of this problem is j * 2 and f * 2 = (j * 2 ); here, e res (j) is the average residual energy level of the neighbor nodes j of i. If j * 2 does not produce a unique solution, we break the tie by selecting the one that produces the most geographic progress.
Note that the nice property of LO is its simplicity, and such a lightweight but effective method is suitable for resource-constrained BSNs. Even though LO has the drawback of neglecting less important objective functions when the most important one produces the unique solution, in our case, such situations should occur less frequently due to the high density of the network nodes. Moreover, LO exploits only local information to make routing decisions. The absence of a global routing scheme reduces the networks setup and updating costs, eliminates the need for storage of network-wide routing information at each node, and alleviates the possibility of incorrect information at the nodes as changes in system topology occur. What requires only is that the nodes must broadcast an upkeep packet including node identification, current location information, average queuing delays, and remaining energy periodically throughout its lifetime.

Reliability Control
Link quality degradation, congestion, node mobility, link failure(s), node failure(s), etc. may cause packet losses, which affect the reliable data delivery to the destination(s). It has been shown in the literature that the probability of successful packet delivery to the destination can be increased by sending duplicate packets over multiple spatially separated routes [11,12,15,16]. However, choosing the most appropriate next-hop nodes (N H r ) of multiple routes toward different sinks to assure end-to-end required reliability as well as determining the optimized number of such next-hop nodes (N H r,opt ) are challenging problems.
In our reliability control algorithm (see Algorithm 1), we use greedy approach to solve the above problems. At first, each node i, for each sink s ∈ S, identifies a candidate downstream node j that produces the maximum link reliabilityr i,j and stores it in the variable N H r (lines 1-3); the estimation method of the parameterr i,j will be discussed in Section 4.5. If |N H r | returns a NULL, the packet is dropped immediately; and, if it returns only one node, the packet is forwarded toward that next-hop node (lines 4-9) provided that its offered reliability is greater than the required reliability R; otherwise, the packet is dropped due to unavailability of feasible path. In the case |N H r | returns multiple nodes, the nodes from the list N H r are chosen one after another (in descending order of theirr i,j values) until their aggregate reliability becomes greater than or equal to the required reliability, R (lines [11][12][13][14][15][16][17]. Since the reliability is a multiplicative metric, we calculate the failure probability F = F × (1 −r i,j ), as presented in line 16. In fact, the above operation produces the optimal number of next-hop nodes |N H r,opt | that determines the degree of packet duplication for the reliability control. Note also that the value of |N H r,opt| ranges between 1 (best case) and the maximum number of sinks in the network (worst case). Therefore, our reliability control algorithm uses only the adequate number of duplicate packets, which in turn minimizes the routing and energy overheads compared to those of other approaches.
Drop the packet immediately; 6. else 7. if (|N H r | == 1) then 8. if (r i,j ≥ R, j ∈ N H r ) then 9. j ∈ N H r is the desired next hop node and send the packet to the outgoing queue;

Delay Control
This unit concerns the routing strategy for on-time delivery of time critical emergency packets. The delay-guaranteed service defines the maximum allowable latency, bounded by the lifetime of a packet (t lif e ), required by the application. The total latency is experienced by a packet to traverse the network nodes from the source to the destination. At the network layer, the end-to-end packet latency is the sum of the processing delay, the transmission delay, the queuing delay, and the propagation delay. The queuing delay contributes most significantly to the total latency followed by the transmission delay; the other delays are negligible. The CP and DP packets should travel through the next-hop nodes that provide with higher speeds so that the delay-guaranteed service is maintained.
Our delay control algorithm is presented in Algorithm 2 that works as follows. Each node i first computes the required velocity of a packet, v req (s) = dist(i,s) t lif e [packet.type] , toward any sink s ∈ S based on its distance from the sink, dist(i, s), and the remaining lifetime of the packet, t lif e [packet.type]. As a packet travels, intermediate nodes update the packet's remaining lifetime as follows, t lif e = t lif e −t elapsed , where t elapsed is the elapsed time of the packet at an intermediate node. We measure the elapsed time at each node i and piggyback it to the packet so that the following node j can determine the remaining time to deadline without using a globally synchronized clock. For this, when a node i receives the last bit of a packet, its MAC layer tags t arrival to the packet. This packet is processed by the network layer and forwarded to the chosen next-hop node j via the MAC layer. Note that the MAC layer of i requires some time to capture the channel using an RTS/CTS handshake and may transmit the packet several times until receiving ACK from j. For i to piggyback the accurate elapsed time, the MAC layer updates the field of elapsed time t elapsed just before it actually transmits the packet to the physical link as follows, t elapsed = t departure + t transDelay − t arrival , where t departure is the time at which node i transmits the first bit of the packet to the physical link and t transDelay is the transmission delay of the packet which can be computed using the transmission rate and packet length. Thus, once node j successfully receives the packet, the packet contains the correct measurement of the elapsed time at node i and computes the remaining lifetime of the packet.
After that the node i calculates the velocities offered by candidate next-hop nodes j toward a sink s ∈ S, v j (s), by taking into account the packet's waiting time at the queue of node i,d i q [packet.type], the estimated packet transmission delay of node i,d i tr , and the packet's waiting time at the candidate next-hop node j,d j q [packet.type] (see instruction 4). The consideration of queuing delay at a candidate next-hop node is very important for localized and delay-constrained routing because it indicates the traffic forwarding efficiency of the node. Nodes in the congested (or high traffic) area may have higher queuing and transmission delays, and thus their offered velocities will be lower. Hence, they will not be able to meet the required velocity level of the CP or DP data packets.
For all sinks, after computing the velocities of all candidate nodes, the algorithm then identifies the set of next-hop nodes N H d that are supposed to meet the required delay deadline (see instruction 6). Note here that there could be several non-overlapping paths from a source to the destination(s) even though they may not be the shortest paths. A non-shortest path is acceptable as long as it can deliver a packet within its end-to-end delay deadline. The estimation methods for queuing and transmission delays will be discussed in Section 4.5.
In the case in which |N H d | returns a NULL value, i.e., there is no neighboring router node satisfying the required velocity level, the packet is dropped immediately in order to prevent the network nodes from expending unnecessary energy. If |N H d | returns only one node, the packet is sent to the outgoing queue putting that node as the next-hop. On the other hand, if |N H d | includes several nodes, either the EAGF or the reliability control algorithm is called depending on the packet type in order to select the most appropriate router(s) from this set.
Drop the packet immediately; 10. else 11. if (|N H d | == 1) then 12. j ∈ N H d is the desired next hop node and send the packet to the outgoing queue;

Parameter Estimations
Estimation of Queuing Delay As shown in Figure 2, several queues are used for storing the different classes of data packets. The transmission scheduling of data packets from different queues is also different, to be discussed soon, and therefore, each class of data packets from a single node i may experience separate estimation of queuing delay d i q . We calculate this delay as the time difference between the insertion time of the packet at the queuing system and the time at which it enters into the position of transmission. Note here that we omitted the processing time of a packet at the node because it is trivial and is assumed to be almost the same for all packet types.
An Exponentially-Weighted Moving Average (EWMA) formula may suffice to estimate the running average queuing delays for each packet typed i q [packet.type]. Algorithm 3 shows the steps for estimating queuing delays, wherein, the weighting for each older data point decreases exponentially, giving much more importance to recent observations d i q [packet.type]. The degree of weighing decrease is expressed as a constant smoothing factor α, a number usually between 0 and 0.4. In our simulation, we use α = 0.2. Algorithm 3 Queuing Delay Estimator, at each node i.  [20], which measures packet loss intervals for TCP congestion control. The WATD that works as follows. It measures the instantaneous delay for each packet transmission, d i tr (n), which is the delay for the n th packet transmission measured as the time duration from the time at which the packet is ready for transmission (becoming the head of the transmission queue) to the time of successful transfer of its last bit and calculates the average value for the last P packets using (13) where, w n = 1 − n − P/2 P/2 + 1 , P/2 < n ≤ P For P = 8, this gives weights of 1, 1, 1, 1, 0.8, 0.6, 0.4 and 0.2 for w 1 through w 8 , respectively. Note that d i tr includes all delays due to media contention, such as channel sensing, RTS/CTS if any (depending on the chosen MAC protocol), backoff time slots, retransmissions, etc. Also note that the sensitivity of the average valued i tr depends on the value of P . In practice, a value of P = 8, with the most recent four samples equally weighted, appears to be a lower bound that still achieves a reasonable balance between resilience to link variations and fast response to real changes in the network conditions. Estimation of Link Reliability Each node i ∈ N in the MAC layer also measures the average link reliabilityr i,j separately for all of the downstream nodes j ∈ D i using Windowed Mean EWMA (WMEWMA), which is very similar to EWMA but updates the estimated parameter in regular time intervals instead of doing it for every packet. This method is more appropriate for measuring link reliability. WMEWMA counts the total number of transmission attempts T xCounter required (including the retransmissions) to send all of the packets of the current window W and the number of packets successfully transmitted SucCounter of the same window. Therefore, the ratio SucCounter T xCounter represents the success probability of the link for the window, which we regard as the link reliability in this paper. This per window link reliability is then averaged with the previous measurements using EWMA as follows,r (14) where β is the moving average smoothing factor, and its value is set equal to 0.4 in our simulation; a higher value is chosen because the current measurement is performed for all of the packets in a window W = 8 instead of for a single packet.

QoS-Aware Queuing and Scheduling
Queuing and scheduling have a direct impact on QoS characteristics. The desired QoS-aware routing for multiple classes of traffic, ranging from most critical data packets having constraints on both the delay and reliability to ordinary packets having no such delay or reliability constraints, is assumed to be met by implementing priority queues. In this work, four separate queues in a sensor node are considered; the highest priority queue for the critical packets (CP), the second higher priority queue for the delay-constrained packets (DP), the next lower priority queue for the reliability-constrained packets (RP) and the least priority queue for the ordinary packets (OP), as illustrated in Figure 2. Here, the scheduler uses strict priority logic, i.e., it always serves the highest priority queue first. If there is no packet waiting in the higher priority queues, it will serve the lower priority queues.
A key problem of the above multi-queuing system is that the lower priority traffic may be indefinitely blocked by higher priority traffic, which is commonly known as the starvation problem. A solution to this starvation problem of the lower priority traffic is aging, which is a technique of gradually increasing the priorities of packets waiting in the system for a longer period of time. In this work, we use a timeout-based policy that moves a packet to an upper priority queue on expiration of the timeout. Note that the above multi-queuing system implements the in-node packet contention based on priority levels, i.e., among the packets of the same node. It is also possible to define inter-node priorities for all traffic classes of the neighboring nodes by modifying the MAC protocol slots and backoff times [15]. However, the implementation of such inter-node prioritization requires important modifications in the MAC layer, which is beyond the scope of this work.

Simulation Model and Method
The performance of the proposed DMQoS routing framework is studied and compared with three other localized and QoS-aware routing protocols DARA [15], LOCALMOR [16] and MMSPEED [12] using simulations based on ns-2 [5], which supports the simulation of multihop wireless networks complete with physical, data link, and MAC layer models. The configuration of network parameters is shown in Table 1. The delay and reliability constraints for each packet class are listed in Table 2. Note here that the constraints for a candidate application may vary depending upon the values generated by the sensors. For instance, BP or body temperature readings may produce CP traffic flows if the values cross certain thresholds. For performance studies, we used five different sets of source traffic loads S 1 through S 5 , listed in Table 3, each consisting of a certain number of traffic flows for each packet classes. For instance, traffic input set S 1 consists of 5 CP traffic flows, 10 DP flows, 20 RP flows and 30 OP flows.
To prevent buffering packets indefinitely, packets are dropped if they wait in the send buffer for more than their remaining lifetimes. All packets sent via the routing layer are queued at the interface queue until the MAC layer can transmit them. The interface queue has a maximum size of 60 packets and is maintained as a priority queue with four priorities, each served in FIFO order. Routing packets get higher priority than data packets.
The average result of 10 simulation runs is calculated for each graph point. For each simulation run, the active nodes are randomly selected, and the source node for each of the flows is also randomly selected. Thus, the variations in the obtained results mainly occur due to the randomness of the topology.
The error bars in the graphs parallel to the y-axis indicate the variations in the obtained results from the presented average values and, thus, show the minimum and maximum values obtained from the runs.

Simulation Results
We first evaluate the impacts of various traffic loads and bit error rates (BER) on the average end-to-end packet delay and the on-time packet delivery ratio. While the first parameter is measured as the average delay experienced by all classes of delivered packets to the sinks, the latter one is the ratio of the total number of packets received by the sinks to the number of packets generated by the sources.

Impact of Traffic Loads
The modular and distributed architecture of the proposed DMQoS framework helps it to achieve significant performance improvements over the state-of-the-art QoS-aware routing protocols, as shown in Figure 3. Recall (from Algorithms 1 and 2) that DMQoS optimizes the number of packet duplications based on measured link reliability (r i,j ) values and chooses the next-hop router that has the highest velocity toward the destination sink. The velocity prediction of DMQoS is more accurate than those of other methods since it takes into account both transmission and queuing delays at neighbor nodes. Furthermore, the routings of different classes of data packets are handled distinctly, giving highest priority to the critical traffic flows, thus ensuring more reliable and faster delivery of important information to the destination.
As source traffic load increases, the media contention increases as well, which in turn raises packet delays at each hop toward the destination. Figure 3(a) shows that, in all approaches, the end-to-end packet delay rises to higher values with increasing traffic load. The DMQoS offers the lowest end-to-end delay, and the gaps amongst the graphs are widened as traffic volume increases, indicating that DMQoS is more capable of handling high traffic volume compared to other approaches. On the other hand, MMSPEED suffers from the highest delay followed by LOCALMOR and DARA. Through careful examination of the details of our simulation, we observe that mainly exponential increase in packet duplication in MMSPEED, blind duplication of data packets toward primary and secondary sinks in LOCALMOR and the use of the same aggregate routing function both for critical and non-critical traffic in DARA cause more contention in the wireless medium, resulting in increased end-to-end packet delivery delays. Figure 3(b) shows that DMQoS demonstrates superior performance in terms of on-time packet delivery ratio, indicating that packet drops can greatly be reduced when source data packets are dispersed toward multiple sinks in a way that implements load-balancing among the paths by judiciously choosing the more reliable links and lightly loaded next-hop router nodes along the path. The simulation results indicate that the poor performances of LOCALMOR and MMSPEED protocols are primarily due to the excessive media contentions caused by huge numbers of duplicate packets in the networks. We also plotted the average end-to-end packet delays and delivery ratio experienced by CP traffic only in Figure 3(c) and Figure 3(d), respectively, and found that our DMQoS outperforms the existing approaches, evidencing the advantage of using the data-centric and scalable modular QoS-aware routing approach.

Impact of Bit Error Rate
In what follows, we investigate the impacts of wireless link bit error rates (BER) on the end-to-end packet delay and the reliability. We vary the BER value ranging from 10 −6 to 10 −2 , keeping the data traffic load fixed at S 3 .
With the increase of bit error rates packet delivery delay increases, and the probability of successful packet delivery decreases. More explicitly, higher value of BER raises the number of retransmissions required for each packet (at each hop) prolonging the per-hop packet delay and thereby the end-to-end delay. A packet is dropped by an intermediate node if the number of retransmissions exceeds its limit, diminishing the packet delivery ratio. However, by comparing the graphs in Figures 3 and 4, we find that the effect of bit error rate is much higher on the end-to-end delay than that on the packet delivery ratio. The reason is that, at moderate traffic loads, the contention in the wireless medium does not grow up that much, and thus, even though the packet delivery delay increases due to packet retransmissions, it can prevent the effect of bit error rates keeping the packet delivery ratio at an acceptable level. From the results of Figure 4, we also observe that our DMQoS is more robust to the wireless link bit error rates compared to other approaches. This result is characterized by several facts: (i) DARA's aggregate routing metric (i.e., weighted-linear combination of three sub-metrics) fails to select the most appropriate next-hop node for the traffic classes, i.e., it uses the same metric for CP, DP or RP traffic flows, (ii) excessive duplicate packets toward fixed number of sinks generated by LOCALMOR and MMSPEED cause high media contention and packet drops, and (iii) MMSPEED suffers most since its exponentially generated duplicated packets (along with the original packets) converge together somewhere near the single sink causing many packet drops due to collisions and buffer overflows. However, our DMQoS optimizes the number of duplicate packets, selects the most appropriate next-hop node using separate metrics for different packet classes and disperses the source traffic toward sinks offering lightly-loaded paths.

Impacts of Traffic Load and BER on Energy Consumption
In this experiment, we calculate the total amount of energy consumed for transmission and reception of a packet by source and forwarder nodes until it is received by a sink and average the values for all packets. Figures 5(a) and 5(b) show the average energy consumption per packet for varying source traffic loads and bit error rates in DMQoS and DARA, respectively. We observe that, in both approaches, the energy consumption rises up linearly for increasing source traffic loads and exponentially for increasing bit error rates. However, the rate of increase in DMQoS is slightly less than that in DARA. Our in-depth look into the simulation results reveals that this is mainly due to the reduced amount of packet collisions and retransmissions in DMQoS compared to those in DARA. As the source traffic load increases, the media contention increases as well and the data packets have to travel longer paths (for load-balancing) to reach their destinations and thus the per packet energy consumption is also increased. BER has more impacts on energy consumption since it forces packets to be retransmitted many times at each hop.
Protocol Operation Overhead One further issue to consider is the amount of energy overheads due to transmission and reception of routing control packets in different approaches for varying traffic loads and bit error rates. Every QoS provisioning scheme has to exchange additional control packets (in addition to those for the basic routing mechanism) in order to update the nodes with the current neighborhood information necessary to provide better QoS services, incurring extra overhead.
As expected theoretically, in all approaches, the amount of overhead quickly rises to higher values with increasing numbers of traffic sources. Because each source node needs to exchange routing control packets, the number of such control packets increases with the traffic load of the network as the routing parameters quickly vary. Figure 6(a) shows that MMSPEED incurs the highest overhead since it uses reliability and delay backpressure packets in addition to the neighborhood route information update messages; however, the overheads in the other three approaches are very close to each other as they all use only HELLO (or BEACON) packets to update single-hop neighborhood information. For the same reason, in Figure 6(b), we observe that the overheads in all approaches increase almost linearly with increasing bit error rates.

Discussions
The assembly efficiency of multiple paths is a great boon to unreliable sensor networks. Obviously, there may exist many feasible combinations. To save the energy cost, the set with minimum number of paths is chosen as the forwarding set (see Sections 4.2 and 4.3). We argue that sending a packet on more paths induces more energy cost, because more data packets have to be transmitted. Also, using more paths introduces more contentions which degrades energy efficiency. Even some paths in the set may have more hops, it is still more energy efficient to confine packets to a few paths. For the energy efficiency, as long as the delay and reliability constraints are satisfied we forward the data traffic over energy-rich nodes in order to implement an almost homogeneous energy dissipation rates for all sensor nodes in the network.
The main limitation of this paper is related to a lack of sufficient understanding about the dynamics of several estimation tuning parameters. For example, α, β and w n values were determined through numerous simulation experiments. If we could build an analytical model for them, we would be able to dynamically select the optimal values to adapt to different situations. We left it for future work.

Conclusions
Due to the overheads caused by implementing QoS in BSNs, QoS and energy must be considered together. In this paper, we have proposed a distributed flexible mechanism to optimize QoS and energy in multihop BSNs based on modular design architecture, following several traffic classes. The routing decision is localized and independent of traffic classes, which distinguishes DMQoS from other approaches. Energy is optimized among the set of candidate nodes offering data-centric QoS services (delay and/or reliability). The results signify that our data-centric multiobjective QoS-aware routing protocol provides a dynamic and modular approach for rendering quality data delivery services and is well suited to resource-constrained BSNs with comparable overhead to those of other methods.


Building an Intelligent Controller using Simple Genetic Type-2 Fuzzy Logic System

Despite the advantages offered by type-2 fuzzy systems (T2FS) in handling uncertainties in control applications, one major problem that hinders its wide-spread implementation in real-time applications is its high computational cost (Hameed, 2010). In order to reduce the computational burden of T2FS, a simplified T2FS based on a hybrid structure of four type-1 fuzzy systems (T1FS) and a genetic algorithm (GA) is introduced (Hameed, 2009). In addition to its rule in providing the system with adaptability to cope with changing conditions, a GA provides the system with a tool to detect and illustrate the amount of uncertainty incorporated in the system. In order to show the robustness and reliability of the new implementation, the developed approach is applied to: (a) control a nonlinear multiinput multi-output (MIMO) system equipped with various types of uncertainties as an example of using T2FS in industrial applications, and (b) evaluate students’ learning achievement as an example of using T2FS in decision support systems. The new implementation of T2FS showed a superior response compared to the very complex and computational costly type-reduction approach. In addition, the ease of using the new implementation, which does not require more than the basic knowledge of T1FS and GA, is expected to help advancing the application of T2FS in multiple different areas of applications. FLS constructed based on type-1 fuzzy systems (T1FS), referred to as T1FLS, have demonstrated their ability in many applications, especially for the control of complex nonlinear systems that are difficult to model analytically (Zadeh, 1973; King & Mamdani, 1997). However, researchers have shown that T1FLS have difficulty in modeling and minimizing the effect of uncertainties (Mendel, 2001). A reason being that, T1FS are certain in the sense that for each input there is a crisp membership grade. T2FS, characterized by membership grades that are themselves fuzzy, were first introduced by Zadeh in 1975 to account for this problem (Zadeh, 1975a). As it is illustrated in Fig. 1, the MF of a T2FS has a footprint of uncertainty (FOU), which represents the uncertainties in the shape and position of T1FS (Wu & Tan, 2004). The FOU is bounded up by an upper MF (UMF) and lower by a lower MF (LMF), both of which are T1MF. Since the FOU of T2FS provides an extra mathematical dimension, they are very useful in circumstances where it is difficult to determine an exact membership grade for FS. Therefore, the amount of uncertainty in a system could be reduced by using T2FLS since it offers better capabilities to handle

148
linguistic uncertainties by modeling vagueness and unreliability of information and hence have the potential to outperform its T1 counterpart (Karnik & Mendel, 2001;Sepulveda et al., 2007a). The ability of T2FLS to eliminate persistent oscillations surpasses that of its T1 counterpart. One reason is that the control surface of a T2FLS is smoother than that of T1FLS, especially around the origin (Tan & Pall, 2003). As a result, small disturbances around steady state will not result in significant control signal changes and thus minimizing the amount of oscillation. The additional degree of freedom provided by the FOU allows T2FLS to handle modeling uncertainties better than conventional T1FLS can do. This advantage is practically useful because many fuzzy controllers are designed offline using genetic algorithms (GA) and a model of the controlled process. As it is impossible for a model to capture all the characteristics of the actual plant, the performance of a controller designed using a model will inevitably deteriorate when it is applied to the actual plant, therefore a controller that is equipped with the ability to handle modeling uncertainties would be valuable. Despite the advantages offered by T2FLS, one major problem that may hinder its use in realtime applications is its high computational cost. Type-reduction, which is used to convert T2FS into T1FS so that they can be processed by the defuzzifier to give a crisp output, is very computationally intensive, especially when there are many MFs and the rule base is large (Karnik & Mendel, 1998, 1999. To reduce the computational burden while preserving the advantages of T2FLS, two approaches may be considered: 1) faster type-reduction methods, such as the uncertainty bound method (Wu & Mendel, 2002); and 2) a simpler architecture, such as using only one T2FS in each input domain (Wu & Tan, 2004). In this chapter, a simplified implementation of T2FLS is proposed. The proposed approach only requires the basic knowledge of T1FLS and GA. Fuzzy Logic Toolbox™ and Optimization Toolbox™ from MathWorks™ are used for carrying out this purpose. The rest of the chapter is organized as follows: Section 2 introduces the proposed simplified implementation of T2FLS using four embedded T1FSs. How GA is used to adjust the controller parameters is described in Section 3. The greenhouse climate control (GCC) problem and a simulation study to assess the ability of the proposed implementation to handle uncertainties are presented in Section 4. Finally, conclusions are drawn in Section 5.

A simplified implementation of T2FS
As illustrated in Fig. 1, a T2FS could be obtained by blurring a T1FS. A Gaussian T1FS is often used to represent vague linguistic terms and it is given by: where ci and σi are the center and width of the ith fuzzy set Ai, respectively, i = 1, 2, …, n, and n is the total number of MFs used to represent a universe of discourse. A Gaussian MF (GMF) with uncertain width (i.e., variance) is obtained by blurring its width and keeping its mean (i.e., center) fixed, as shown in Fig. 1(a). On the other hand, a GMF with an uncertain center is obtained by blurring its center and keeping its width fixed, as shown in Fig. 1(b). In this paper and for the sake of simplicity, GMF with uncertain width has been adopted. The upper and lower bounds of a Gaussian T2FS with uncertain width could be represented by: where Ui Li σ σ ≥ , shown in Fig. 1 (a). The upper and lower bounds of each GMF can be further decomposed into the left and the right side MF and represented in the form: A T2FS can be thought of as a set of an infinite number of T1FSs, and correspondingly, the defuzzified output of T2FLS could be obtained by aggregating the centroids of an infinite number of embedded T1FLSs. When the antecedent and consequent membership grades in T2FLS have a continuous domain, the number of embedded T1FLSs becomes uncountable. For the sake of simplicity and without loss of generality, each T2MF will be represented by its upper (U) and lower (L) bounds which are T1MFs, as shown in Fig. 2. Therefore, each two neighbor T2MFs will intersect in four points instead of one point as is MFs constitute the upper, right, lower and left intersection points will be used as the input/output MFs of the upper, right, lower and left T1FLSs respectively. The defuzzified output of the T2FLS is then obtained by averaging the defuzzified outputs of the resultant four embedded T1FLSs, as shown in Fig. 4. When uncertainty equals zero, the four intersection points become one and T2MF degrades to T1MF. Therefore, the proposed structure will vary between T1 and T2 according to the level of uncertainty detected in the system. The proposed method has more degrees of freedom compared to the method represented by Sepulveda and his colleagues in which type-2 MF is decomposed into only UMF and LMF (Sepulveda et al., 2007a;Sepulveda et al., 2007b Fig. 4. Simplified type-2 fuzzy logic system: controller output is the average of the four outputs of the embedded upper, left, right, and lower type-1 fuzzy logic systems, x 1 and x 2 are the controller inputs and y is the controller output. Holland in 1975(Holland, 1975Goldberg, 1988). In this chapter, a GA will be used to evolve the parameters of the proposed implementation of T2FLS to test the hypothesis that the simplified architecture retains the ability to handle measurement and modeling uncertainties. It is not mandatory to use a GA to adjust the controller parameters and instead the controller parameters could be set manually. GA will not only be used as an optimization algorithm but rather it will be used as an uncertainty sensor to detect the level of uncertainty which exist in the controlled system. In other applications such as students\s evaluation, GA can not be used and a proper thickness of T2FS would be manually selected. The thickness of a T2FS will increase as the amount of uncertainty detected in the systems is increased and vice versa. When the uncertainty level is very low or zero, the thickness of a T2FS will equal to zero and the controller will simply behave like a T1FLS. In this chapter, seven MFs are used. The centers of the MFs are set constant, -1 for negative big (NB), -2/3 for negative medium (NM), -1/3 for negative small (NS), 0 for zero (Z), 1/3 for positive small (PS), 2/3 for positive medium (PM) and 1 positive big (PB) and their optimum widths are obtained using a real-valued GA. Each T2GMF has two widths, U σ and L σ where UL σ σ ≥ while T1GMF has only one width value, σ . Since each controller input and output variables are set to the same range of universe of discourse, [-1, 1], three additional parameters, called scale factors (SFs), could be tuned. SFs are real constants which multiply the values of the variables (input or output variables), modifying the limits of their variation range, and therefore have a significant impact on the performance of the resulting fuzzy control system, and hence they are often a convenient parameter for tuning. The modification of the input scale factors has a general effect on the behaviour of the system: increasing input gains implies reducing their universes of discourse, having a direct consequence on control: the response is faster and more oscillatory, reducing the stationary error. It thus improves the transient response by reducing rise time and set-up time, but it does increase the risk of instability with the overshoot increment. On the other side, reducing input gains produces the opposite effects; the wider the membership functions the rougher control can be achieved, which produces a slower response with less overshoot. However, the variation of the output gain has a complex relation with the behaviour of the controller and has not been analysed in depth (Rojas et al., 2006). For the sake of simplicity, it is assumed that all MFs have equal widths. For T2FLS, five parameters namely, U σ , L σ , SF 1 , SF 2 , and SF 3 and for T1FLS, four parameters, namely, σ , SF 1 , SF 2 , and SF 3 have to be tuned. For the proposed T2FLS, up to 4(2n+3) parameters could be optimized, where 4 stands for 4 embedded T1FLSs, 2 stands for the center and the width of the GMF, n stands for the number of MFs used in universe of discourse, and 3 stands for 3 SFs of the input and output parameters of each embedded T1FLS, which could result in better results but also requires greater computational costs. The fitness function used to quantify the optimality of a solution (i.e., chromosome) is the reciprocal of the Integral of Square Error (ISE), given in Eq. (8) where the error e is the difference between the desired set point and the actual system output (Sepulveda et al., 2007b). Chromosomes in a population are ranked according to their fitness value. Optimal or near optimal chromosomes (i.e., solutions) are allowed to reproduce through new generations that will (hopefully) be even better. In this paper, the maximum number of generations is set to 30. The number of chromosomes or solutions in a population is set to 20. The mutation and crossover probability are set to 0.2 and 0.25 respectively. The roulette wheel selection method is used to select the fittest chromosomes, the generational process is repeated until a termination condition has been reached; a solution is found that satisfies minimum criteria or a fixed number of generations reached.

Simulation experiments
In this section, the developed implementation of T2FS will applied to Greenhouse climate control (GCC) problem as an example of an industrial application. It will also applied to the problem of students' evaluation as an example of using T2FS as a decision support system. GCC has received considerable attention in agricultural engineering research (Albright et al., 2001;Koutb et al., 2004;Van Henten & Bontsema, 2009). Controlling the climate inside a greenhouse is a challenging task because of the many sources of uncertainty. Such uncertainty could arise from using none or near accurate models, greenhouse orientation, age and type of crop inside the greenhouse, sensor measurements, actuators and outdoor climate conditions. In this chapter, a simple greenhouse heating-cooling ventilating (HCV) model will be used to control temperature and humidity ratio inside a greenhouse by means of heating, ventilating, and humidifying the air inside the greenhouse. ). In this chapter, two types of uncertainty will be introduced to the system to evaluate the performance of the proposed controller; 1) measurement uncertainty which is introduced to the system by adding random noise to sensory measurements, and 2) modeling uncertainty which is introduced to the system by changing the model parameters by ±10%. A first simulation experiment has been conducted to demonstrate the ability of control scheme to provide non-interacting control and smooth closed-loop response to set-point step change. Measurement uncertainty has been introduced by adding a 10% multiplicative error to all the measured signals. The responses for set-point step changes in temperature and humidity ratio for T1 and T2 controllers are shown in Fig. 5. Fig. 6 illustrates the controller outputs. A simulation of the outside weather conditions of a normal hot day are shown in Fig. 7. The T1MFs and T2MFs for both temperature and humidity loops are shown in Fig. 8, respectively. Fig. 9 illustrates the control surface for both T1 and T2 controllers, respectively.       Table 1. Parameters of type-1 (T1) and type-2 (T2) fuzzy logic controllers obtained by GA where measurement uncertainty is introduced in experiment 1 and modeling uncertainty is introduced in experiment 2. SF e , SF Δe , and SF Δu are the scale factors of error, change of error and change of control signal respectively.
The parameters of T1 and T2 controllers are shown in Table 1. From the table, the difference between σ L and σ U increases as the level of uncertainty detected in the system increases. For the sake of comparison, Mean Squared Error (MSE) and Signal-to-Noise Ration (SNR) for temperature and humidity loops are computed for T1, T2 (the proposed structure), T2 structure proposed by Sepulveda and his colleagues (Sepulveda et al., 2007b) and T2 using type-reduction method (Mendel, 1998), as shown in Table 2. Although the performance of the proposed structure of T2FLS using four embedded T1FLSs is similar to the performance of T2 using type-reduction (T2TR) but implementing T2TR requires acquiring new knowledge and writing new codes but in the case of the proposed T2 structure using four embedded T1FLSs, only the basic knowledge of T1 fuzzy sets is required and take the advantage of using MATLAB® Fuzzy Logic Toolbox™ and Optimization Toolbox™ from MathWorks™ for ease of implementation. Type-2 fuzzy controller using type-reduction method 1.7439 0.0294 0.0309 Table 2. Mean squared error (MSE) and signal-to-noise ratio of temperature (SNRT) and humidity ratio (SNRH) of different types of controllers when measurement uncertainty is introduced in experiment 1 and modeling uncertainty is introduced in experiment 2 Saleh and Kim (2009) proposed a three nodes fuzzy system to evaluate students' learning achievement. The transparency and objective nature of the fuzzy system makes their method easy to understand and enables teachers to explain the results of the evaluation to sceptic students. The method involved conventional triangular MFs of fixed parameters which could result in different results when changed. In order to improve the reliability and robustness of the system, Gaussian membership functions (GMFs) are proposed as an alternative to the traditional triangular MFs (Hameed & Sorensen, 2010). When the three nodes system based on Gaussian membership of width of 4.0 is applied to all students, the resultant new total scores of students rounded to two digits are equal to that of the classical scores but with new ranking orders. The same result is obtained when the T2FS for σ L and σ U of 0.2 and 0.4, respectively, are applied.

Conclusions
The proposed architecture of Type-2 FLS using four embedded Type-1 FLSs provides a smoother control surface and a greater ability to detect and treat the measurement and modeling uncertainties in the controlled system with the aid of a GA. It also achieved a dramatic reduction in computational complexity without sacrificing performance compared to its equivalent type-2 FLS with type-reduction method. The proposed T2FLS is easy to implement using MATLAB® Fuzzy Logic Toolbox™ from MathWorks™ and it does not require more than the basic knowledge of T1FLS.