Final-volume 3 No 5

ADAPTIVE FUZZY CONTROLLER TO CONTROL TURBINE SPEED K. Gowrishankar, Vasanth Elancheralathan Rajiv Gandhi College Of Engg. & tech., Puducherry, India [email protected], [email protected] Abstract: It is known that PID controller is employed in every facet of industrial automation. The application of PID controller span from small industry to high technology industry. In this paper, it is proposed that the controller be tuned using Adaptive fuzzy controller. Adaptive fuzzy controller is a stochastic global search method that emulates the process of natural evolution. Adaptive fuzzy controller have been shown to be capable of locating high performance areas in complex domains without experiencing the difficulties associated with high dimensionality or false optima as may occur with gradient decent techniques. Using Fuzzy controller to perform the tuning of the controller will result in the optimum controller being evaluated for the system every time. For this study, the model selected is of turbine speed control system. The reason for this is that this model is often encountered in refineries in a form of steam turbine that uses hydraulic governor to control the speed of the turbine. The PID controller of the model will be designed using the classical method and the results analyzed. The same model will be redesigned using the AFC method. The results of both designs will be compared, analyzed and conclusion will be drawn out of the simulation made. Keywords: Tuning PID Controller, ZN Method, Adaptive fuzzy controller.

1

INTRODUCTION

Since many industrial processes are of a complex nature, it is difficult to develop a closed loop control model for this high level process. Also the human operator is often required to provide on line adjustment, which make the process performance greatly dependent on the experience of the individual operator. It would be extremely useful if some kind of systematic methodology can be developed for the process control model that is suited to kind of industrial process. There are some variables in continuous DCS (distributed control system) suffer from many unexpected disturbance during operation (noise, parameter variation, model uncertainties, etc.) so the human supervision (adjustment) is necessary and frequently. If the operator has a little experience the system may be damage or operated at lower efficiency [1, 4]. One of these systems is the control of turbine speed PI controller is the main controller used to control the process variable. Process is exposed to unexpected conditions and the controller fail to maintain the process variable in satisfied conditions and retune the controller is necessary. Fuzzy controller is one of the succeed controller used in the process control in case of model uncertainties. But it may be difficult to fuzzy controller to articulate the accumulated knowledge to encompass all circumstance. Hence, it is essential to provide a

UbiCC Journal - Volume 3

tuning capability [2, 3]. There are many parameters in fuzzy controller can be adapted. The Speed control of turbine unit construction and operation will be described. Adaptive controller is suggested here to adapt normalized fuzzy controller, mainly output/input scale factor. The algorithm is tested on an experimental model to the Turbine Speed Control System. A comparison between Conventional method and Adaptive Fuzzy Controller are done. The suggested control algorithm consists of two controllers process variable controller and adaptive controller (normalized fuzzy controller).At last, the fuzzy supervisory adaptive implemented and compared with conventional method. 2

BACKGROUND

In refineries, in chemical plants and other industries the gas turbine is a well known tool to drive compressors. These compressors are normally of centrifugal type. They consume much power due to the fact that very large volume flows are handled. The combination gas turbine-compressor is highly reliable. Hence the turbine-compressor play significant role in the operation of the plants. In the above set up, the high pressure steam (HPS) is usually used to drive the turbine. The turbine which is coupled to the compressor will then drive the compressor. The hydraulic governor which, acts as a

1

control valve will be used to throttle the amount of steam that is going to the turbine section. The governor opening is being controlled by a PID which is in the electronic governor control panel. In this paper, it is proposed that the controller be tuned using the Genetic Algorithm technique. Using genetic algorithms to perform the tuning of the controller will result in the optimum controller being evaluated for the system every time. For this study, the model selected is of turbine speed control system. Electronic Governor Control system

Speed SP HPS

Control Valve Opening (MV)

GT Turbine

Speed Signal (PV)

KP Compressor

Figure 1: Turbine Speed Control The reason for this is that this model is often encountered in refineries in a form of steam turbine that uses hydraulic governor to control the speed of the turbine as illustrated above in figure 1. The complexities of the electronic governor controller will not be taken into consideration in this dissertation. The electronic governor controller is a big subject by it and it is beyond the scope of this study. Nevertheless this study will focus on the model that makes up the steam turbine and the hydraulic governor to control the speed of the turbine. In the context of refineries, you can consider the steam turbine as the heart of the plant. This is due to the fact that in the refineries, there are lots of high capacities compressors running on steam turbine. Hence this makes the control and the tuning optimization of the steam turbine significant. 3

EXPERIMENTAL PROCESS IDENTIFICATION

To obtain the mathematical model of the process i.e. to identify the process parameters, the process is looked as a black box; a step input is applied to the process to obtain the open loop time response. From the time response, the transfer function of the open loop system can be approximated in the form of a third order transfer function:

UbiCC Journal - Volume 3

𝐺 𝑠 =

1 𝑆 𝑆+1 (𝑆+5)

(1)

The identified model is approximated as a linear model, but exactly the closed loop is nonlinear due to the limitation in the control signal. 4

PID CONTROLLER

PID controller consists of Proportional Action, Integral Action and Derivative Action. It is commonly refer to Ziegler-Nichols PID tuning parameters. It is by far the most common control algorithm [1]. In this chapter, the basic concept of the PID controls will be explained. PID controller’s algorithm is mostly used in feedback loops. PID controllers can be implemented in many forms. It can be implemented as a stand-alone controller or as part of Direct Digital Control (DDC) package or even Distributed Control System (DCS). The latter is a hierarchical distributed process control system which is widely used in process plants such as pharceumatical or oil refining industries. It is interesting to note that more than half of the industrial controllers in use today utilize PID or modified PID control schemes. Below is a simple diagram illustrating the schematic of the PID controller. Such set up is known as non- interacting form or parallel form. P I/P

I

P

Plant

D

Figure 2: Schematic of the PID Controller – NonInteracting Form In proportional control, Pterm = KP x Error

(2)

It uses proportion of the system error to control the system. In this action an offset is introduced in the system. In Integral control, Iterm = K1 x Error dt

(3)

It is proportional to the amount of error in the system. In this action, the I-action will introduce a lag in the system. This will eliminate the offset that was introduced earlier on by the P-action.

2

In Derivative control,

𝐷𝑡𝑒𝑟𝑚 = 𝐾𝐷𝑥

𝑑(𝐸𝑟𝑟𝑜𝑟) 𝑑𝑡

(4)

It is proportional to the rate of change of the error . In this action, the D-action will introduce a lead in

If the maximum overshoot is excessive says about greater than 40%, fine tuning should be done to reduce it to less than 25%. From Ziegler-Nichols frequency method of the second method [1], the table suggested tuning rule according to the formula shown. From these we are able to estimate the parameters of Kp, Ti and Td.

the system. This will eliminate the lag in the system that was introduced by the I-action earlier on. Controller 5

OPTIMISING PID CONTROLLER BY CLASSICAL METHOD

For the system under study, Ziegler-Nichols tuning rule based on critical gain Ker and critical period Per will be used. In this method, the integral time Ti will be set to infinity and the derivative time Td to zero. This is used to get the initial PID setting of the system. This PID setting will then be further optimized using the “steepest descent gradient method”. In this method, only the proportional control action will be used. The Kp will be increase to a critical value Ker at which the system output will exhibit sustained oscillations. In this method, if the system output does not exhibit the sustained oscillations hence this method does not apply. In this chapter, it will be shown that the inefficiency of designing PID controller using the classical method. This design will be further improved by the optimization method such as “steepest descent gradient method” as mentioned earlier [6]. 5.1 Design of PID Parameters From the response below, the system under study is indeed oscillatory and hence the Z-N tuning rule based on critical gain Ker and critical period Per can be applied. The transfer function of the PID controller is Gc(s) = Kp (1 + Ti (s) + Td(s)) (5) The objective is to achieve a unit-step response curve of the designed system that exhibits a maximum overshoot of 25 %.

P PI PID

Kp

Ti

Td

0.5Ker 0.45Ker

 1 / 1.2 Per

0 0 0.125 Per

0.6 Ker

0.5 Per

Figure 4: PID Value setting Consider a characteristic equation of closed loop system 3 2 s + 6s + 5s+ Kp = 0 From the Routh’s Stability Criterion, the value of Kp that makes the system marginally stable can be determined. The table below illustrates the Routh array.

s³ s² s¹ sº

1 6 (30-Kp)/6 Kp

5 Kp 0 -

With the help of PID parameter settings the obtained closed loop transfer function of the PID controller with all the parameters is given as

𝐺𝑐 (𝑆) = 𝐾𝑝 (1 + = 18 ( 1 +

=

1 + 𝑇𝑖𝑆

𝑇𝑑𝑆)

1 + 0.3512 ) 1.4𝑆

6.3223 ( 𝑆+1.4235 )2 𝑆

(6) From the above transfer function, we can see that the PID controller has pole at the origin and double zero at s = -1.4235. The block diagram of the control system with PID controller is as follows. R(s) 6.3223

(S  1.4235) S

2

1 S ( S  1)( S  5)

PID

ControllerFeedback Figure 3: Illustration of Sustained Oscillation

UbiCC Journal - Volume 3

Figure 5: Illustrated Closed Loop Transfer Function

3

Hence the above block diagram is reduced to C R

( s )

6.3223s 2 17.999s 12.8089 s 4  6s3  5s 2

( s )

Figure 6: Simplified System Therefore the overall close loop system response of 𝐶𝑆 6.3226𝑆2 + 17.999𝑠 + 12.808 = 4 𝑅𝑆 𝑆 + 6𝑆3 + 11.3223𝑆2 + 18𝑠 + 12.8089

(7) The unit step response of this system can be obtained with MATLAB.

5

OPTIMIZING OF THE DESIGNED PID CONTROLLER

The optimizing method used for the designed PID controller is the “steepest gradient descent method”. In this method, we will derive the transfer function of the controller as the minimizing of the error function of the chosen problem can be achieved if the suitable values of can be determined. These three combinations of potential values form a three dimensional space. The error function will form some contour within the space. This contour has maxima, minima and gradients which result in a continuous surface. In this method, the system is further optimized using the said method. With the “steepest descent gradient method”, the response has definitely improved as compared to the one in Fig. 9 (a). The settling time has improved to 2.5 second as compared to 6.0 seconds previously. The setback is that the rise time and the maximum overshoot cannot be calculated. This is due to the “hill climbing” action of the steepest descent gradient method. However this setback was replaced with the quick settling time achieved. Below is the plot of the error signal of the optimized controller. In the figure below it is shown that the error was minimized and this correlate with the response shown in Figure 9(b).

Figure 7: Step Response of Designed System To optimize the response further, the PID controller transfer function must be revisited. The transfer function of the designed PID controller is

𝐺𝑐 (𝑍) =

𝑞𝑜+ 𝑞1𝑍−1 +𝑞2𝑍−2 1−𝑍−1

Figure 8: Improved System.

UbiCC Journal - Volume 3

(8)

Figure 9 (a) & (b): Optimization of Steepest Descent Gradient Method & Error Signal

4

From the above figure, the initial error of 1 is finally reduced to zero. It took about 2.5 to 3 seconds for the error to be minimized. 6

IMPLEMENTATION OF ADAPTIVE FUZZY CONTROLLER ON EXPERIMENT CASE STUDY

6.1

Normalized Fuzzy Controller

To overcome the problem of PID parameter variation, a normalized Fuzzy controller with adjustable scale factors is suggested. In our experimental case study, the fuzzy controller designed has the following parameters: • Membership functions of the input/output signals have the same universe of discourse equal to 1 • The number of membership functions for each variable is 5 triangle membership functions denoted as NB (negative big), NS (negative small), Z (zero), PS (positive small) and PB (positive big) as shown in Fig. 10.

NB

NM

-1

Z

PM

PB

0

0.5

1

-0.5

Figure 10: Normalized membership function of inputs and output variables • Fuzzy allocation matrix (FAM) or Rule base as in Table1. Table 1: FAM Normalized Fuzzy Controller e NB

NM

Z

PM

PB

NB

PB

PB

PM

Z

Z

NM

PM

PB

PM

Z

Z

Z

PM

PM

Z

NM

NM

PM

Z

Z

NM

NB

NB

PB

Z

NM

NB

NB

NB

e

• Fuzzy inference system is mundani. • Fuzzy inference methods are “min” for AND, “max”for OR, “min” for fuzzy implication, “max” for fuzzy aggregation (composition), and “centroid” for Defuzzification. Adjusting the gains according to the simulation results, the system responses for different input/output gains are shown in Fig. 11.

UbiCC Journal - Volume 3

Figure 11: Actual responses for different input output gains From the analysis of the above responses, we can conclude that: • Decreasing input scale factors increase the response offset. • Increasing output scale factor fasting the response of the system but may cause some oscillation. So the selection must compromise between input and output scale factors. In the following section we try to adapt the output scale factor with constant input scale factor at 10 error scale, and 15 rate of error scale based on manual tuning result. There are two method tested to adapt the output scale factors, GD (Gradient Decent) adaptation method and supervisor fuzzy. 6.2 Fuzzy Supervisory Controller In this method I try to design a supervisor fuzzy controller to change the scale factors online design of the supervisor can be constructed by two methods: a) Learning method b) Experience of the system and main requirements must be achieved. In this paper, the supervisor controller is built according to the accumulative knowledge of the previous tuning methods. The supervisor fuzzy controller has the following parameters: • The universe of discourse of input and output is selected according to the maximum allowable range and that is depend on process requirements • The number of membership functions for input variables is 3 triangle membership functions denoted as N (negative), Z (zero) and P (positive). For output variable is 2 membership functions denoted as L (low) and H (High) as shown in Fig, 12.

5

N

Z

-1

0

P

N

1

Z

-1

a) Error

0

P

1

b) rate of error

L

two responses are almost similar. The response of supervisor fuzzy is relatively faster. Tuning both input and output scale factors using supervisor controller, the supervisor fuzzy will be multi-input multi-output fuzzy controller without coupling between the variables, i.e. the same supervisor algorithm is applied to each output individually with different universe of discourses.

H

6 10 c) Output Scale Factor Figure 12: Membership Function of Inputs and Output of supervisory fuzzy control • Fuzzy allocation matrix (FAM) or rule base as in Table 2.

Figure 14: System responses for single and multioutput supervisor

Table 2: FAM of Supervisory Fuzzy Controller

e e N Z P

N

Z

P

H L L

H L H

L H H

• Fuzzy Interference system is mundani. • Fuzzy Inference methods are “min” for AND, “max” for OR, “min” for fuzzy implication, “max” for fuzzy aggregation (composition), and “centroid” for Defuzzification.

+ Ref ere nce Mo del

+

Inp ut Sca le

-

Superv isory Fuzzy Control ler Normal ized Fuzzy Control ler

Contr oller

Out put Sca le

All the previous results are taken with considering that the reference response is step. In practice, there is no physical system can be changed from initial value to final value in now time. So, the required performance is transferred to a reference model and the system should be forced to follow the required response (overshoot, rise time, etc.). The desired specification of the system should to be: overshoot≤ 20%; rise time ≤ 150sec; based on the experience of the process. The desired response which achieves the desired specification is described by equation. yd(t)=A*[1-1.59e-0.488tsin 0.3929t+38.83*π/180)] (9) Where A: step required. Fig. 15 compares between the two responses at different values and reference model response. This indicates a good responses and robustness controller.

Pro ces s

Figure 13: Supervisory Fuzzy Controller Firstly, we supervise the output gain only as in GD method to compare between them. Reference model is a unity gain. Fig. 14 shows the system response using supervisory fuzzy controller. The

UbiCC Journal - Volume 3

Figure 15: Analysis of Steepest gradient & Adaptive Fuzzy Method

6

8

RESULTS OF IMPLEMENTED ADAPTIVE FUZZY CONTROLLER

In the following section, the results of the implemented Adaptive Fuzzy Controller will be analyzed [4]. The Adaptive Fuzzy designed PID controller is initially initialized and the response analyzed. The response of the Adaptive Fuzzy designed PID will then be analyzed for the smallest overshoot, fastest rise time and the fastest settling time. The best response will then be selected. From the above responses fig 15, the Adaptive Fuzzy designed PID will be compared to the Steepest Descent Gradient Method. The superiority of Adaptive Fuzzy Controller against the SDG method will be shown. The above analysis is summarized in the following table. Table 3: Results of SDGM Designed Controller and Adaptive Fuzzy Designed Controller. Measuring Factor

SDGM Controller

AF Controller

% Improvement

Rise Time

10

0.592

40.8

NA

4.8

NA

2.5

1.66

33.6

designed PID is much better in terms of the rise time and the settling time. The steepest descent gradient method has no overshoot but due to its nature of “hill climbing”, it suffers in terms of rise time and settling time. With respect to the computational time, it is noticed that the SDGM optimization takes a longer time to reach it peak as compare to the one designed with GD. This is not a positive point if you are to implement this method in an online environment. It only means that the SDGM uses more memory spaces and hence take up more time to reach the peak. This paper has exposed me to various PID control strategies. It has increased my knowledge in Control Engineering and Adaptive Fuzzy Controller in specific. It has also shown me that there are numerous methods of PID tunings available in the academics and industrial fields. 10 [1]

[2] Max. Overshoot Settling Time

[3]

From Table 3, we can see that the Adaptive Fuzzy designed controller has a significant improvement over the SDGM designed controller. However the setback is that it is inferior when it is compared to the rise time and the settling time. Finally the improvement has implication on the efficiency of the system under study. In the area of turbine speed control the faster response to research stability, the better is the result for the plant. 9

[4]

[5]

[6]

REFERENCES Astrom, K., T. Hagglund: PID Controllers; Theory, Design and Tuning, Instrument Society of America, Research Triangle Park, 1995. M. A. El-Geliel: Supervisory Fuzzy Logic Controller used for Process Loop Control in DCS System, CCA03 Conference, Istanbul, Turkey, June 23/25, 2003. Kal Johan Astroum and Bjorn Wittenmark: Adaptive control, Addison-Wesley, 1995 Yager R. R. and Filer D. P.: Essentials of Fuzzy Modeling and Control, John Wiley, 1994. J. M. Mendel: Fuzzy Logic Systems for Engineering: A tutorial, Proc. IEEE, vol. 83, pp. 345-377, 1995. L. X. Wang: Adaptive Fuzzy System & Control design & Stability Analysis, Prentice-Hall, 1994.

CONCLUSION

In conclusion the responses had showed to us that the designed PID with Adaptive Fuzzy Controller has much faster response than using the classical method. The classical method is good for giving us as the starting point of what are the PID values. However the approached in deriving the initial PID values using classical method is rather troublesome. There are many steps and also by trial and error in getting the PID values before you can narrow down in getting close to the “optimized” values. An optimized algorithm was implemented in the system to see and study how the system response is. This was achieved through implementing the steepest descent gradient method. The results were good but as was shown in Table 3 and Figure 15. However the Adaptive Fuzzy

UbiCC Journal - Volume 3

7

MIDDLEWARE FOR UBIQUITOUS ACCESS TO MATHEMATICAL EXPRESSIONS FOR VISUALLY-IMPAIRED USERS Ali Awde1, Manolo Dulva Hina1,2, Chakib Tadj1 Université du Québec, École de technologie supérieure, Montréal Québec, Canada 2 PRISM Laboratory, Université de Versailles-Saint-Quentin-en-Yvelines, France [email protected], [email protected], [email protected] Yacine Bellik, Université de Paris-Sud, France LIMSI-CRNS, Université de Paris-Sud, France [email protected] Amar Ramdane-Cherif 2,3 3 LISV Laboratory, Université de Versailles-Saint-Quentin-en-Yvelines, France [email protected] 1

ABSTRACT Providing visually-impaired users with ubiquitous access to mathematical expressions is a challenge. Our investigation indicates that most, if not all, of the current state-of-the art systems and solutions for presentation of mathematical expressions to visually-impaired users are generally not pervasive, that they do not take into account the user’s interaction context (i.e. combined contexts of the user, his environment and his computing system) into their system’s configuration and that they present mathematical expressions in only one format. We address these weaknesses by providing a middleware that provides a ubiquitous access to mathematical expressions. Our middleware gathers various suppliers in which one supplier is selected based on its suitability to the given instance of interaction context and of the user’s preferences. The configuration of the chosen supplier, including its quality of service (QoS) dimensions, is also adaptive to the user’s preferences. This paper discusses the challenges in designing this middleware and presents a proposed solution to each of these challenges. This paper discusses the concepts and principles applied on the middleware design as well as their validation through case studies and formal specification. This work is intended to contribute on the ongoing research to make informatics accessible to handicapped users, specifically providing them ubiquitous access to mathematical expressions. Keywords: pervasive computing, visually-impaired users, expressions presentation, multimodal computing, adaptive system.

1

INTRODUCTION

In pervasive computing [1], the user can continue working on his computing task whenever and wherever he wishes. The task is usually realized through the use of one or more software applications. If the task is the ubiquitous access to mathematical expressions for visually-impaired users, then the applications are those that will correctly present mathematical expressions to these users with special needs. There are available applications that can do the task. Hence, instead of inventing another one, it is more practical to collect all these applications and put them in one middleware. The middleware then selects an application, henceforth called a supplier, based on its suitability to the given context. The quality-of-service (QoS) dimensions of the chosen supplier are also configured based on user’s preferences.

UbiCC Journal - Volume 3

mathematical

To realize the ubiquity of documents containing mathematical expressions, the document is stored in a server and its copy is replicated on every member of the server group, making it accessible to the user whenever and wherever he wishes. The mathematical document serves as input file to the middleware. This research work is a result of an investigation of the current state-of-the-art systems and solutions in which we found out that the available systems for presentation of mathematical expressions to visually-impaired users are not pervasive; that most of them do not take into account the current interaction context in the system’s configuration and that the prevailing systems provide only one type of format for the presentation of mathematical expressions. As such, they are not multimodal. Our work addresses these weaknesses. This paper presents the concepts and principles

8

used in the design of this middleware. Data validation is done through case studies and formal specifications. This proposed middleware is functional under these assumed conditions: (i) that wired and wireless communication facilities are available to support our system, (ii) that the mathematical expression as input to the middleware is stored in a MathML [2] or LaTex [3] input file, and (iii) that there are available application suppliers and media devices to support the optimal modalities selected by the middleware. Apart from this introductory section, the rest of this paper is structured as follows. Section 2 provides a brief review of the state of the art related to our work; Section 3 lists down the challenges, proposed solutions and contributions of our work. Section 4 presents the infrastructure and system architecture of our middleware. In Section 5, we explain the concept of machine learning in relation to the system design so it adapts seamlessly to the given interaction context. Section 6 presents our methodology to configure an application supplier and optimize settings, taking into account user’s satisfaction. Section 7 discusses interaction contexts, modalities and media devices that characterize a typical scenario of a blind user trying to access mathematical expressions. Through scenario simulations in Section 8, we show the design specification of our infrastructure. Future works and conclusion are presented in Section 9. 2

REVIEW OF THE STATE OF THE ART

To a visually-impaired user, the mere understanding of a mathematical expression is already a challenge. It requires repeated passage on an expression where user often skips secondary information only to revert back to it again and again until he fully grasps the meaning of the expression. A complicated task like this is explained in [4]. Fortunately, some applications were developed to lessen the complexity of performing similar task, some of them are MathTalk [5], Maths [6] and AudioMath [7, 8]. MathTalk and Maths convert a standard algebraic expression into audio information. In Maths, the user can read, write and manipulate mathematics using a multimedia interface containing speech, Braille and audio. VICKIE (Visually Impaired Children Kit for Inclusive Education) [9] and BraMaNet (Braille Mathématique sur InterNet) [10] are transcription tools that convert mathematical document (in LaTex, MathML, HTML, etc.) to its French Braille representation. Labradoor (LaTex-to-Braille-Door) [11] converts an expression in LaTex into its Braille equivalent using the Marburg code. MAVIS (Mathematics Accessible To Visually Impaired Students) [12] supports LaTex to Braille translation via Nemeth code. As a background, some special Braille notations have been developed for mathematics, different

UbiCC Journal - Volume 3

countries adopting different Braille code notations. Some of these are the Nemeth Math code [13] which is used in the USA, Canada, New Zealand, Greece and India; the Marburg code [14] used in Germany and Austria, the French Math code [15]. Lambda [16] translates expression in MathML format into multiple Braille Math codes that are used in the European Union. ASTER (Audio System for Technical Readings) [17] reformats electronic documents written in LaTeX into their corresponding audio equivalent. AudioMath provides vocal presentation of mathematical content encoded in MathML format. Of all the tools cited above, none is pervasive. None takes into account the user’s interaction context into its configuration. Our approach, therefore, is to get the strength of each tool, integrate each one of them into our work in order to build a middleware that (1) broadens the limits of utilization, (2) provides the user with opportunities to access mathematical expressions written in either MathML or LaTex format, and (3) selects appropriate application supplier and its configuration depending on the given instance of interaction context. In [18], the use of multimodal interaction for non-visual application was demonstrated. The multimodal system selects the modality over another after determining its suitability to a given situation. Multimodality is important to visually-impaired users because it provides them equal opportunities to use informatics like everybody else. Recently, agents or multi-agent systems (MAS) [19, 20] have been widely used in many applications, such as on a large, open, complex, missioncritical systems like air traffic control [21]. Generally, agency is preferred over traditional techniques (i.e. functional or object-oriented programming) because the latter is inadequate in developing tools that react on environment events. Some works on MAS for visually-impaired users include [18, 22]. In contrast to those works, ours focuses on ubiquitous access to mathematical expressions. Incremental machine learning (IML) is a progressive acquisition of knowledge. In the literature, various IML algorithms exist but in this work, supervised learning is adopted because limited scenarios have been considered. Supervised learning is a ML method by which the learning process produces a function that maps inputs to certain desired outputs. More details of ML design are in Section 5. Our focus has always been pervasive multimodality for the blind. This work was initially inspired by [23]. As our work evolves, however, the domain of application and its corresponding optimization model becomes completely different as this paper is reflective of our intended user. The methodology is different; this work adopts machine learning (ML) to acquire knowledge. Such knowledge is stored onto the knowledge database (KD) so that it can be

9

made omnipresent, accessible anytime and anywhere via wired or wireless networks. A major challenge in designing systems for blind users is how to render them autonomy. To this end, several tools and gadgets have emerged, among them are the GPS (global positioning system), walking stick that detects user context [24] and a talking Braille [25]. Our work aims the same. Ours is adaptive to user’s condition and environment. Through pervasive computing networks, the ML acquired knowledge, and user’s task and profile all become omnipresent, and the system’s knowledge on the feasible configuration for the user’s task is generated without any human intervention.

learning mechanism wherein the system remembers scenarios – the input conditions and the resulting output conditions of each scenario. This learning mechanism assists the system in selecting the optimal supplier based on the given scenario. Different suppliers are apt for different scenarios. Part of this learning mechanism is the ranking of application suppliers; the ranking takes into account the user’s preference. In general, it is possible that in a given scenario, two or more suppliers may be found suitable for invocation, with the top-ranked supplier being activated by default. When the chosen supplier is not available, then the next-ranked supplier is taken as its replacement.

3

CHALLENGES, PROPOSED SOLUTIONS AND CONTRIBUTION

Contribution 3: Design of a system that is tolerant to faults due to failure of servers and media devices.

In this section, we define the requirements in designing a pervasive system that will present mathematical expressions to visually impaired users by posing specific technical challenges to solve and then describe the approach to address them.

Related Questions: In case of server failure, what must be done to guarantee that the current user’s data, profile and machine knowledge are not lost? If selected media devices are malfunctioning, what must be done to keep the system remain operational and persistent? Proposed Solutions: Like any pervasive system, ours assume that there are many members of the server group by which the user can connect. During the time that the server to which the user is connected is down, the user may continue working and that his data, profile and machine knowledge are all stored in the local cache. As soon as the server is up, the server starts communicating with the user’s terminal, and the server’s copy of ubiquitous information is updated. Afterwards, the server’s ubiquitous information is sent to all members of the server group. Our system also adopts a ranking scheme for media devices’ suitability to a given modality. When a highly-ranked media device is not available or has failed, a lower-ranked media device is taken as its replacement. If no replacement is found, then the system re-evaluates the current instance of interaction context and accordingly chooses the optimal supplier and modalities. Afterwards, the system activates the available media device(s) that support the chosen modalities.

Contribution 1: Design of a scheme in which a mathematical document can be made accessible anytime and anywhere to visually-impaired users. Related Questions: Given that the computing task is to provide ubiquitous access to a mathematical document, how can this document be made accessible whenever and wherever the user wishes to given that the user can be either stationary or mobile? Also, given that any computing machine or server may fail, what configuration must be established in order to ensure the ubiquity of such document? Proposed Solutions: A mathematical expression becomes accessible if it is stored as a MathML or LaTex document. This document, along with the user’s data and profile, becomes available for ubiquitous computing if it is stored in a server. The content of this server becomes omnipresent if it is replicated to the other members of the server group. Hence, the server group renders the user’s document ubiquitous, available anytime and anywhere. The user connects to a member of the server group upon login. This server, one that is closest to the user’s location, becomes a point of access for the user’s profile, data and mathematical document. Contribution 2: Conceptualization of an adaptive system that selects an optimal application supplier, one that provides visually-impaired users access to mathematical expressions, based on the given instance of interaction context. Related Questions: How do we associate a mathematical document to an optimal application supplier? What would be the basis of such association? If this optimal supplier happens to be not available, how will the system find a relevant replacement? Proposed Solutions:

UbiCC Journal - Volume 3

Contribution 4: Design of a system that provides configuration suitable to the user’s satisfaction. Related Questions: How do we represent and quantify user’s satisfaction? What parameters are used to measure the user’s satisfaction with regards to system configuration? Proposed Solutions: We use the utility measure [0,1] to denote user satisfaction in which 0 = condition is inappropriate while 1 = user is happy with the condition. In general, the closer the configuration setting is to the user’s pre-defined preferences, the higher is the user satisfaction. In this work, we consider the application supplier and its QoS dimensions as parameters for system configuration.

We incorporate machine

10

4

INFRASTRUCTURE ARCHITECTURE

AND

SYSTEM

Here, we present the architectural framework of our pervasive multimodal multimedia computing system that provides ubiquitous access to mathematical expression for blind users. 4.1

System Architecture Figure 1 shows the layered view of our pervasive multimodal multimedia computing system. It is a multi-agent system organized into layers. Layering is a method by which communication takes place only between adjacent layers. It limits the undesirable ripple-effect propagation of errors within the boundary of the layer involved. The various system layers and their functionalities are:

Figure 1: The architectural abstraction of a generic MM computing system for visually-impaired users. (1) The Presentation Layer – Here, the mathematical expression is presented to the user via optimal presentation format. This layer is responsible for the conversion of the mathematical expression’s encoded format (from Data Analysis Layer) into its final presentation format. (2) The Data Access Layer – Here, users may edit or search for a term in a mathematical expression. (3) The Data Analysis Layer – Here, the mathematical expression presentation format is selected based on available media devices and supplier, and interaction context. Also, an agent takes in a MathML or LaTex expression and converts it to its encoded format. Furthermore, its machine learning component selects the optimal presentation format of the expression based on parameters just cited. (4) The Control and Monitoring Layer – This layer controls the entire system, coordinating the detection of user’s interaction context, and the manipulation and presentation of the mathematical expression. In this layer, there is an agent that retrieves MathML or LaTex document and the user‘s profile.

UbiCC Journal - Volume 3

(5) The Context Gathering Layer – Here, the current interaction context is detected. Also, the user’s media devices and application supplier preferences are also detected. The layer’s agents detect the available media devices and the contexts of the user’s environment and of the computing system. (6) The Physical Layer – It contains all the physical entities of the system, including media devices and sensors. The raw data from this layer are sampled and interpreted and forms the current instance of interaction context. 4.2

The Ubiquitous Mathematical Document We define task as user’s work to do and its accomplishment requires the use of a computing system. Hence, in this paper, the user’s task is to access (i.e. read, write, edit) a mathematical expression in a document in a ubiquitous fashion. 4.2.1 Creating a mathematical document The processes of creating a ubiquitous mathematical document are as follows: (i) Using Braille or speech as input media, the user writes a mathematical equation using the syntax of MathML or LaTex; (ii) There is a supplier (selected by the middleware as the most appropriate to the current interaction context) that takes in this input equation and yields its corresponding output – via speaker or Braille (note that in a Braille terminal, there is a separate section where the user can touch/sense the output); (iii) The supplier saves the document in the local cache; and (iv) Our middleware saves the document onto the server which is also propagated to other members of the server group. Figure 2 shows a specimen fraction (in bi-dimensional form) and its equivalent representation in MathML, LaTex and Braille.

x + 1 x − 1

Figure 2: A fraction in bi-dimensional form and its corresponding equivalent in LaTex, MathML and Braille. 4.2.2 Reading and presenting the mathematical expression in a document A ubiquitous mathematical document becomes readily available to the user once a connection is made between the user’s terminal and a member of the server group. In general, the processes for read-

11

ing or presenting a mathematical document to the user are as follows: (i) Our middleware retrieves the mathematical document from the server and download it to the user’s cache/local terminal; (ii) The middleware selects a supplier based on the given interaction context; (iii) The middleware reads or presents the mathematical equation to the visuallyimpaired user via speech or Braille. 4.2.3 Modifying a mathematical document At any time, the user may delete or modify a mathematical equation within a document. Once a mathematical document is identified, our middleware opens up the file and our Data Access Layer (see Section 4.1) allows users to search for a term within the equation and edit same. Once editing is done, the document is saved accordingly.

The user may continue working on the same mathematical document in, say, a park. In this new setting, the middleware detects the user’s interaction context and the available media devices. The system then provides an application supplier that is likely different from what the user used when he was at home. Although different in setting, the point is that the user is still able to continue working on an interrupted task. 5

DESIGNING AN INTERACTION CONTEXT ADAPTIVE SYSTEM

Here, we elaborate on the system’s knowledge acquisition that makes it adaptive to the given interaction context. 5.1

4.3

Anytime, Anywhere Mathematical Computing As shown in Figure 3, computing with mathematical equations for visually-impaired users is possible anytime, anywhere the user wishes to. In the diagram, the user is assumed to be working at home using our middleware.

Theoretical Machine Learning In machine learning (ML), a program is said to have learned from experience E with respect to a class of task T and a performance measure P if its performance P at task T improves with experience E [26]. In this work, the learning problem is defined as follows: (i) task T: selecting the modalities (and later the media devices) that are appropriate to the given instance of interaction context, (ii) performance P: measure of the selected modalities’ suitability to the given interaction context, as given by their “suitability score” (iii) training experience E: various combinations of possible modalities for visually-impaired users. Figure 4 shows the functionality of a generic ML-based system. In general, a scenario is an event that needs to be acted upon appropriately. An input to the ML component is the pre-condition of a scenario. Here, the pre-condition scenario is a specific instance of an interaction context. The ML component analyzes the input, performs calculations and decisions and yields an output called the postcondition of a scenario. For knowledge acquisition purposes, the pre- and post-conditions of every scenario are stored in a databank called the scenario repository (SR). Each entry in SR forms a distinct scenario.

Figure 3: An anytime, anywhere adaptive computing with mathematical document for visuallyimpaired users. The system detects the user’s interaction context (i.e. getting the values of parameters that make up the contexts of the user, his environment and his computing system – more details in Section 7), detects the currently available media devices and selects the most suitable application supplier, and eventually accessing the user’s mathematical document. The user then reads or modifies the mathematical equations in this document or writes a new one. At the end of the user’s session, his mathematical document is saved onto the server and on all other members of the server group.

UbiCC Journal - Volume 3

Figure 4: A generic ML system: an instance of interaction context serves as input to a ML component yielding a corresponding post-condition result. When a ML component is given a situation (i.e. pre-condition of a scenario), it consults SR for a similar entry. If a match is found then it simply

12

retrieves the post-condition scenario and implements it. If no match is found (i.e. scenario is new), then the ML component, using its acquired knowledge, performs calculations producing the postcondition of the scenario. If accepted by the expert (i.e. the user), then the complete scenario is stored onto SR as a new entry. This process is performed whenever a new scenario is encountered. Over time, the ML component accumulates enough knowledge that it knows the corresponding reaction (i.e. post-condition) given a certain situation (i.e. pre-condition). Incremental machine learning (IML) is a progressive acquisition of knowledge. In the literature, various IML algorithms exist, such as the candidate elimination [26], and ID5 (i.e. the iterative dichotomizer version 5, an incremental implementation of ID3 which itself is a decision-tree induction algorithm developed by Quinlan) [28]. In this work, supervised learning is adopted because limited scenarios have been considered. Supervised learning is a ML method by which the learning process produces a function that maps inputs to certain desired outputs. Let there be a set of inputs X with n components and a set of outputs Y with m components. Let f be the function to be learned which will map some elements in X to the elements in Y, and h be the hypothesis about this function. Furthermore, let X be the set of interaction context instances, i.e. set of pre-condition scenarios. Hence, Y would be a set of post-condition scenarios, and the mapping between the pre- and post-condition scenarios is denoted by f: X
Y. See Figure 5.

5.2

Basic Principles of Interaction Context In this paper, the following logic symbols are used: ⊗ = Cartesian product yielding a set composed of tuples, £1 = set of positive integers excluding zero, ∀ = universal quantifier, ∃ = existential quantifier, the basic logical connectives ∧ (AND) and ∨ (OR), and the intervals [x, y] which denotes that a valid data is in the range of x and y, and (a, b] which denotes that a valid data is higher than a and up to a maximum of b. The interaction context, IC = {IC1, IC2,…, ICmax}, is a set of all possible interaction contexts. At any given time, a user has a specific interaction context i denoted ICi, 1 ≤ i ≤ max. Formally, an interaction context is a tuple composed of a specific user context (UC), environment context (EC) and system context (SC). An instance of IC may be written as:

ICi = UC k ⊗ EC l ⊗ SC m

(1)

where 1 ≤ k ≤ maxk, 1 ≤ l ≤ maxl, and 1 ≤ m ≤ maxm, and maxk = maximum number of possible user contexts, maxl = maximum number of possible environment contexts, and maxm = maximum number of possible system context. The Cartesian product means that at any given time, IC yields a specific combination of UC, EC and SC. The user context UC is made up of parameters that describe the state of the user during the conduct of an activity. A specific user context k is given by: max k UC k = ⊗ ICParam kx x =1

(2)

where ICParamkv = parameter of UCk where k is the number of UC parameters. Similar in form with UC, any environment context ECl and system context SCm are given as follows:

Figure 5: The relation between pre-condition scenarios and the post-condition scenarios using supervised learning. As shown in the diagram, Xi = an element of X, and i ∈ 1 ... n, and Yj = a element of Y, and j ∈ 1 ... m. When a new pre-condition Xnew occurs, the learning system finds the best possible output value Ybest using hypothesis. In general, the learner compares the results of hypothesis functions h(f(Xnew) = Y1), h(f(Xnew) = Y2), … , h(f(Xnew) = Ym) and selects one that yields the best score. The new case is the newly-acquired knowledge which is later on added to the knowledge repository. This learning process is called incremental machine learning.

UbiCC Journal - Volume 3

max l EC l = ⊗ ICParam ly y =1

SC m =

max m ⊗ ICParam mz z =1

(3)

(4)

The first knowledge the ML component must learn is to relate the interaction context to an appropriate modality. In general, a modality is possible if there exists at least one modality for data input and at least one modality for data output. Given a modality set M = {Vin, Tin, Vout, Tout} wherein Vin = vocal input, Vout = vocal output, Tin = tactile input and Tout = tactile output then modality is possible under the following condition: Modality Possible = (Vin ∨ Tin ) ∧ (Vout ∨ Tout )

(5)

13

The failure of modality, therefore, can be specified by the relationship: Modality Failure = ((Vin = Failed) ∧ ( Tin = Failed)) ∨ ((Vout = Failed) ∧ (Tout = Failed))

(6)

Let Mj = element of the power set of M, that is, Mj ∈ P(M) where 1 ≤ j ≤ mod_max (maximum mo-

ˆ = the most suitable Mj for a givdality). Also, let M en interaction context ICi. As stated, X is a set of pre-condition scenarios. Hence, the relationship between X and IC may be written as Xi = ICi. For simplicity purposes, we let the pre-condition set X be represented by interaction context IC. Each interaction context i, denoted as ICi, is composed of various attributes of n components, that is, ICi = (A1, A2, ...,An ) where an attribute may be a parameter belonging to UC or EC or SC. We also let the set of post-condition Y be represented by a set of modality M. Let the function f map the set of IC to the set of M, in which h calculates the suitability score of such mapping, that is,

(

)

h f (ICi ) → M j = < suitability_score >

(7)

In Mathematics, function h can be written as: (8)

h = P(M j/ICi )

which should be read as the probability of the occurrence of Mj given ICi. To simplify calculation, Bayes Theorem [29], given below, can be adopted:

Equation 11 can also be written as: n P(M j ) ∏ P(A i | M j ) i =1 P(M j | A1...A n ) = m n ∑ P(M k ) ∏ P(A i | M k ) k =1 i =1

(12)

which is the fundamental equation for the Naive Bayes classifier. Given a new instance of interaction context ICnew = (A1 …An), the equation shows how to calculate the probability that Mj will take on any given value, given the observed attribute values of ICnew and given the distributions P(Mj) and P(Ai|Mj) estimated from the training data (SR). If we are interested only in the most suitable value of Mj, then we have the Naive Bayes classification rule: n    P(M j ) ∏ P(A i | M j )    i =1 ˆ = arg max h best = M  (13) m n j  ∑ P(M ) ∏ P(A | M )  k i k   i =1  k =1 

Given that the denominator does not depend on parameter j, then the above equation becomes: n   ˆ = arg max  P(M ) ∏ P(A | M )  h best = M j i j   i =1 j  

(14)

where P(Mj) = the frequency of Mj in SR ÷ cardinality of (SR). 5.3

P(M j/ICi ) =

P(ICi /M j ) × P(M j ) P(ICi )

(9)

The implementation of Bayes Theorem leads to the Naive Bayes algorithm [26]. The Naive Bayes algorithm is a classification algorithm that assumes that ICi attributes A1,…,An are all conditionally independent of one another given a post condition Mj. The representation of P(ICi|Mj) becomes: n P(ICi | M j ) = ∏ P(Ai | M j ) i =1

(10)

5.4

Here, our goal is to train a classifier that, given a new ICi to classify, will provide the probability distribution over all possible values of M (i.e. M1, M2, …, Mm). Given that ICi = (A1, A2, ...,An ), then Eq. (9) becomes: P(M j | A1...An ) =

P(M j )P(A1...An | M j ) m ∑ P(Mk )P(A1...An | M k ) k =1

UbiCC Journal - Volume 3

Finding Optimal Modalities for Interaction Context Given that M = {Vin, Tin, Vout, Tout}, then the power set (i.e. the set of all subsets) of M is given by P(M) = {{Vin}, {Tin}, {Vout}, {Tout}, {Vin, Tin}, {Vin, Vout}, {Vin, Tout}, {Vin, Tin, Vout}, {Vin, Tin, Tout}, {Vin, Vout, Tout}, {Vin, Tin, Vout, Tout}, {Tin, Vout}, {Tin, Tout}, {Tin, Vout, Tout}, {Vout, Tout}, {}}. Mj, therefore, evaluates the suitˆ = hbest is ability score of each element of P(M). M then chosen from one of these elements. The selected element is one that satisfies Eq. (14) and one with the highest suitability score.

(11)

Realizing User Task Using Optimal Modalities and Supporting Media Devices Given that an optimal modality has just been selected based on the given instance of interaction context, the next step is to find the media devices that will support the chosen modality. To do so, let there be a function f1 that maps a specific modality to its appropriate media device(s) as given by f1: Modality
Media, Priority. See Figure 6.

14

Figure 6: Media selections to support a modality.

Throughout this paper, the following acronyms will be used to denote names of media devices: MIC = microphone, KB = keyboard, OKB = overlay keyboard, SPK = speaker, HST = headset, BRT = Braille terminal, TPR = tactile printer. The availability of supporting media devices is important if a modality is to be implemented. The following is a sample set of elements of f1 for visually-impaired users: f1 = {(Vin, (MIC,1)), (Vin, (Speech Recognition,1)), (Vout, (SPK,1)), (Vout, (HST,2)), (Vout, (Text-to-Speech,1)), (Tin, (KB,1)), (Tin, (OKB,2)), (Tout, (BRT,1)), (Tout, (TPR,2))}

Note that although media technically refers to hardware components, a few software elements, however, are included in the list as vocal input modality would not be possible without speech recognition software and the vocal output modality cannot be realized without the presence of text-tospeech translation software. From f1, we can obtain the relationship in implementing multimodality:

filename extension .tex) and MathML (with extension .xml) is supported by several suppliers. Let there be a function f2 that maps a given mathematical document (of type MathML and LaTex) and available media device(s) to the user’s preferred supplier and its priority ranking as given by f2: Document, {media devices}
Preferred supplier, Priority. For demonstration purposes, let us assume that the user chooses his 3 preferred suppliers and ranks them by priority. The learned function is saved onto knowledge repository and is called user supplier preference. Given that Media Devices = {MIC, KB, OKB, SPK, HST, BRT, TPR} and Supplier = {MAVIS, LaBraDoor, ASTER, AudioMath, BraMaNet, Lambda} and Document = {.tex, .xml} then the following are some possible mappings within f2: f2 = {((.tex, BRT) (MAVIS, 1)), ((.tex, BRT) (LaBraDoor, 2)), ((.tex, {BRT, SPK |HST}), (ASTER, 1)), ((.tex, {BRT, SPK|HST}), (MAVIS, 2)), ((.tex, {BRT, SPK|HST}), (LaBraDoor, 3)), ((.tex, {SPK|HST}), (ASTER, 1)), ((.xml, {BRT}), (Lambda, 1)), (.xml, {BRT}), (BraMaNet, 2)), ((.xml, {BRT, SPK|HST}), (AudioMath,1)), ((.xml, {BRT, SPK|HST}),(Lambda, 2)), ((.xml, {BRT, SPK|HST}), (BraMaNet, 3)), etc.}

f1(Vin) = (MIC,1) ∧ (Speech Recognition,1) f1(Vout) = ((SPK,1) ∨ (HST,2)) ∧ (Text-to-Speech,1) f1(Tin) = (KB,1) ∨ (OKB,2) f1(Tout) = (BRT,1) ∨ (TPR,2)

Therefore, the assertion of modality, as expressed in Eq. (5), with respect to the presence of media devices becomes: Modality Possible = ((MIC ∧ Speech Recognition) ∨ (KB ∨ OKB)) ∧ (((SPK ∨ HST) ∧ Text - to - Speech) ∨ (BRT ∨ TPR))

5.5

(15)

Machine Learning Training for Selection of Application Supplier In supervised learning, there exists a set of data, called training set, from which the learning knowledge is based. The function to be learned maps the training set to a preferred output. The user provides the result of the mapping. A successful mapping, called positive example, is saved while an incorrect mapping, called negative example, is rejected. The positive examples are collected and form part of the system’s knowledge. The acquired knowledge is then saved onto the knowledge database (KD). Figure 7 shows the ML knowledge acquisition. A mathematical document of type LaTex (with

UbiCC Journal - Volume 3

Figure 7: The training process for ML knowledge acquisition: (Up) the mapping of data type to a supplier and (Down) building a user’s preferred QoS dimensions for a supplier.

Every supplier has its set of quality of service (QoS) dimensions that consumes computing resources. Here, the only important QoS dimensions are those that are valuable to visually-impaired users. A function f3 creates a mapping of a supplier and its QoS dimensions that the user prefer (f3: Supplier
QoS dimension j, Priority) Also, 1 ≤ j ≤ qos_max (maximum number of QoS dimensions). Priority is of type £1. Since there are many possible values for each QoS dimension, the user arranges these values by their priority ranking. A sample f3 is given below: f3 = {(Lambda, (40 characters per line, 1)), (Lambda, (60 characters per line, 2)), (Lambda, (80 characters per line, 3)), (Lambda, (French Math code, 1)), (Lambda, (Nemeth

15

code, 2)), (AudioMath, (medium volume, 1)), (AudioMath, (high volume, 2)), (AudioMath, (low volume, 3)), etc.} 6

CONFIGURATION AND OPTIMIZATION OF APPLICATION SUPPLIER

Here, we discuss the method by which the system would self-configure taking into account the user’s satisfaction. Alternative Configuration Spaces Given a user task, application suppliers are instantiated to realize the task. For each supplier, however, there are various QoS dimensions that can be invoked in its instantiation. Respecting the user’s preferences is the way to instantiate a supplier, but if this is not possible, the dynamic reconfiguration mechanism should look upon the various configuration spaces and determine the one that is suitable and optimal for the user’s needs. A QoS dimension is an application’s parameter that consumes computing resources (battery, CPU, memory, bandwidth). As an application’s QoS dimension improves, then the application’s quality of presentation (e.g. clarity of sound, etc.) also improves but at the expense of larger resources’ consumption. Given a task and its various applications, the task’s QoS dimension space is given by:

where s ∈ Supplier space is an application supplier and the term cs ∈ [0, 1] reflects how the user cares about supplier s. Given a task of n suppliers arranged in order of user’s preference, then csupplier1 = 1, csupplier2 = 1 – 1/n, csupplier3 = 1 – 1/n – 1/n, and so on. The last supplier therefore has cs value close to zero which means that the user cares not to have it if given a choice. In general, in a task, the cs assigned to supplier i, 1≤ i ≤ n, is given by:

6.1

QoS Dimension space = ⊗

qos_max Di i =1

(16)

In this work, the QoS dimensions that matter are those that are valuable to blind users. For suppliers that convert LaTex or MathML to Braille, the QoS dimensions of importance are the number of characters per line, and the number of Math codes that it can support. For suppliers that convert .tex and .xml document into its audio equivalent, the QoS dimensions are the volume, age of the speaker, gender of the speaker, words uttered by the speaker per unit of time, and the speaker’s language. 6.2

Optimizing Configuration of User’s Task An optimal configuration is a set-up that tries to satisfy the user’s preferences given the current interaction context and available media devices. When the configuration is optimal, it is said that the user’s satisfaction is achieved. Let the user’s satisfaction to an outcome be within the Satisfaction space. It is in the interval of [0, 1] in which 0 means the outcome is totally unacceptable while a 1 corresponds to a user’s satisfaction. Whenever possible, the system tries to achieve a result that is closer to 1. Given a supplier, user’s satisfaction improves if his preferences are enforced. The supplier preferences in instantiating an application are given by:

Supplier preferences = h s x s • f s cs

UbiCC Journal - Volume 3

i -1 csupplier i = 1 - ∑ (1/n) 1

(18)

The term fs: dom(s) → [0, 1] is a function that denotes the expected features present in supplier s. The supplier features are those that are important to the user, other than the QoS dimensions. For example, for a supplier that produces an audio output, the user might prefer one that provides wave intonation, or capable of informing the user of the nature of the next mathematical expression, etc. For example, if the user listed n = 3 preferred features for an application, and the selected supplier supports them all, then fs = 1. If, however, one of these features is missing (either because the feature is not installed or the supplier does not have such feature), then the number of missing feature m = 1 and fs = 1 – m/(n + 1) = 1 – ¼ = 0.75. In general, the user satisfaction with respect to supplier features is given by: f supplier = 1 -

m n +1

(19)

The term hs Xs expresses the user’s satisfaction with respect to the change of the supplier, and is specified as follows: hs ∈ (0, 1] is the user’s tolerance for a change in the supplier. If this value is close to 1, then the user is fine with the change while a value close to 0 means the user is not happy with the change. The optimized value of hs is:  cs + c rep   h s = arg max   2× c  s  

(20)

where crep is value obtained from Eq. (18) for the replacement supplier. The term xs indicates if change penalty should be considered. xs = 1 if the supplier exchange is done due to the dynamic change of the environment, while xs = 0 if the exchange is instigated by the user. The algorithm for finding the optimized supplier configuration of a task is given in Figure 8. In the algorithm, the default configuration is compared with other possible configurations until the one that yields the maximum value of user’s satisfaction is found and is returned as result of the algorithm.

(17)

16

on the following parameters: (1) the workplace’s noise level – identifies if it is quiet/acceptable or noisy, and (2) the environment restriction – identifies whether a workplace imposes mandatory silence or not. Based on the specified parameters, the environment context, therefore, is formally given by the relationship: EC = (Noise Level) ∧ ( Environment Restriction) (22)

Table 1 shows the affected modality based on environment’s context. It also shows the convention table we have adopted for EC. Figure 8: Algorithm for optimized supplier and its QoS configuration. 7

Table 1: The tabulation for affected modalities by combined noise level and environment restriction

INTERACTION CONTEXT, MODALITY AND MEDIA DEVICES

Interaction context is formed by combining the contexts of the user, his environment, and his computing system. The user context, in this work, is a function of user profile (including any handicap) and preferences. A sample user profile, in generic format, is shown in Figure 9. The user’s special needs determine other affected modalities (i.e. the user is already disqualified from using visual input/output modalities). For example, being mute prevents the user from using vocal input modality.

Figure 9: A sample user profile.

As a function of modality, the user context UC can be represented by a single parameter, that of the user’s special needs. This parameter is a 4-tuple representing additional handicaps, namely the manual disability, muteness, deafness, and unfamiliarity with Braille. Each handicap affects user’s suitability to adopt certain modalities. The failure of modality, adopted from Eq. (6), with respect to UC parameters is: Modality Failure = ((Manually- Disabled) ∧ (Mute)) ∨ ((Manually- Disabled ∨ Unfamiliar with Braille)

(21)

∧ (Deaf))

The environment context EC is the assessment of a user’s workplace condition. To a blind user, a parameter such as light’s brightness has no significance, while others, such as noise level, are significant. In this work, the environment context is based

UbiCC Journal - Volume 3

The unit of noise is decibel (dB). In our work, 50 dB or less is considered “acceptable” or “quiet” while 51 dB or more is considered “noisy”. In our system design, this range can be modified, through user interface, by the end user based on his perception. In general, when the user’s workplace is noisy, the effectiveness of vocal input modality is doubtful; hence an alternative modality is necessary. In an environment where silence is required, sound-producing media (e.g. speaker) needs to be muted or deactivated. For environment noise restriction, we have defined a database of pre-defined places (e.g. library, park) and their associated noise restrictions (e.g. library: silence required, park: silence optional). User can modify some database records. Also, new ones can be added through the user interface. In our work, the system context (SC) signifies the user’s computing device and the available media devices. See Figure 10. The computing device (e.g. PC, laptop, PDA, cellular phone) also affects the modality selection. For example, using a PDA or cell phone prevents the user from using tactile input or output modality. Let SC, for the purpose of modality selection, be represented by a single parameter, the user’s computing device. Let Computing Device = {PC, MAC, Laptop, PDA, Cellular phone}. The computing device convention is shown in Table 2. For example, SC = 1 means that the user’s computer is either a PC, a laptop or a MAC. Note that when SC = 2

17

(i.e. PDA), Tin = Failed because the computing device has no tactile input device; its Tout = Failed because, in a regular set-up, it is not possible to attach a tactile device (e.g. Braille terminal) onto it.

Figure 10: The system context as function of user’s computing device and available media devices. Table 2: The convention table of user’s computing device and its effect on modality selection

Using ML, the following are the derived rules on modality failures given the parameters of interaction context: Vin Failure = (User = Mute) ∨ (Noise Level = Noisy) (23) ∨ (Environme nt Restrictio n = Silence required)

Vout Failure = (User = Deaf)

(24)

Tin Failure = (User = Manually- Disabled) ∨ (Computing Device = PDA)

(25)

Tout Failure = (User = Manually - Disabled) ∨ (User = Unfamiliar with Braille) ∨ (Computing Device = PDA) ∨

(26)

(Computing Device = Cellphone)

8

DESIGN SPECIFICATION SCENARIO SIMULATIONS

AND

Having formulated various ML knowledge to optimize the configuration setting of user’s task, this knowledge is then put to test via sample scenarios. The design specification comes along as these scenarios are further explained. 8.1 Selection of Modalities Consider, for example, an interaction context that is composed of the following parameters: IC = (A1, A2, A3, A4, A5, A6, A7) wherein: • A1 = {true | false} = if user is manually disabled,

UbiCC Journal - Volume 3

• A2 = {true | false} = if user is mute, • A3 = {true | false} = if user is deaf, • A4 = {true | false} = user familiarity with Braille, • A5 = {quiet | noisy} = environment’s noise level, • A6 ={silence required | silence optional} = environment’s noise level restriction, and • A7 = {PC or Laptop or MAC | PDA | Cellphone} = user’s computing device. The set of possible modalities (i.e. refer to Eq. (5)) is given by M = {M1,M2,M3,M4,M5,M6, M7, M8, M9} wherein M1 = {Tin, Tout}; M2 = {Tin, Vout}; M3 = {Vin, Vout}; M4 = {Vin, Tout}; M5 = {Vin, Tout, Vout}; M6 = {Tin, Tout, Vout}; M7 = {Tin, Vin, Vout}; M8 = {Tin, Vin, Tout}; M9 = {Tin, Vin, Tout, Vout} (see its derivation from Section 5.3). In this example, let us assume the following interaction context: (i) user context: blind with no further handicaps, familiar with Braille; hence A1 = False, A2 = False, A3 = False, A4 = True, (ii) environment context: the user is in a classroom, then A5 = noisy, A6 = silence required, (iii) system context: the user works on a laptop; A7 = Laptop. The system now finds the modality that suits the given interaction context. The system does so using the principles discussed in Section 5. Let us assume that the computing system’s SR contains recorded scenarios as shown in Figure 11. The given figure is generated by using WEKA (Waikato Environment for Knowledge Analysis) [30] which is a collection of machine learning algorithms for data mining tasks. It is used in testing a machine learning algorithm as it contains tools for data pre-processing, classification, regression, clustering, association rules, and visualization. In this work, a sample SR is shown using arff viewer (i.e. a WEKA tool). As shown in the diagram, there are already 19 scenarios representing the system’s acquired knowledge. The 20th scenario represents a new case. Using Equation 14, and with reference to the given interaction context and SR, the suitability score of Mj (where j = 1 to 9) can be calculated. Let us consider, for instance, the calculations involved with modality M1: Suitability_Score (M1) = P(A1 = False | M1) × P(A2 = False | M1) × … × P(A7 = Laptop | M1) × P(M1) = 1 × 0.67 × 0 × …. × 3/19 = 0 wherein P(A1 = False | M1) = 3/3, P(A2 = False | M1) = ⅔, P(A3 = False | M1) = 0/3, P(A4 = True | M1) = 3/3, P(A5 = Noisy | M1) = ⅓, P(A6 = silence optional | M1) = ⅓, and P(A7 = Laptop | M1) = ⅓. Also, P(M1) = 3/19. Similarly, we do calculate the suitability score of all other remaining modalities. Using the same procedure, the calculations involved with the modality that yields the highest suitability score, M6, is shown below: Suitability_Score (M6) = P(A1 = False | M6) × P(A2 = False | M6) × … × P(A7 = Laptop | M6) × P(M6) = 1× ⅔ × 1 × 1 × ⅔×⅔× ⅓× 3/19 = 0.015671

18

Figure 11: A sample of a scenario repository (SR).

As explained in Section 5.3, M6 = {Tin, Tout, Vout} respects the conditions imposed in Eq. (5), hence, it is chosen as the optimal modality for the given IC. This new scenario is added to SR as a newlyacquired knowledge (i.e. scenario #20 in SR). 8.2

Selection of Media Devices As stated in Section 5.4, function f1 associates selected modalities to available media devices. For simulation purposes, let us assume that currently available media devices are the MIC, Speech Recognition, SPK, HST, Text-to-Speech, KB, and BRT. Given this scenario, Vin is not part of optimal modalities, then media devices MIC, and Speech Recognition which support Vin are automatically excluded from the set of supporting media devices: f1 = {(Vin, (Mic,1)), (Vin, (Speech Recognition,1)), (Vout, (SPK,1)), (Vout, (HST,2)), (Vout, (Text-to-Speech,1)), (Tin, (KB,1)), (Tin, (BRT,2)), (Tout, ((BRT,1)} Since the selection of media device is based on the user preferences, therefore the system automatically activates the media devices having 1 as priority for each modality.

8.3

Selection of Application Supplier Consider for example a user on the go (i.e. in a park) working on a LaTex document (work1.tex) and another document MathML (work2.xml) as part of his homework. To do so, our user needs instantiation of these files using appropriate suppliers. Finding relevant suppliers can be done using function f2 which yields the following values: f2 = {((.tex, {KB, BRT}) (MAVIS, 1)), ((.tex, {KB,BRT}) (LaBraDoor, 2)), ((.tex, {KB,BRT}) (VICKIE, 3)), ((.tex, {KB, SPK |HST}), (ASTER, 1)),((.xml, {KB,BRT}), (Lambda, 1)), (.xml, {KB,BRT}), (BraMaNet, 2)),((.xml, {KB, SPK|HST}), (AudioMath,1)), ((.xml, {KB, SPK|HST}), (VoiceXML, 2))}

UbiCC Journal - Volume 3

Formally, ∀x: data format d: media devices, ∃y: Supplier and p: Priority of type £1| (x, d)
(y, p) ∈ f2. Given that supplier priority is involved in f2 then the most-preferred supplier is sought. With reference to Eq. (19), the numerical values associated with user’s preferred suppliers are as follows: (i) priority = 1 (high), user satisfaction = 1, (ii) priority = 2 (medium), user satisfaction = 2/3, and (iii) priority = 3 (Low), user satisfaction = 1/3. Now, consider further that the user’s preferred supplier, MAVIS, is absent as it is not available in the user’s laptop. The method by which the system finds the optimal supplier configuration is shown below: Case 1: (Lambda, MAVIS)
not possible Case 2: (Lambda, LaBraDoor)
alternative 1 Case 3: (Lambda, VICKIE)
alternative 2 Then the replacement selection is based on user satisfaction score: User Satisfaction (Case 2) =(1+1+⅔)/3 = 8/9 = 0.89 User Satisfaction (Case 3) =(1+1+⅓)/3 = 7/9 = 0.78 Hence, Case 2 is the preferred alternative. Formally, if f2: Document Format, {Media devices}
(Supplier, Priority) where Priority: £1, then the chosen supplier is given by: ∃(doc, m): (Document, Media devices) ∀y: Supplier, ∃p1: Priority, ∀p2: Priority | (doc, m) ● y
(y, p1) ∈ f2 ∧ (p1 < p2). 8.4

Optimizing User’s Task Configuration Consider a scenario where all suppliers that convert LaTex document to its Braille equivalent are available. For example, given the suppliers MAVIS, LaBraDoor, VICKIE, then the corresponding user satisfaction with respect to these suppliers are as follows: cMAVIS = 1.0, cLaBraDoor = 2/3, cVICKIE = 1/3. This indicates that the user is most happy with the top-ranked supplier (MAVIS) and least happy with the bottom-ranked supplier (VICKIE). Consider further that these suppliers have n = 3 preferred features (i.e. Math Braille code, capability of informing the user of the nature of the next mathematical expression, navigation within the expression). If in MAVIS set-up, the Nemeth Math code is not installed, then the missing feature m = 1 and the user satisfaction becomes fs = 1 – m/(n + 1) = 1 – ¼ = 0.75. This also reduces the user’s satisfaction, as given by the relationship cMAVIS * fMAVIS = (1.0)(0.75) = 0.75. Now, consider a case of a dynamic reconfiguration wherein the default supplier is to be replaced by another. Not taking fs into account yet (assumption: fs = 1), if the current supplier is BraMaNet, then the user’s satisfaction is cBraMaNet = 2/3 = 0.67. What would happen if it will be replaced by another supplier through dynamic reconfiguration (xsupplier = 1.0)? Using the relationship hsupplier = (csupplier + creplacement) / 2* csupplier then the results of possible alternative configurations are as follows:

19

Replacing BraMaNet (supplier 2): Case 1: Replacement by MAVIS (supplier 1): (0.67)(1) * [(0.67 + 1)/2*(0.67)]1 = 0.835 Case 2: Replacement by itself (supplier 2): (0.67)(1) * [(0.67 + 0.67)/2*(0.67)]1 = 0.67 Case 3: Replacement by VICKIE (supplier 3): (0.67)(1) * [(0.67 + 0.33)/2*(0.67)]1 = 0.50

Hence, if the reconfiguration aims at satisfying the user, then the second-ranked supplier should be replaced by the top-ranked supplier. 8.5

Simulation Results Using user’s preferences, we have simulated the variations in user’s satisfaction as these preferences are modified through dynamic configuration. The results are presented through various graphs in Figure 13. The first three graphs deal with application supplier, and the variation of user’s satisfaction as additional parameters (supplier features and alternative replacements) are taken into account. The last two graphs deal with QoS dimensions and their variations. In general, user is satisfied if the supplier and its desired features and QoS dimensions are provided. Whenever possible, in a dynamic configuration, the preferred setting is one where the parameters are those of user’s top preferences.

1

1

0,8

0,8

User Satisfaction

User Satisfaction

Figure 12: A snapshot of the simulated selection of optimal modality based on interaction context.

0,6 0,4 0,2

0,6 0,4 0,2 0

0 1

2

1

3

No missing feature One missing f eature Tw o missing f eatures

Suppliers (by priority)

1

1

0,8

0,8

User Satisfaction

User Satisfaction

Specification for Detecting Suitability of Modality Petri Net 1 is a formal, graphical, executable technique for the specification and analysis of a concurrent, discrete-event dynamic system. Petri nets are used in deterministic and in probabilistic variants; they are a good means to model concurrent or collaborating systems. In the specifications in this paper, only a snapshot of one of the many outcomes is presented due to space constraints. We use HPSim2 in simulating Petri Net. In Figure 12, a Petri Net specification is shown with modalities and interaction context. As shown, the combination of interaction context’s parameters yields the implementation of some modalities (M1 up to M9). The Net illustrates the snapshot simulation of the case cited in Section 7. As shown, the simulation begins with a token in “Modality” place and “Interaction Context” place. The firing of the token in Interaction Context yields a specific value for “User Context”, “Environment Context” and “System Context based on Computing Device” places, which is exactly similar to the values of A1,…,A7 in the previous section. The traversal of the tokens in different places is noted by green colored places. As shown, the result yields modality M6 being selected as the optimal modality. The Petri Net simulation confirms the result obtained in the previous section. Also, the same case yields a Vin failure result (i.e. due to noisy environment).

0,6 0,4 0,2

2

3

Supplie rs (by priority)

0,6 0,4 0,2

0 1

2

Supplier1 Supplier2 Supplier3

3

4 5 6 Supplie rs (by priority)

7

8

9

0 1

2

3

QoS (by priority)

8.6

1 http://www.winpesim.de/petrinet 2 "HPSim. http://www.winpesim.de

UbiCC Journal - Volume 3

Figure 13: Various graphs showing variations of user’s satisfaction with respect to its preferred supplier and QoS dimension and their replacements. 9

CONCLUSION

Our investigation on the state of the art systems and solutions for providing visually-impaired users with access to mathematical expressions indicates that none of these systems are pervasive and not a single one adapts its configuration based on the given interaction context. To address these weaknesses, we have designed a multimodal multimedia computing system that would provide mathematical computing to blind users whenever and wherever the users wish. This paper presented

20

the infrastructure design of a middleware that realizes a successful migration and execution of user’s task in a pervasive multimodal multimedia computing system, the task being the ubiquitous access to mathematical expressions for visuallyimpaired users. Through ML training, we illustrated the acquisition of positive examples to form user’s preferred suppliers and QoS dimensions for selected applications. In a rich computing environment, alternative configuration spaces are possible which give the user some choices for configuring the set-up of his application. We have illustrated that configuration could be dynamic or user-invoked, and the consequences, with respect to user’s satisfaction, of these possible configurations. Optimization is achieved if the system is able to configure set-up based on user’s preferences. In this work, we have listed modalities suitable to blind users. Given sets of suppliers, modalities, computing devices, and the possible variations of interaction context, we stated conditions in which modality will succeed or fail. Similarly, we showed a scenario wherein even if a specific modality is already deemed possible, still it is conceivable that it would fail if there are not sufficient media devices that would support it or the environment restriction imposes the non-use of the needed media devices. We validated all these affirmations through scenario simulations and formal specifications. 10 REFERENCES 1. Satyanarayanan, M., Pervasive Computing: Vision and Challenges. IEEE Personal Communications, 2001(August): p. 10-17. 2. MathML. http://www.w3.org/Math [cited. 3. Lamport, L., LaTeX: The Macro Package, http://web.mit.edu/texsrc/source/info/latex2e.pdf. 1994. 4. Stöger, B., et al., Mathematical Working Environment for the Blind Motivation and Basic Ideas, in ICCHP. 2004, Springer. p. 656-663. 5. Edwards, A.D.N. et al., A Multimodal Interface for Blind Mathematics Students. in INSERM. 1994. Paris, France. 6. Cahill, H., et al., Ensuring Usability in MATHS, in The European Context for Assistive Technology. 1995, IOS Press: Amsterdam. p. 66-69. 7. Ferreira, H., et al., Enhancing the Accessibility of Mathematics for Blind People: The AudioMath Project. in ICCHP-9th Intl Conf. on Computer Helping People with Special Needs. 2004. Paris, France. 8. Ferreira, H., et al., AudioMath: Towards Automatic Readings of Mathematical Expressions. in HumanComputer Interaction Intl (HCII). 2005. L. V., USA. 9. Moço, V. et al., VICKIE: A Transcription Tool for Mathematical Braille. in AAATE-Asso. for the Adv. of Assistive Tech. in Europe. 2003. Dublin, Ireland. 10. Schwebel, F., et al., BraMaNet: Quelques règles simples à connaître pour qu'un aveugle puisse lire vos documents mathématiques et vos pages web. in Journées nationales Caen. 2005. Caen, France.

UbiCC Journal - Volume 3

11. Batusic, M., et al., A Contribution To Making Mathematics Accessible For The Blind. in International Conf. on Computers Helping People with Special Needs. 1998. Oldenbourg, Wien, München. 12. Karshmer, A.I., et al., Reading and writing mathematics: the MAVIS project, in Proceedings of the third international ACM conference on Assistive technologies. 1998, ACM Press. p. 136-143. 13. Nemeth, A., The Nemeth Braille Code for Mathematics and Science Notation. American Printing House for the Blind, 1972. 14. Epheser, H., et al., Internationale Mathematikschrift fur Blinde, Deutsche Blindenstudienanstalt. Marburg (Lahn) 1992. 15. Commission Evolution du Braille Francais. Notation Mathematique Braille, mise à jour de la notation mathematique de 1971. 2001. 16. Edwards, A.D.N., et al., Lambda: a Multimodal Approach to Making Mathematics Accessible to Blind Students. in Proceedings of the 8th international ACM SIGACCESS conference on Computers and accessibility. 2006. Portland, Oregon, USA. 17. Raman, T.V., Audio System For Technical Readings 1994, Cornell University. 18. Awde, A., et al., Information Access in a Multimodal Multimedia Computing System for Mobile Visually-Impaired Users, in ISIE 2006, IEEE Intl. Symp. on Industrial Elec. 2006: Montreal, Canada. 19. Weiss, G., Multiagent systems. MIT-Press, 1999. 20. Ferber, J., Les systemes multi-agents, ed. V.u.i. collective. 1995, Paris: InterEditions. 21. Jennings, N.R., et al., Applications of Intelligent Agents, in Agent Technology: Foundations, Applications, and Markets, 1998, Springer-Verlag: Heidelberg, Germany. p. 3-28. 22. Awde, A., et al., A Paradigm of a Pervasive Multimodal Multimedia Computing System for the Visually-Impaired Users, in The First International Conference on Grid and Pervasive Computing. 2006: Tunghai University, Taichung, Taiwan. 23. Sousa, J.P., et al., Task-based adaptation for ubiquitous computing. IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews 2006. 6(3): p. 328-340. 24. Jacquet, C., et al. A Context-Aware Locomotion Assistance Device for the Blind. in ICCHP 2004, 9th International Conference on Computers Helping People with Special Needs. Université Pierre et Marie Curie, Paris, France. . 25. Ross, D.A., et al., Talking Braille: A Wireless Ubiquitous Computing Network for Orientation and Wayfinding in Proceedings of the 7th International ACM SIGACCESS Conf. on Computers and Accessibility 2005. Baltimore, MD, USA ACM Press. 26. Mitchell, T., Machine Learning. 1997, McGrawHill. 28. Utgoff, P., ID5: An incremental ID3, in 5th Intl. Workshop on Machine Learning. 1988. p. 107-120. 29. Kallenberg, O., Foundations of Modern Probability, ed. S.S.i. Statistics. 2002: Springer. 650. 30. Witten, I.H. and E. Frank, Data Mining: Practical Machine Learning Tools and Techniques, 2nd ed. 2005, San Francisco: Morgan Kaufmann. 525.

21

On the Implementation of Differential Encoder for Spectral Shaping in 56Kbps Embedded Modems Davinder Pal Sharma Department of Physics, University of the West Indies, St. Augustine Campus, Tinidad & Tobago, West Indies [email protected] Jasvir Singh Department of Electronics Technology, Guru Nanak Dev University, Punjab, India [email protected]

ABSTRACT Present paper deals with the simulation and implementation of two functional units, parse-to-shaping-frame and differential encoder, for spectral shaping in 56Kbps digital modem transmitter. The idea behind spectral shaping is to adapt the shape of the transmitted signal, to conform to the shape or spectral limitations of the channel, without changing the basic pulse shape or peak-to-average-ratio. This unit suppresses the signal component close to dc to minimize the effect of ac couplings or to provide sufficient data transitions for reliable clock recovery. A combined algorithm for implementation of the parse-to-shaping-frame and differential encoder functions utilized in transmitter of 56Kbps digital modem has been presented. An algorithm to perform parse-to-shaping-frame and differential encoding functions has been developed during present study. Proposed algorithm has been simulated and implemented on the Digital Signal Processor. Practical results obtained have been found almost similar to the theoretical and simulated results. Keywords: Spectral Shaping, 56Kbps Modem, Differential Encoder, Digital Signal Processor.

1

INTRODUCTION

Technologies are changing very frequently in the field of data communication over twisted copper pair (plain old telephone lines). These changes are due to quick advancement in computer and digital communication technologies along with powerful digital signal processing algorithms [1]. In the present cyber age everyone wants to enjoy Internet services like teleconferencing, web-surfing, elearning, e-banking, online movies and voice-overtelephony at very lower cost, which demands high speed. Even though it has been repeatedly predicted that network access via telephone lines would be replaced by new services based on emerging technologies [2], 56Kbps voice-band modems seem to be the best solution [3], [4] as these modems are still used by the majority of home computer users and small business owners for data communication and network access. In accordance with a study made by Georgia Tech, in 1998 approximately 70% of Internet users were connected to the network with analog voice-band modems and according to the survey conducted by a firm (Jupiter Communication) more than 50 million people in the US alone were

UbiCC Journal - Volume 3

using telephone dial up technology to access the Internet in 2001 and the user strength is growing up continuously. The Gartner Group estimates that about 55% of the user were relying on voice-band services even till 2004[5], [6]. Moreover voice-band modem has many advantages over others like they are inexpensive, easy to install, more reliable, widely available and easy in functioning. Seeing the huge consumer market of voice-band modem for Internet access, present study was carried out on data transmission over analog telephone lines. V.90/V.92 is the current 56Kbps modem standard over the PSTN telephone lines, which uses entirely different technology. Block diagram of 56Kbps modem communication system is shown in Fig. 1. Traditional analog modem like V.34 assumes both the ends of the modem session to have an analog connection to PSTN whereas V.90/V.92 standard assumes one end of the modem section to be purely digital to take the advantage of high-speed connection [7]. Internet Service Providers (ISPs) are already using digital connection at their end. There is only one analog portion on the downstream transmission path (from ISP to DTE) and the upstream data conforms to the V.34 standard. TCM is used in upstream direction whereas in downstream

22

Pulse Coded Modulation (PCM) as specified by ITU in G.711 recommendation [8] is used in this modem, also known as PCM modem. 56Kbps

AM

PSTN

I/P Data

Scrambler

Server PC

DM

To PSTN

48Kbps

DAC

Figure 1: Block diagram of 56Kbps modem communication system 2

DISCRIPTION OF 56Kbps MODEM TRANSMITTER

Mi

Figure 2: Transmitter modem (server side)

56Kbps

digital

During startup, the following encoder parameters are established: Ci equals the positive constellation points for data frame interval i . Mi is the number of code points in each constellation C i . K is the number of modulus encoder input data bits per data frame. Sr is the number of PCM code sign bits per data frame used as redundancy for spectral shaping. S is the number of differential encoder input data bits per data frame, where S + Sr = 6.

‰ ‰ ‰ ‰ ‰

The positive constellations (Ci ) to be used in each data frame interval are specified by the analog modem during training procedures. The signaling rate is determined by the selection of the parameters

Modulus Encoder

Ki

Sign Assign Unit

Ui

Data Mapper

Parse To Shaping Frame

Pj

tj (n) Differential Encoder

PCMi

$0:$5

Ui

S0: Ss-1

of

LPF

Ci

Bit Parser

d0: dD-1

Linear to µ or A Law Convertor

DIGITAL

Transmitter of V.90/V.92 56Kbps digital modem is shown in the Fig. 2. First unit is scrambler whose purpose is to facilitate effective transmission of the data over the telephone channel and to improve the convergence of the adaptive equalization and echo cancellation in the receiver. It helps the receiver to recover the timing information from the received data to facilitate synchronous operation. The downstream encoder in Draft Recommendation V.90/V.92 uses multiple modulus conversion for mapping scheme and convolutional spectral shaping as its spectral shaping scheme. The block diagram in Fig. 3 shows an overview of the downstream encoder and represents one data frame. Data frames in the digital modem have a six-symbol structure (since the robbed-bit signaling pattern repeats every six symbols).

b0: bk-1

Encoder

Bit Parser

Spectral Shaper

MUX

Serial PCM Octets

User PC

Each symbol position within the data frame is called a data frame interval and is indicated by a time index, i = 0, ..., 5.

Sr

Figure 3: Encoder of 56Kbps digital modem

UbiCC Journal - Volume 3

23

K and S during the startup phase using formula given by Ds = [(K + S) × 8000]/(6)

(1)

Description of each of the components or functional blocks as presented in Fig. 3 is given below [7]: Bit Parser partitions the block of binary data for one mapping frame into different groups of bits for processing by subsequent stages of the transmitter. It takes bits from scrambled data stream and parses them into two groups, which are fed to two different parts of encoder i.e. to differential encoder and modulus encoder. It takes D (equal to S + K) scrambled input data bits (d0 : dD-1) and parses them into K modulus encoder input bits (b0 : bK-1) and S differential encoder input bits ( s0 : sS-1 ). The modulus encoder takes K bits from the bit parser and maps them into six integers Ki, where i = 1, 2 ,…, 6. Each Ki is an integer between 0 and Mi, where the Mi’s are called the mapping moduli and represent the number of elements in each of the PCM code sets defined for data frame interval 0 to data frame interval 5. In order to be able to represent the information in the K bits taken from the parser with these six integers, the values of Mi and K must satisfy the following inequality 5 K ≤ ∏ (M ) i =0 i

(2)

Each frame interval has an independent mapper associated with it. Each one of them also has a tabulation of Mi PCM codes corresponding to the positive elements of the constellation to be used by it and denoted by Ci. The specific PCM codes that assemble each of the constellations are selected by the analog modem during the startup phase of the communication. It is required that the members of Ci should be labeled in descending order so the label 0 corresponds to the largest PCM code in the constellation and the label Mi correspond to the smallest. The output of each mapper (Ui) is generated by selecting the constellation point in Ci corresponding to Ki. The S differential encoder input bits (s0 : sS-1 ) are parsed into j = Sr spectral shaping frames of length 6/Sr . The six Pj ( n) bits are then differentially encoded to produce six input sign bits, tj ( n) , to the spectral shaper. The spectral shaping is intended to change the shape of the spectrum of the transmitted signal to make it better suited to the channel used. Spectral shaping affects only the signs of the transmitted PCM symbols. The spectral shaper modifies input sign bits tj (n) to corresponding PCM code-sign bits

UbiCC Journal - Volume 3

($i) so as to minimize the spectral shaping metric without violating the constraint specified in V.90/V.92 recommendation [7, 9]. The six sign bits generated by the spectral shaper ($i) are attached to the six unsigned mapper outputs (Ui) to form the six output symbols (PCMi), which are then multiplexed to form the stream of PCM octets to be transmitted. This completes the encoding process. 8-bit PCM codes generated by the transmitter arrive at the central telephone office through the internal digital telephone network and are applied to the digital to analog converter in the Codec at the rate of 8000 samples per second. The Codec converts each code to one of 256 voltage levels and passes the resulting staircase waveforms through a low pass filter with a 4kHz cut-off frequency [10]. The linear to µ/A-Law Converter, who expands the 8 encoded PCM bits to 14 bits in accordance with the ITU recommendation G.711 [8]. The procedure of expanding 8-bit input to 14-bit data at transmitter and the compressing the 14-bit data to 8-bit at other end is called Companding. The device, which accomplishes this task, is called CODEC and is generally situated at the central office. A-law is used by European countries whereas in U.S.A. µ-law is popular. Low pass filter in the modem design is generally used to avoid the aliasing problem caused by ADC in the communication path. To avoid the aliasing problem it should be ensured that the ADC never sees any signals that are to high in frequency. This is also known as anti-aliasing filter. As discussed above this filter has cut-off frequency equal to the bandwidth of the channel used i.e. 4 KHz. The output of filter is connected to the twisted pair (telephone line) through the hybrid circuit installed at the local telephone office of a client. 3

SPECTRAL SHAPING DIGITAL MODEM

IN

56KBPS

Spectral shaping affects only the signs of the transmitted PCM symbols. From the six sign bits of each frame, Sr are the redundancy bits and S are the information bits. The number of redundancy bits Sr is determined by the analog modem during the startup procedures; it can take the values 0, 1, 2, or 3. By setting the value of Sr = 0, the spectral shaping capabilities can be disabled [7]. Spectral shaping is used to adapt the shape of the transmitted signal to conform to the shape or spectral limitations of the channel without changing the basic pulse shape or peak to average ratio. Spectral shaping codes achieve this objective by adding some redundant information or modifying the symbol sequence [11]-[13].There are many varieties of spectral shaping codes like those presented in [14]-

24

[18] depending on the particular requirements of each application. Typical applications of spectral shaping codes include the suppression of the signal component close to dc to minimize the effect of ac couplings, or to provide sufficient data transitions for reliable clock recovery. Simulation and implementation of functional units such as parse-toshaping-frame and differential encoder of spectral shaping block of 56Kbps digital modem transmitter is discussed in the subsequent sections.

s0 - s5 bits from parser

s0 s1 s2 s3 s4 s5

PSF

Pj(i) for i = 0-5

Sr = 0 and S = 6

Sr

3.1 Parse to Shaping Frame This unit takes S input bits (s0-sS-1) from the bit parser and parsed them into j = Sr spectral shaping frames of length 6/Sr. This unit produces six outputs Pj(n) where j(n) represents the nth bit of the jth spectral shaping frame in a data frame. The spectral shaping function depends on selected values of Sr, which may ranges from 0 to 3. Sr bits which are determined during startup procedure selects the value of S bits as Sr + S = 6. When Sr = 0 & S=6, spectral shaping is disabled and when Sr = 1 & S=5 sign bits s0 to s4 shall parse to one six-bit shaping frame per data frame according to Table 1. As per ITU Recommendations V.90/V.92, for Sr=2 & S=4, the sign bits s0 to s3 shall be parsed into two three-bit shaping frames per data frame and when Sr=3 & S=3, sign bits s0 to s2 shall be parsed to three two-bit shaping frames per data frame [7]. Block diagram of parse-to-shaping-frame (PSF) units for different value of Sr is given in Fig. 4. Pj(i) is current shaping frame, Pj+1(i) stands for next 1st frame and Pj+2(i) stands for next 2nd frame.

s0 – s5 bits from parser

PSF

Sr

s0 – s5 bits from parser

PSF

Sr = 3, S = 3

0

Pj (0) = 0

Pj (0) = 0

Pj (0) = 0

1

Pj (1) = s0

Pj (1) = s0

Pj (1) = s0

2

Pj (2) = s1

Pj (2) = s1

Pj+1 (0) = 0

Pj(i) for i = 0-2 Pj+1(i)

Sr

s0 – s5 bits

Sr = 2, S = 4

0 s0 s1 0 s2 s3

Sr = 2 and S = 4

from parser Sr = 1, S = 5

Pj(i) for i = 0-5

Sr = 1 and S = 5

Table 1: Parsing process of input sign bits

Data frame interval

0 s0 s1 s2 s3 s4

PSF

0 s0 0 s1 0 s2

Pj(i) Pj+1(i)

for i = 0-1

Pj+2(i)

Sr = 3 and S = 3

Figure 4: Block diagram of parse to shaping frame (PSF) units for different values of Sr 3.2 Differential Encoder

3

Pj (3) = s2

Pj+1 (0) = 0

Pj+1 (1) = s1

4

Pj (4) = s3

Pj+1 (1) = s2

Pj+2 (0) = 0

5

Pj (5) = s4

Pj+1 (2) = s3

Pj+2 (1) = s2

UbiCC Journal - Volume 3

The power spectral density (PSD) of a digital communication signal can be controlled and shaped by selecting the transmitted signal pulse and by introducing correlation through coding, which is

25

used to combat channel distortion and noise in transmission. Coding for spectrum shaping is introduced followed by the channel encoding so that the spectrum of the transmitted signal matches the spectral characteristics of a base band or equivalent low-pass channel. Codes that are used for spectrum shaping are generally called either modulation codes or line codes, or data translation codes. Such codes generally place restrictions on the sequence of bits into the modulator and thus introduce correlation and hence memory into the transmitted signal. Modulation codes are usually employed in digital communication over cable systems to achieve spectral shaping and to eliminate or minimize the dc content in the transmitted (or stored) base band signal [19]. Differential encoding technique has been recommended by the ITU for providing spectral shaping in V.90/V.92 56Kbps digital modem, which is basically Non-Return-to-Zero-Invert-on-ones (NRZI) line coding technique. In this scheme transitions from one amplitude level to another occurs only when a ‘1’ is transmitted. The encoding operation is described mathematically by the relation bk = ak ⊕ bk-1

(3)

where {ak} is the binary information sequence into the encoder, {bk} is the output sequence of the encoder and ⊕ denotes modulo-2-addition operation. The differential encoding operation introduces memory in the signal. The most direct implementation of the differential encoder is to use an exclusive – OR (XOR) function with a delay in the feedback path as given in the Fig. 5 [19]-[20]. ak

bk = ak ⊕ bk-1 XOR

$0 = s0 ⊕ ($5 of the previous data frame); and $i = si ⊕ $i–1 for i = 1, ..., 5

(4)

When Sr=1 and S=5 the odd bits may be differential encoded to produce the output Pj' and a second order differential encoding may be performed to produce the initial shaping sign bit assignment, tj(0) to tj(5) using the rule tj(k) = Pj'(k) ⊕ tj-1(k)

(5)

Finally spectral shaper converts each bit tj(k) to PCM code sign bit $k . For Sr=2 and S=4, after processing through parse to-shaping-frame, the odd bit in each shaping frame may be differentially encoded to produce outputs Pj' and P'j+1 and a second order differential encoding may be performed to produce the initial shaping sign bit assignment, tj(0) to tj(2) and tj+1(0) to tj+1(2) using the differential encoding rules: tj(k) = Pj'(k) ⊕ tj-1(k) tj+1(k) = P'j+1(k) ⊕ tj(k)

(6)

and finally the spectral shaper converts each tj(k) bit to PCM code sign bit $k and each tj+1(k) bit to PCM code sign bit $k+3 . In the case when Sr=3 and S=3, the odd bit in each shaping frame may be differentially encoded to produce differentially encoded outputs P'j, P'j+1, and P'j+2. A second order differential encoding may be performed on each shaping frame to produce the initial shaping sign bit assignments tj(0) to tj(1), tj+1(0) to tj+1(1), and tj+2(0) to tj+2(1) using the differential encoding rules: tj(k) = P'j(k) ⊕ tj–1(k) tj+1(k) = P'j+1(k) ⊕ tj(k) tj+2(k) = P'j+2 (k) ⊕ tj+1(k)

(7)

The spectral shaper converts each tj(k) bit to PCM code sign bit $k, each tj+1(k) bit to PCM code sign bit $k+2, and each tj+2(k) bit to PCM code sign bit $k+4. bk-1

1-Bit Period Delay

Figure 5: Differential encoder direct ntation using a XOR function.

4

impleme -

For the present case spectral shaping function depends on the selected value of Sr. In the case of Sr=0 and S=6, the PCM code sign bits, $0 to $5 may be assigned using input sign bits s0 to s5 with the help of following differential coding rules:

UbiCC Journal - Volume 3

ALGORITHM FOR IMPLEMENTATION OF PARSE-TO-SHAPING-FRAME AND DIFFERENTIAL ENCODER

An algorithm to implement spectral shaping unit of the 56Kbps digital modem transmitter is shown in Appendix I, First of all, S sign bits (s0-s1-S) received from bit parser can be stored at appropriate data memory address (dma) and thereafter various 'dma' can be assigned for the storage of outputs of different stages of spectral shaping unit. After that Sr bit is

26

received from the analog modem during startup operation and then its value can be checked. If it is equal to 0 then a subroutine for parse to shaping frame corresponding to Sr=0 and S=6 is followed otherwise query tasks for Sr=1 and Sr=2 can be performed and then corresponding subroutines LOOP-A, LOOP-B or LOOP-C can be followed. Upon qualifying query task Sr=0, all the six sign bits (S) s0-s5 can be parsed as specified in the ITU Recommendation V.90/V.92. Bit masking technique can be used to perform this parse to shaping frame function and after parsing all the six bits they can be stored at an appropriate 'dma' Pji for further processing by differential encoder. At this stage differential encoding on these parsed bits is performed as per Eq. (4) using the basic structure as given in Fig. 5 and finally obtained sign bits ( $0 - $5) are stored at 'dma' tji , where i= 0-5 for jth data frame. If the analog modem sends Sr=1 during startup procedure then subroutine (a) can be followed. Five sign bits, out of six (s0-s5), are parsed as specified in Table 1. In this case bit-masking technique can also be used to perform parse to shaping frame function and after parsing all the six bits they can be stored at an appropriate 'dma' Pji for further processing by differential encoding section. The next task is to perform differential encoding on odd bits of data frame interval 'j' using bits from present and previous data frame 'j-1' after odd bit differential operation, the encoded bits are stored at new 'dma' Pnji. In the next step, second order differential encoding according to Eq. (5) is performed on Pnji bits of data frame j and previously second order differential encoding bits. Finally the output of second order differential encoder is stored at 'dma' tji, which represents the corresponding sign bits and can be used to assign the sign to the PCM code words. In the case, if query task for Sr=2 get satisfied, subroutine (b) can be used. Initially the data bits received from bit parser are again parsed according to Table 1 using bit masking technique and parsed bits may be stored at 'dma' Pji and Pjp1i corresponding to jth and j+1th data frames. Then odd bit differential encoding is performed on odd bits of data frame 'j' and 'j+1' using bits from present (j) previous (j -1) and next (j+1) data frames. Then after encoded bits may be stored at 'dma' Pnji and Pnjp1i for further processing. Furthermore to achieve sign bits, second order differential encoding may perform as per Eq. (6) using previously encoded bits corresponding to data frame j and j+1 along with the present bits. Process ends with the storage of so obtained sign bits to form PCM code word at 'dma' tji and tjp1i corresponding to data frame j and j+1. Similar tasks can be performed for the case of Sr=3 using Eq. (7) corresponding to three data frames j,

UbiCC Journal - Volume 3

j+1 and j+2 to obtain sign bits to form PCM code words as per subroutine (c).

5

DEVELOPMENT OF ASSEMBLY LEVEL PROGRAM FOR PARSE - TO SHAPING FRAME AND DIFFERENTIAL ENCODER

Assembly level program corresponding to the algorithm discussed in previous section to implement parse to shaping frame and differential encoding functions of 56Kbps digital modem transmitter on TMS320C50PQ57 DSP has been developed during present study. Query task has been implemented with the help of CPL (compare the specified constant with the contents of 'dma' specified by the Auxiliary resister) and BCND (conditional branch, get activated when carry-bit is high) instructions. Parse to-shaping-frame function has been implemented with the help of bit masking technique, which can be implemented with the help of AND instruction with appropriate shift. This is used to AND the content of accumulator with a constant, to mask a particular bit. Differential encoding (both odd bit and second order) function has been implemented with the help of XOR (the content of dma are exclusive-ORed with the contents of the accumulator) instruction. Various ‘dma’, which acts like 1-bit delay along with other supporting instructions, have been used to implement differential encoder as shown earlier in Fig. 5. 6

SIMULATION OF PARSE –TO – SHAPING FRAME AND DIFFERENTIAL ENCODER

For simulation purpose Code Composer Studio (CCS) software package from Texas Instruments, USA has been used. Assembly level program has been converted into the appropriate format for loading into the simulator of CCS using assembler and linker programs. Simulator status before execution of the spectral shaping program for Sr = 0 (stored at 'dma' 802CH) and incoming data 0025H (i.e. s0 – s5 having values 1,0,1,0,0,1 respectively) corresponding to data frame j (stored at 'dma' 8000H) along with the previous sign bit $5 =1(stored at dma 802BH), is shown in Fig.6. Program has been debugged and after execution simulation results have been obtained which are shown in Fig. 7. Results corresponding to parse to shaping frame have been stored at 'dma' 8003H to 8008H, which are in accordance with the theoretically predicted results as per Table 1. Similarly the outputs of differential

27

Figure 6: Simulator status before execution of spectral shaping program for Sr = 0

Figure 7: Simulator status after execution of spectral shaping program for Sr = 0

UbiCC Journal - Volume 3

28

encoder have been stored at 'dma' 801BH to 8020H which again exactly matches with the theoretically predicted results as per Eq. (5) and hence confirm the successfulness of assembly program corresponding to option Sr=0. To further confirm the successfulness of developed algorithm and corresponding assembly level program, another case for Sr=3 is considered here. In this case three data frames are required so output of bit parser corresponding to data frame j(000BH), j+1(0002H) and j+2 (0005H) has been stored at 'dma' 8000H, 8001H and 8002H respectively. Another initialization includes Sr = 3 ('dma' 802CH), previous odd bit differential encoding output in data frame interval 1 of data frame j-1 (i.e. P 'j-1(1) = 1 stored at 'dma' 801AH) and previous outputs of second order differential encoding in data interval 0 & 1 corresponding to data frame j-1 (i.e. tj-1(0)=0 at 'dma' 8026H and tj-1(1) = 1 stored at 'dma' 8027H). With above initialization the status of the simulator is shown in Fig. 8 and simulation results after debugging and executing the program have been presented in the Fig. 9. Parse to shaping frame results have been stored at 'dma' 8003H to 8008H and results of odd bit differential encoding along with second order differential encoding have been stored at 'dma' 8009H-800AH, 8014h-8015H, 8017-8018H and 801BH-801CH, 8021H-8022H, 8024H-8025H respectively which are in accordance with the theoretically predicted results. Similarly program was simulated for other options Sr=1 and Sr=2 with different outputs of bit parser and absolute performance have been achieved. 7

IMPLEMENTATION OF PARSE - TO SHAPING - FRAME AND DIFFERENTIAL ENCODER ON TMS320C50PQ57 DSP CHIP

Program for parse - to - shaping - frame and differential encoder to perform spectral shaping has been loaded into the DSP Module for its practical implementation using communication software program XTALK provided by VI Microsystems Pvt. Ltd. Same inputs and initialization parameters as used during simulation have been taken again here and it has been observed that practical results are in accordance with the simulated or theoretically predicted results which confirms the successfulness of the present study. Various implementation parameters regarding present implementation of parse to shaping frame and differential encoding functions to perform spectral shaping in the transmitter of 56Kbps digital modem have been given in Table 2.

UbiCC Journal - Volume 3

Table 2: Summery of implementation parameters

Function

Parse to Shaping Frame and Differential Encoding

8

Data Memory Used (W)

Program Memory Used (W)

44

251

Program Execution Time (µs) Depends upon the value of Sr (1.123 – 1.368)

CONCLUSION

Simulation and implementation of functional units such as parse - to - shaping - frame and differential encoder etc. of spectral shaping block of 56Kbps digital modem transmitter have been discussed in the present paper. A combined algorithm for implementation of the parse to shaping frame and differential encoder functions utilized in transmitter of 56Kbps digital modem has been suggested. Parse - to - shaping - frame function has been implemented with the help of bit masking technique where as differential encoder has been implemented with the help of XOR functioning and delay line implementation. Assembly level program corresponding to algorithm developed during present study has been simulated and loaded into the DSP module to implement parse - to - shaping - frame and differential encoding process. Practical results obtained have been found to be same as of theoretical and simulated ones.

ACKNOWLEDGEMENTS One of the authors Davinder Pal Sharma is thankful to Guru Nanak Dev University, Amritsar, for providing Research facilities at Department of Electronics Technology for the present research work.

10 REFERENCES [1] A. A. Gokhale: Introduction to Telecommunication, Thomson Asia Pvt. Ltd. (2001). [2] D. E. A. Clarke et. al: Emerging Broadband

29

Figure 8: Simulator status before execution of spectral shaping program for Sr=3

Figure 9: Simulator status after execution of spectral shaping program for Sr=3

UbiCC Journal - Volume 3

30

Access Technologies, British Telecommunication Technology Journal, Vol. 16, pp. 187-195 (Oct. 1998). [3] V. U. Reddy: Voice-band Modems: A Device to Transmit Data over Telephone Networks Part (I): Basic Principles of Data Transmission, Resonance, Vol. 6, pp. 56-65 (May 2001). [4] V. U. Reddy: Voice-Band Modems: A Device to Transmit Data over Telephone Networks Part (II): Advanced Ideas which made High Data Rates possible, Resonance, Vol. 6, pp. 6070 (June 2001). [5] F. Adams et. al: Today's Access Technologies, British Telecommunication Technology Journal, Vol. 16, pp. 21-33 (Oct. 1998).

Constrained Optimization Problem, Proc. of IEEE ISIT, pp. 330 (June 1994). [17] M. Campanella, G. Garbo, G. Mamola: A Design Technique for Spectral Shaping in CPM Systems, IEEE Transactions on Communications, Vol. 45 (May 1997). [18] J.K. Cavers, R.F. Marchetto: A New Coding Technique for Spectral Shaping of Data, IEEE Transactions on Communications, Vol. 40 (Sept. 1992). [19] J. G. Proakis, D.G. Manolakis: Digital Communication, McGraw Hill Inc. (2000).

[6] Georgia Tech Studies: (1998). http://www.gvu.gatech.edu/user_surveys/surve y-1998-10/graphs/technology/q01.htm.

[21] L. M. Caraballo: System Level Design and Simulation of a PCM Voiceband Modem Compliant with the ITU V.90 Standard, Texas A & M University, M. S. Thesis (May 2000).

[7] ITU-T Recommendation V.90: A Digital and Analog Modem pair for use on the PSTN at Data Signaling Rates of up to 56000 bits/s Downstream and 33600 bits/s Upstream, ITUT V Series Recommendations (1998).

[20]

H. Shankar, P. V. Wagt: Implementing a High-Speed Differential Encoder, Inphi Corporation, White Paper.

[8] Recommendation G.711: Pulse Coded Modulation (PCM) of Voice Frequencies, ITUT G Series Recommendations (1988). [9] L. Brown: PCM Modem Design: V.90 Characteristics, Communication System Design Magazine, Vol. 6 (1998). [10] S. A. Tretter: Constellation Shaping, Nonlinear Precoding and Trellis Coding for Voice band Telephone Channel Modems, Kluwer Academic Publishers (2002). [11] H. Kobyashi: A Survey of Coding Schemes for Transmission or Recording of Digital Data, IEEE Trans. Comm. Tech., Vol. COM-19, pp 1067-1100 (Dec. 1971). [12] A. Croiser: Introduction to Pseudoternary Transmission Codes, IBM Journal of Research & Development, Vol. 14, pp. 354-367 (July 1970). [13] E. Gorog: Redundant Alphabets with Desirable Frequency Spectrum Properties, IBM Journal of Research & Development, Vol. 12, pp 234241 (May 1968). [14] H. Waldman, C. A. M. Pingarilho: Spectral Shaping Codes” Proc. of IEEE ISIT, pp 209 (June, 1994). [15] H. Waldman, C.A.M. Pingarilho: Coding for Spectral Shaping, Proc. of Global Telecommunications Conference, pp. 132-135 (Nov. 1994). [16] A. K. Khandani,: Constellation Shaping as a Geometrical Approach to Solving a

UbiCC Journal - Volume 3

31

APPENDIX – I Main algorithm to perform spectral shaping in 56Kbps digital modem transmitter

Start

Save I/P data frame received from parser at appropriate ‘dma’.

Assign 'dma' to O/P's of different stages of Differential Encoder.

Save Sr bit received from analog modem.

YES

Use bit masking technique to parse bits of data frame 'j' as specified in Table 1

NO Sr = 0

Sr = 1

NO

Loop B

Sr = 2 Store the masked bits (O/P of PSF) at 'dma' Pji (i =0,- - - - ,5)

YES

YES

NO Loop C Loop D

Perform differential encoding as $0 = s0 ⊕ ($5) $i = si ⊕ $i–1

Store Sign bits $0 - $5 at 'dma' tji

UbiCC Journal - Volume 3

STOP

32

APPENDIX – I (contd…..)

LOOP-B

Use bit masking technique to parse bits of data frame 'j' as specified in Table 1

LOOP-C

Use bit masking technique to parse bits of data frame 'j' as specified in Table 1

Store the masked bits (O/P of PSF) at dma 'Pji' (i =0,- - - - ,5)

Store the masked bits at dma 'Pji' and 'Pjp1i' corresponding to jth and j+1th data frame (i =0,1,2)

Perform odd bit differential encoding on odd bit of data frame 'j' according to Eq. (5) also using bits from previous data frame ' j - 1 '

Perform odd bit differential encoding on odd bit of data frame 'j' and 'j+1' according to Eq. (6) using bits from present (j) previous (j - 1) and next (j+1) data frames

Store the encoded bits at dma 'Pnji'

Perform second order differential encoding as specified in Eq. (5)

Store the sign bits ($0 - $5 ) obtained from differential encoder at dma 'tji'

STOP

(a) Subroutine to perform spectral shaping corresponding to Sr=1 and S=5

LOOP-D

Use bit masking technique to parse bits of data frame 'j' as specified in Table 1

Store the masked bits at dma 'Pji' , 'Pjp1i' and 'Pjp2i' corresponding to jth , j+1th and j+2nd data frames (i =0,1)

Perform odd bit differential encoding on odd bit of data frame 'j', 'j+1' and 'j+2' according to Eq. (7) using bits from present (j) previous (j - 1) and next (j+1, j+2) data frames

Store the encoded bits at dma 'Pnji' and 'Pnjp1i' corresponding to data frames j and j+1

Store the encoded bits at dma 'Pnji' , 'Pnjp1i' and 'Pnjp2i' corresponding to data frames j , j+1 and j+2

Perform second order differential encoding as specified in Eq. (6)

Perform second order differential encoding as specified in Eq. (7)

Store the sign bits ($0 - $5 ) at dma tji and tjp1i corresponding to data frames j and j+1

Store the sign bits ($0 - $5 ) at dma tji tjp1i and tjp2 corresponding to data frames j , j+1 and j+2

,

STOP

(b) Subroutine to perform spectral shaping corresponding to Sr=2 and S=4

STOP

(c) Subroutine to perform spectral shaping corresponding to Sr=3 and S=3

Computing and Communication Journal UbiCC Journal - VolumeUbiquitous 3

12

33

EFFICIENT ENERGY MANAGEMENT FOR MOBILE AD HOC NETWORKS M.Tamilarasi1 , S.Chandramathi2 T.G. Palanivelu3 Department of Electronics and Communication Engineering Pondicherry Engineering College, Pondicherry, India. Email: [email protected];2 [email protected]; [email protected];

ABSTRACT A Mobile Ad Hoc network (MANET) is a collection of digital data terminals that can communicate with one another without any fixed networking infrastructure. Since the nodes in a MANET are mobile, the routing and power management become critical issues. Wireless communication has the advantage of allowing untethered communication, which implies reliance on portable power sources such as batteries. However, due to the slow advancement in battery technology, battery power continues to be a constrained resource and so power management in wireless networks remains to be an important issue. Though many proactive and reactive routing protocols exist for MANETs the reactive Dynamic Source Routing (DSR) Protocol is considered to be an efficient protocol. But, when the network size is increased, it is observed that in DSR overhead and power consumption of the nodes in the network increase, which in turn drastically reduce the efficiency of the protocol. In order to overcome these effects, in this paper it is proposed to implement overhead reduction and efficient energy management for DSR in mobile Ad Hoc networks. Key words: MANET, DSR, Energy Management, overhead reduction. 1. INTRODUCTION An Ad Hoc network is a collection of wireless mobile hosts forming a temporary network without the aid of any established infrastructure or centralized administration [1]. The absence of any fixed infrastructure, such as access points, makes Ad-Hoc networks prominently different from other wireless LANs. In such an environment each node may act as a router, source and destination, and forwards packets to the next hop allowing them to reach the final destination through multiple hops. With the proliferation of portable computing platforms and small wireless devices, Ad Hoc wireless networks have received more and more attention as a means for providing data communications among devices regardless of their physical locations. The main characteristic of Ad-Hoc networks is the absence of pre-planning. The topology of the

UbiCC Journal - Volume 3

network is discovered on the fly, after the network’s deployment. Thus, such a network must exchange a number of messages which are used to “set-up” various parameters in the network. Example of such parameters is the very existence of other nodes in the network, their position, information about their neighbors, what they offer (e.g., local maps, files, printing facilities etc). Various solutions for Overhead Reduction and Power Management in DSR protocol are found in the literature. Dynamic Source Routing protocol is a simple and efficient routing protocol designed specially for use in multi-hop wireless Ad Hoc networks of mobile nodes. DSR allows network to be completely self-organising and selfconfiguring, without the need for any existing infrastructure or administration [2].Energy management is an essential requirement for the efficient operation of the battery powered MANETs. Rong Zheng and Robin Kravats

34

proposed an extensible on-demand power management framework for Ad Hoc networks in [3] that adapts to traffic loads.Sheetalkumar Doshi and Timothy X Brown[4] identified the necessary features of an on-demand minimum energy routing protocol and suggested mechanisms for their implementation. Jorge Nuevo[5] elucidates the simulating software used in this work. It presents an easy tutorial to use and simulate Ad Hoc networks in GloMoSim as well as the basic structure of the simulator. Several distributed power aware routing protocols in mobile ad hoc networks are discussed in [6]. Gill Zussman et al [7] introduced iterative algorithms for energy efficient routing in ad hoc networks. The problem is formulated as an anycast routing problem in which the objective is to maximize the time until the first battery drains out.Nicolaos B.Karayiannis et al present an approach which relies an entropy constrained routing algorithm for power conservation, which were developed by utilizing the information theoretic concept of the entropy to gradually reduce the uncertainty associated with route discovery through a deterministic annealing process [8]. Stephanie Lindsey and Cauligib S. present energy efficient one-to-all and all-to-all broadcast operations of ad hoc network in [9]. Although establishing correct and efficient routes is an important design issue in MANETs, a more challenging goal is to provide energy efficient routes. Authors of [10] give the idea of minimize the active communication energy required to transmit or receive packets or energy consumed by the idle nodes. Incorporating current estimates of battery levels into routing metrics has been shown in [11] to reduce the demand on nodes with little remaining energy and allow them to participate in the network longer.The Energy Saving Dynamic Source Routing (ESDSR) protocol is introduced in [12] to maximize the life span of a mobile ad hoc network. Pierpaolo Bergamo et al [13] proposed distributed power control as a means to improve the energy efficiency of routing algorithms in ad hoc networks. A table-driven protocol called BEST and an on demand routing protocol called DST were introduced in [15] which are compared to DSR. Samir R Das et al introduce several routing protocols including protocols specifically designed for Ad hoc networks in [16] and traditional protocols such as link state and distance vector used for dynamic networking. It is found that the new generation of on-demand routing protocols use much lower routing load while the traditional link state and distance vector protocols provide better packet delivery and delay performance.Three routing protocols for ad hoc networks namely DSR, DSDV and AODV are compared in [17]. Three different realistic scenarios are considered and it is found that the reactive protocols (AODV and DSR) perform significantly better than DSDV. AODV fared better than DSR at higher traffic loads while DSR performed better than AODV at moderate traffic load. In this paper we propose an algorithm for modifying DSR to reduce overhead by reducing the number of route reply packets and the header size of DSR data packets. Besides this an algorithm for energy management is incorporated in the Modified DSR by transmitting the data packets with minimum required energy .The rest of the paper is organized as follows: Section 2 deals with the Modified DSR for overhead reduction. Section 3 describes the Efficient Energy

UbiCC Journal - Volume 3

Management algorithm. Section 4 presents the simulation results and conclusions are given in Section 5. 2. MODIFIED DSR The propagation of Route Request and Route Reply packets in DSR are as shown in Figure.1 and Figure.2 respectively.

Figure.1 DSR Route Request

Figure. 2 DSR Route Reply

Figure.3 DSR (modified) Route Reply The main drawback in DSR protocol is the large number of unwanted Route Replies, because a Route Reply is sent through all the available routes leading to unnecessary congestion and waste of energy (battery power). It is found through observations that it is sufficient if the destination node sends the Route Reply through one selected route rather than through all the routes. Hence it is proposed to limit the number of Route Replies to only one. This is sent via the route through which the destination received the first Route Request, because it is the most active route for the particular source-destination pair at the moment of sending the request. Moreover this is the route through which the data

35

packets can be transmitted fastest. Hence the same is chosen as the route for the data transmission, which can reduce the propagation delay to a great extant. Furthermore it leads to the decrease in control packets generated in the network and the increase in packet delivery ratio. Thus these modifications make the data transmission optimum. Figure.3 shows the modified DSR for route reply mechanism. Another drawback of the DSR protocol is the overhead, which occurs due to appending of the addresses of intermediate nodes present on the route from source to destination (this happens especially as the number of nodes in a particular network increases). The Data Packet Format of existing DSR protocol is shown below.

Figure .4 Data Packet Format of existing DSR protocol Here it is proposed to exclude the addresses of intermediate nodes from the header of the data packets in order to reduce the overhead in existing protocol. Thus the header of Data Packet contains only source and destination addresses as shown below.

Figure.5 Data Packet Format of modified DSR protocol

Step7: After re-broadcasting acknowledgement will be sent to

the data packet, the previous node

3. Efficient Energy Management in Modified DSR In the Ad Hoc networks, each node is powered by a battery which has a limited energy supply [4]. Over the time, various nodes will deplete their energy supplies and drop out from network. Unless nodes are replaced or recharged, the network will eventually become partitioned. In a large network, relatively few nodes may be able to communicate directly with their intended destinations. Instead, most nodes must rely on other radios to forward their packets. Some radios may be especially critical for forwarding these packets because they provide the only path between certain pairs of radios. Associated with each radio that depletes its battery and stop operating, there may be a number of other radios that can no longer communicate. For this reason a number of researchers have focused on the design of communication protocols that preserve energy so as to network failures for as long as possible [12]. In existing DSR, each node uses constant power to forward the packet or to transmit the packet. According to the DSR draft [1] each node uses 280mw power. Irrespective of the distance between adjacent nodes, each node transmits with a constant power. In the proposed MDSR the transmit power is tuned according to the distance between transmitting node and receiving node [3].

SNA- Source Node Address INA- Intermediate Node Address DNA- Destination Node Address

3.1 Algorithm for implementing power management:

2.1 Implementation of Overhead Reduction

Step1: Once the route request process is over and the route is established, the Route Reply packet is broadcast by the destination

2.1.1 Algorithm for overhead reduction: Step1: Source broadcasts Route Request packets which are heard by nodes within the coverage area

Step2: The immediately previous node in the selected path determines the distance between itself and the destination, by means of the time taken by the Route Reply packet to reach it.

Step2: The neighboring nodes re-broadcast the route request Step3: Destination sends Route Reply only to the first received Route Request

Step3: All the nodes in the selected path follow the same procedure and the distance between the nodes is determined and stored in the cache.

Step4: Source address, destination address and previous node addresses are stored during route reply.

Step4: The transmitted power is determined using the following formula, Transmitted Power = (a x d4) +c

Step5: The data packet contains only source & destination addresses in its header. Step6: When the data packet travels from source to destination, through intermediate nodes, for re-broadcasting of data packet, the node verifies source and destination addresses in its cache. If it is present, the data packets are forwarded, otherwise it is rejected. .

UbiCC Journal - Volume 3

(1)

Where‘d’ is the distance between two adjacent nodes ‘a’ and ‘c’ are arbitrary constants a=Pr*k

(2)

Pr=Minimum Received power=-91dbm k =8 then find c a = 6.48 x 10-11 and c = 30 x 10-3 W

36

Step5: Transmitted power is varied in accordance with the distance 4.SIMULATION RESULTS Using GloMoSim (Global Mobile Simulator) the DSR was simulated. Then the proposed modifications are introduced and the modified protocol is simulated to verify the predicted changes in parameters of packet delivery ratio, end to end delay and number of control packets at different pause times, with respect to the number of nodes in the network. The packet delivery ratio(PDR) is the ratio of the number of packets received by the destination to the number of packets transmitted by the source. PDR reduces as the pause time decreases from 900 seconds to 0 seconds. This is due to the mobility of the network and the probability of link failures increases as the pause time decreases. It is observed that the MDSR maintains a better Packet delivery Ratio than the existing DSR. This may be attributed to the reduction in the number of control packets which reduces the collisions between the transmitted data packets and control packets. It is also observed that the MDSR maintains a significantly high Packet Delivery Ratio than the existing DSR as the pause time decreases. This is a result of the fact that in the MDSR, unlike in existing DSR, the most active path is selected which is less probable to fail and in turn increases the Packet Delivery Ratio. The number of control packets is the sum of all the Route Requests, Route Replies and Route Error packets. In existing DSR, the destination initiates Route Reply for all the Route Requests received, but in MDSR, destination initiates Route Reply only to the first received Route Request. Thus, it is seen that the MDSR maintains less number of control packets than the existing DSR. As the pause time decreases, the complexity of the network increases and the probability of link failures increases. Though the MDSR reduces the number of Route Replies, the source has to re-perform the route discovery process in case of link failures, unlike in existing DSR, where it chooses the next path in its route cache. Thus, as the mobility increases, the MDSR requires almost the same number of control packets as the existing DSR.

Figure.6 Packet Delivery ratio Vs. No. Of nodes for pause time of 900s

UbiCC Journal - Volume 3

Figure.7 Packet Delivery ratio Vs. No. Of nodes for a pause time of 600 s

Figure.8 Packet Delivery ratio Vs. No. Of nodes for a pause time of 300 s.

Figure.9 Packet Delivery ratio Vs. No. Of nodes for a pause time of 0s

37

Figure.10 Number of Control Packets vs. No. Of nodes for a pause time of 900 s.

Figure.13 Number of Control Packets vs. No. Of nodes for a pause time of 0 s

Figure.11 Number of Control Packets vs. No. Of nodes foa pause time of 600 s

Figure.14 Delay Vs. No. Of nodes for a pause time of 900 s

Figure.12 Number of Control Packets vs. No. Of nodes for a pause time of 300 s

Figure.15 Delay Vs. No. Of nodes for a pause time of 600 s

UbiCC Journal - Volume 3

38

Figure.18 shows the change in the percentage energy saving in accordance with the distance between the adjacent nodes for the modified DSR .It is observed that more energy is saved when the distance of separation is less and hence, an effective energy management is obtained in the modified DSR while in the existing DSR there is no energy management since the transmitting energy is constant regardless of the distance between the adjacent nodes.

Figure.16 Delay vs. No. Of nodes for a pause time of 300 s

Figure.17 Delay Vs. No. Of nodes for a pause time of 0 s The end-to-end delay is the time taken by a data packet to reach destination from the source. As the number of nodes increases, the complexity of the network increases and hence the end-to-end delay increases. As the pause time decreases, the mobility increases, which increases the probability of link failures and hence the end-to-end delay increases. In MDSR, the header of the data packet is reduced and the route cache is limited to contain the addresses of only the previous node, source and destination nodes which improve the processing capacity of the nodes. This reduces the processing time of the nodes which in turn reduces the end-to-end delay when MDSR is compared to existing DSR.

Figure.19 Percentage energy saving with respect to the distance between the adjacent nodes for energy efficient MDSR compared to DSR .

Figure.20 Comparison of existing DSR, MDSR without energy management and MDSR with energy management

Figure.18 Energy consumption variation with respect to Distance of separation between the nodes

UbiCC Journal - Volume 3

In Figure.19 it is observed that irrespective of the number of nodes in the network, the modified DSR shows an average percentage energy saving of 37.9 % in comparison to the existing DSR .This efficient energy saving results due to the reduction in the number of control packets and also due to the variation of the transmit power between two nodes as a function of the distance between the adjacent nodes rather than the constant power used for transmission between nodes irrespective of the distance between them as in the existing DSR. Figure20 shows a comparison between the existing DSR, modified DSR before energy management and MDSR after energy management for varying network densities. It is observed that MDSR due to overhead and delay reduction gives a better energy management than

39

the existing DSR but MDSR with energy management still enhances the energy consumption. It may also be seen that the power is almost independent of the density of the network connections in all the three cases. Thus it may be justified that the MDSR after energy management becomes an energy efficient protocol for mobile ad hoc networks.

Figure21,Figure.22 and Figure23 show the comparison among exiting DSR, Modified DSR and Modified DSR with energy management for packet delivery ratio, number of control packets and delay. There is no much change in packet delivery ratio before energy management and after energy management when number of nodes is less in network. As number of nodes increases PDR has decreased and same as existing DSR. Regarding the number of control packets there is no significant change. Delay has increased after incorporation of energy management.

5. CONCLUSIONS

Figure.21Packet Delivery Ratio For Energy Efficient MDSR Compared to DSR

It is observed that the modifications brought about in the existing DSR reduces the end to end delay and the number of control packets which is the sum of Route Request, Route Reply and Route Error packets while it is observed that the modifications do not reduce the packet delivery ratio. The average percentage energy saved per node is found to be 37.9 %.Thus there is an enhancement of energy management in the DSR protocol due to the modifications made and hence it can be considered a energy efficient protocol.

6. REFERENCES

[1] [2]

Figure.22 Number Of Control packets For Energy Efficient MDSR compared to DSR

[3]

[4]

[5] [6] Figure.23 Comparison Of Delay for Energy Efficient MDSR,MDSR and Existing DSR

UbiCC Journal - Volume 3

Charles E. Perkins, “Mobile Ad-Hoc Networks,” Addison-Wesley, 2000. David B. Johnson, David A. Maltz and Yih-Chun Hu, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR),” Internet Draft, draftietf-manet-dsr-09.txt,15April2004. URL:http://www.ietf.org/internetdraft/draf t-ietf-manet-dsr-09.txt Rong Zheng and Robin Kravats, “Ondemand Power Management for Ad-hoc Networks,” Journal of Ad Hoc networks, vol.3, pg: 51-68, ELSEVIER, 2005. Sheetalkumar Doshi and Timothy X Brown, “Design Considerations for an Ondemand Minimum Energy Routing Protocol for Wireless Ad Hoc Network,” Mobile Computing and Communication Review, Vol.6, No.2, July 2002. Jorge Nuevo, “A Comprehensible GloMoSim Tutorial” September 2003. Qun Li, Javed Aslam and Daniela Rus, “Distributed Energy-Conserving Routing Protocols,” Proceedings of 36th HICSS 2003. 40

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Gill Zussman, Adrian Segall, “Energy Efficient routing in ad hoc disaster recovery networks” ELSEVIER, 2003. Nicolaos B.Karayiannis, Sreekanth Nadella, “Power-conserving routing of ad hoc mobile wireless networks based on entropyconstrained algorithms”, ELSEVIER, pp.2435, 2006. Stephanie Lindsey, Cauligib S. Ragavendra, “Energy efficient all-to-all broadcasting for situation awareness in wireless ad hoc networks”, journal of parallel and distributed Computing, pp.15-21, 2003. Chansu Yu, Ben Lee, Hee Yong Youn,”Energy efficient routing protocols for mobile ad hoc networks”. URL:eecs.oregonstate.edu/~ben1/pulications/ Book_chapters/Handbook_AHWN_routing03 .pdf. Frederic.J.Block, Carl W.Baum, “Information for routing in energy-constrained ad hoc networks”, ELSEVIER, pp.499-508, 2006. Mohommed Tatique, Kamal E.Tape, Mohomad Naserian, "Energy saving dynamic source routing for ad hoc wireless network", proceeding of the third international symposium on Modeling and optimization in mobile, Ad Hoc wireless networks, pp 305-310,2005. Pierpaolo Bergamo, Alessandra Giovanardi, Andrea Travasoni, Daniela Maniezzo, Gianluca Mazzini, Michelle Zorzi,”Distributed power control for energy efficient routing in ad hoc networks”, Wireless networks, pp.29-42, 2004. Jyoti Raju, J.J Garcia-Luna-Aceves, “Scenario-based Comparison of SourceTracing and Dynamic Source Routing Protocols for Ad Hoc Networks”, proceedings of the 36th Hawaii international Conference on System Sciences, 2002. Samir R Das, Robert Castafieda, Jiangatao Yan, Rimli Sengupta, "Comparative Performance Evaluation of Routing Protocols for Mobile, Ad Hoc Networks", IEEE,1998. Per Johansson, Tony Larsson, Nicklas Hedman, Bartosz Mielczarek, Mikael Degermark, “Scenario-based Performance

UbiCC Journal - Volume 3

analysis of Routing Protocols for Mobile Ad-hoc Networks”, International conference on Mobile computing and networking,pp.195-206,1999.

41

SELECTIVE SUSPENSION OF TRANSMISSION FOR AVOIDING PRIORITY REVERSAL IN MOBILE AD HOC NETWORKS #R.Gunasekaran, Dr.V.Rhymend Uthariaraj Department of Information Technology, Anna University, Chennai, India #[email protected]

ABSTRACT Ad hoc wireless networks are a very potential field offering lot of scope for research. In these networks, the Medium Access Control (MAC) protocols are responsible for coordinating the access from active nodes. These protocols assume greater significance since the wireless communication channel is inherently prone to such problems as hidden terminal, exposed terminal and fading effects .The scheme proposed here is used to perform priority scheduling in nodes resolving any contention scenario that can arise for the channel in the best possible manner. Alert transmission packets are used as a means of notification whenever a high priority node wants to transmit data. Suspend transmission packets are used to avoid priority reversal issue and a retry count is implemented to avoid starvation among the nodes. Keywords: Ad Hoc Networks, Alert Transmission, Suspend Transmission, Priority, Retry Count

1

INTRODUCTION

Contention for channel among the nodes is resolved using Contention based protocols. In a heterogeneous network like ad-hoc several problems like hidden terminal and exposed terminal problem can arise. The popular Carrier Sense Multiple Access MAC scheme and its variations such as CSMA [1] with Collision Detection (CSMA/CD) developed for wired networks, cannot be used for wireless networks. Priority scheduling is a means to avoid channel contention among the various nodes in the network. The scheme here proposes a new protocol for effective priority scheduling. Two new packets have been designed namely Alert Transmission and Suspend Transmission packets which form the crux of the new scheme. A retry count is implemented to avoid priority starvation. The rest of this paper is organized as follows. Section 2 presents the related work. The proposed Priority Scheduling scheme with a Suspend Transmission mechanism is explained in Section 3. Simulation results are given in section 4. 2

RELATED WORK

2.1 Classic CSMA problems In fig 1 Node B is within the range of A and C but nodes A and C are not visible to each other Let us consider the case where A is transmitting to B. Node C, unaware of the transmission at B can UbiCC Journal 3 transmit data -toVolume B thus causing collision at B. This is referred to as the hidden-terminal problem, as nodes

A and C are hidden from each other. Now consider another case where B is transmitting to A. Since C is within B’s range it receives the transmission too and can eventually defer its own transmission which is unnecessary as C’s transmission is in no way going to affect A receiving the packets from B. This is known as the exposed terminal problem i.e. C is exposed to B.

Figure 1: Hidden Terminal Problem Different flows in multi-hop networks have different degree of contention. Here, the contention degree for a flow is defined as the number of flows with which it is competing for the channel. Two types of MAC schemes are prominently used. Reservation and contention based schemes. Reservation based schemes usually make some assumptions about high priority traffic. Flow scheduling is done locally while contention resolving probabilistically. Blackburst dealt in [8] is a typical example where a high priority node transmits this black-burst signal as a notification for its transmission. Reference [9] generalizes this for wireless ad-hoc network. That is each station can sense the transmission of the other42 nodes in the network. Reference [6] explains a

dynamic priority scheduling with a CAN MAC protocol. 2.2 IEEE MAC 802.11 DCF The 802.11 DCF function [5] is subjected to several research modifications, which is giving a back-off counter to each node such a way that every node can choose a random number between 0 to maximum contention window size. After sensing the channel to be idle for an inter-frame space the nodes start counting their back-off counters to zero, and if the channel is found to be busy they freeze the backoff counters. The value of Contention Window is constrained to be between CWmin and CWmax. A source station sends an RTS for which it receives back CTS following which it transmits data and gets an ACK packet back. In the event of CTS or ACK not received the source is led to believe that collision has occurred, so it is imperative that there is adequate waiting time for the source before it arrives at some decision. There are two waiting stages in

low priority packets that hear either BT1 or BT2 will defer their transmissions for some duration. In this way, channel access priority of a high priority node can be ensured. Certainly, if there is no high priority packet backlogged at a high priority node, a low priority node will not receive any busy tone. 3

PROPOSED SCHEME

In this scheme priority scheduling in wireless ad-hoc networks, using alert transmission mechanism is implemented. This way contention for channel access between nodes is resolved. This is also seen to eliminate the hidden terminal and exposed terminal problems occurring frequently in ad-hoc networks. Individual nodes are assigned priority ‘Low and High’ based on the back off counter value. It is computed using the formula shown in Eq. (1) Back Off = (1%cw)*priority*slot time

…..(1)

where cw is the size of the contention window for each node. And, priority is a user defined integer value. For each node slot-time is 20µs, and CWmin < CW < CWmax, where CWmin is the minimum CW, and it is usually set to 32 and CWmax is the maximum CW and often set to 1024.

Figure 2: Distributed Coordination Function (DCF) ad hoc network, the inter frame space (IFS) stage and the back off stage. The back off counter is a random value between zero and the Contention Window. For example high priority source stations randomly choose the back off interval from [0, 2i+1 -1] and low priority source stations choose from [2i+1, 2i+2 -1], where i is the number of consecutive times a station attempts to send a packet. Two different values of CWmin and CWmax are set for different priority classes. It proposes an exponential increase by a factor of 2 in the event of collision. 2.3 Existing Scheme In order to effectively perform a priority scheduling among these nodes in the network, a priority scheduling scheme was proposed. Whenever a high priority packet is backlogged at some high priority node 0, it will send a primary busy tone signal every M slots before it acquires the channel, where M is a parameter of the proposed scheme. When another node1 of lower priority hears this primary busy tone signal (BT1), it will send a secondary busy tone signal (BT2). All nodes with UbiCC Journal - Volume 3

43

Figure 3: Transmission of AT1 and AT2 packets and Data between the sender, receiver and neighbors. After DIFS idle time, the station senses the medium to determine whether or not it is idle. If it is idle, then the station decrements its back off value by a slot time, otherwise the back off value stays the same. When the back off value of a station reaches 0, the station sends an alert transmission packet AT1 to its immediate neighbors, which again sends secondary AT2 packet to its neighbors and so on such that the hidden terminal problem is effectively overcome. The transmission of AT1 and AT2 packets is shown in Fig 3. All the nodes in the network are thus conveyed of the node’s intention to transmit data. A typical Alert transmission packet shown in Fig 4 will contain the following information: Sender Address, Initial Back Off counter of the original sender node, Receiver Addresses, and The time of transmission. The frame format of the Alert Transmission Packet (AT) is as follows:

Figure 5: Suspend Transmission Packet during Priority Reversal Therefore in order to eliminate such a scenario, whenever a high priority node receives a Alert transmission packet either directly or via indirect means it can compare the initial back off value in the Alert transmission packet to check if the source node is of higher priority or lower than its own. The high priority node will immediately send a SUSPEND TRANSMISSION (ST) packet for suspending the transmission this will be directed at the source node. However not all high priority nodes can transmit the ST packet. This transmission of ST is decided based on the following criteria: original priority of the node, priority threshold determined through average packet transmission time. Only if a high priority node satisfies these conditions it can transmit the ST packet. The ST packet contains the following fields: Sender Address, Receiver Address, and Initial Back off counter, Time sent. The frame format of the Suspend Transmission Packet (ST) is as follows:

Figure 4: Frame Format of Alert Transmission Packet (AT1 or AT2) Duration represents the time of sending and TA is the sender address while RA is the receiver address. Other lower priority nodes sensing the transmission immediately freeze their back off counters and defer their transmission to a later period. 3.1 Priority Reversal A priority reversal occurs when a low priority node has its back off at zero when nodes at a higher priority are in contention. This can lead to a situation where the lower priority node grabbing the channel before the Higher priority nodes.

Figure 6: Frame Format of Suspend Transmission Packet Duration represents the time of sending and TA is the sender address while RA is the receiver address. The right to send an ST packet for nodes will not remain constant it can be subjected to changes based on network characteristics. An example scenario is depicted in Fig 7. Nodes 1, 4 are high priority nodes and nodes 3, 5 are of low priority. At t1, the initial back off values of nodes 1, 3, 5 are 10, 17 and 18. AT1 Node 1 t1 (bc=10)

DIFS+ SIFS WAIT

DATA

t2(bc=0)

ST

AT1

Node 4

t3

AT1

UbiCC Journal - Volume 3

t1 (bc=17) t2(bc=7)

t5(bc=7)

Node 5 t1 (bc=18) t2(bc=8)

t5(bc=8)

DATA

t9(bc=0)

t4 t5(bc=9)t6(bc=2) t7

Node 3

DIFS+ SIFS WAIT

DIFS + SIFS WAIT

t6(bc=0)

t8(bc=3)

t6(bc=1)

Figure 7: Scenario explaining the Priority Reversal 44

issue with 5 nodes. At t1, nodes 1, 3, 5 compete for the channel access while 4 stays away from contention. Once the DIFS time expires, the back off time of node 1 counts to zero and then, it sends an alert transmission packet AT1 to all its neighbors. The nodes which receive AT1 send AT2 packet to its neighbors. After the SIFS period expires, nodes freeze their back off counters. Nodes 3, 5 have their back off counters frozen at 7, 8 respectively and their retry counts are increased by 1. Node 1 after sending AT1 waits for a DIFS+SIFS period and then takes control of the channel for data transmission. At t4, nodes 4 (BC =9), node 3, 5 contend for the channel access with 3 beating 4 leading to a priority reversal. To overcome this, once the AT1 packet of 3 reaches node 4, it realizes that it has high priority than node 3. Hence, it disregards the AT1 packet and transmits a SUSPEND TRANSMISSION packet ST to node 3 for suspending the transmission. The ST packet contains the current back off value, curr of the sender node i.e., node 4 in our case. Once node 3 receives the ST packet from node 4, it resets it back off value according to the formula. New Back off = curr + slot time

(2)

Where, curr is the current back off value of the node sending ST. After sending ST, node 4 waits for an SIFS period and then starts counting its back off timer to zero. Once a node receives ST it is necessary to do the following apart from resetting its back off value. Firstly, there is a variable backpri initialized with the value of initial back off counter of the node. From the ST packet received, the current back off value of the high priority sender is obtained. This value is compared with the existing value in backpri and the smaller value is stored in backpri. Simultaneously, the back off counter is frozen. If current back off time of sender < backpri, then Overwrite backpri as follows Backpri=current back off time of sender Else Do Nothing Similarly, when this low priority node gets into contention in the next idle phase and if it loses contention again by receiving an ST from a high priority node, it will compare the backpri value with the current back off value of the sender and store the smaller value into backpri. Thus, the priority reversal issue is dealt with using Suspend Transmission packets. 3.2 Starvation Avoidance A Retry Count (RC) is used to prevent the UbiCC Journal - Volume 3

excessive starvation of a low priority node. This can be fixed based on the number of nodes in the network and network characteristics. The number of times the back off counter is frozen is the retry count. The backpri value of the low priority node comes in handy whenever its RC value reaches a threshold. Once a node’s retry count reaches this threshold the following occurs. The initial back off counter value is replaced now with backpri value and a slot time is added to it. But before overwriting the initial back off value it is imperative that a copy of it is stored as backup in initial backup variable defined. Now the backpri value is used to overwrite the new back off value which denotes the current or active back off value of the low priority node. That is once RC threshold is reached do the following Initial backup=Initial back off

(3)

Initial back off=backpri+ slot time

(4)

New back off= backpri

(5)

The backpri value denotes the lowest current back off value of the high priority nodes that have beaten the current node to access the channel. This means the low priority node is promoted to a high priority status temporarily, this is only fair because it has starved so long a period defined by RC threshold to transmit the current packets, and it is necessary that some means are done to promote its priority status, to minimize the further backlogging of these packets. The low priority node will now enter contention as a high priority node since it has its initial back off value reset. Now the initial back off value will remain as backpri + slot-time only till the node transmits the current packets backlogged. The RC value is reset to zero as shown in Eq. (6) and initial back off value is set to the initial backup in Eq. (7) after current packets are transmitted. RC=0

(6)

Initial back off= initial backup

(7)

This means after the nodes are transmitted the node’s priority is reverted back to its original status, which is only agreeable as it cannot be promoted all the time. This scheme would thus be helpful in avoiding starvation of low priority nodes for the channel access. 4. SIMULATION The proposed scheme is implemented with the help of ns2 and the results of the implementation analysis are illustrated in the following graphical representations. The Random Way Point model [10] is used in ns2 simulation. Figure 8 indicates the 45

comparisons in aggregate throughput between the proposed Alert Transmission schemes to the existing IEEE MAC 802.11 scheme. The number of nodes is used as the measuring criteria. The simulation is carried out with 20, 40, 60, 80, 100 nodes. The results show that the proposed scheme produces better average throughput when the number of nodes increases. IEEE MAC 802.11 AT-ST SCHEME

2500

5. CONCLUSION A new priority scheduling scheme (Alert Transmission Scheme) is proposed for ad hoc networks. With the use of AT1, AT2 the Alert Transmission Scheme ensures the channel access of high priority data packets. Priority reversal is also avoided by the use of Suspend Transmission ST packets. To avoid the starvation of lower priority packets and to ensure a fair scheduling, retry count is used.

2000 1500

5 NODES 10 NODES 15 NODES

1000

120

500

100

0 0

20

40 60 Number of nodes

80

100

Figure 8: Comparisons in aggregate throughput between proposed Alert Transmission scheme and IEEE MAC 802.11 scheme.

Delivery Ratio of High Priority Packets

Figure 9 shows the comparison results in the delivery ratio of high priority packets between the proposed scheme and the IEEE MAC 802.11 scheme. The results show that the high priority packets are delivered at a much better rate in the proposed scheme. IEEE MAC 802.11 AT-ST SCHEME 1.2 1 0.8 0.6

THRO UG HP UT

Aggregate Throughput

3000

observed that with the increase in the number of nodes in the network, the throughput increases.

80 60 40 20 0 0

0.2

0.4

0.6 0.8 ARRIVAL RATE

1

1.2

Figure 10: Throughput as a function of delay in the arrival of packets with different number of nodes in network The average throughput is compared with the number of nodes in the network. The delivery ratio of high priority packets is also observed to be better in the proposed scheme, further the throughput is illustrated as a function of delay in arrival rate of packets for varying number of nodes in the networks. The simulation results ascertain that the overall average throughput, delivery of packets in the network implementing the proposed scheme is better than the IEEE MAC 802.11 scheme.

0.4 0.2

REFERENCES

0 0

20

40

60

80

100

Number of Nodes

Figure 9: Comparison of delivery Ratio of High Priority Packets between the proposed Alert Transmission scheme and the IEEE MAC 802.11 Figure 10 shows the throughput as a function of delay in the arrival rate of packets, the number of nodes used here are 20, 40 and 60, 80, 100 and it is UbiCC Journal - Volume 3

[1] Andrew Muir, J.J. Garcia Luna Aceves, “An Efficient Packet Sensing MAC protocol for Wireless Networks”, 1998 [2] Chunhung Richard Lin and Mario Gerla, “Realtime support in multihop wireless networks. Wireless Networks”, 1999 [3] Wei Liu, Yuguang Fang, “Courtesy Piggybacking, “Supporting Differentiated Services in Multi-Hop Mobile Ad Hoc Networks”, April 2004 [4] Xue Yang, Nitin H. Vaidya, “Priority Scheduling in Ad Hoc Networks“, July 2006 (ACM) 46

[5] Sunil Kumar, Vineet Raghavan, Jing Deng, “Medium Access control Protocols for ad hoc wireless networks” A survey”, June 2004 [6] Oleko Odongo, “Dynamic Priority Scheduling with Can MAC protocol”, December 2006 [7] Yu Wang, Brahim Bensaou, “Priority Based Multiple Access for Service Differentiation in MANETS”, July 2005 [8] J.L.Sobrinho and A.S.Krishnakumar, “Real-time traffic over the IEEE 802.11 medium access control layer, Bell Labs Technical Journal, pages 172187, Autumn 1996.

UbiCC Journal - Volume 3

[9] J.L.Sobrinho and A.S.Krishnakumar. Quality-ofService in Ad Hoc Carrier Sense Multiple Access Wireless Networks. IEEE Journal on Selected Areas in Communications, 17(8), August 1999. [10] Tracy Camp, Jeff Boleng and Vanessa Davies.” A Survey of Mobility Models Ad Hoc Network Research”, 10 September 2002

47

A* PRUNE MODIFIED ALGORITHM IN VIDEO COMPRESSION S Verma IIIT, India [email protected] Amit Kant Pandit † SMVDU , India [email protected]† † Corresponding author

ABSTRACT Block matching technique is the most significant tool in motion estimation and compensation in video compression. Block matching is either fixed size block matching (FSBM) techniques or variable size block matching (VSBM). Rate distortion optimization problem is related with it. The R-D optimization, NP hard problem, is solved using Lagrange’s parameter to find a constrained path, where a given PSNR (distortion) and bit rate is achieved. In this paper, we modify and study the A*Prune algorithm used in QoS routing in network ,to solve the R-D optimization problem of video compression .we cast the R-D optimization problem as KMCSP (K multiple constrained shortest path problem). The modification presented in this paper is applied to DVF and DFD both and are constrained simultaneously to find any optional number of constrained shortest paths. . Keywords: A* PRUNE,VIDEO COMPRESSION,QUAD TREE

1

INTRODUCTION

Block matching is widely used method for stereo vision, visual tracking and video compression. At present, most of the techniques used for block matching in video compression are either fixed size block matching (FSBM) or variable size block matching (VSBM) techniques. In FSBM blocks of only one size are used. When a larger block size is used, the number of motion vectors to be encoded or the motion vector field (MVF or DVF) is low. So less number of bits is required for transmission in a channel. However, it results in a higher prediction error or displaced frame difference (DFD) which affects the quality of reconstructed frame. On the other hand, when a smaller block size is used, the DFD is quite low, but more motion vectors need to be encoded resulting in higher transmission rates. There is Rate distortion (R-D) optimization problem associated with video compression The optimal solution to the fundamental problem of splitting coding bits between DVD and DVF is closely related to the size of the block which in turn is dependent on the scene content of video. Variable size block matching (VSBM) provides a better solution of above optimization problem as compared to fixed size block matching (FSBM). The constrained R-D problem is solved using shortest path algorithms like graph search or viterbi algorithm [1]. It is a multiple constraint shortest path problem

UbiCC Journal - Volume 3

(MCSP); universal solution is not possible to arrive at. Solving the R-D using the graph search is shown to be NP- hard [2].Lagrangian bit allocation technique is most popular and widely accepted, for efficient bit allocation at some distortion level. Its popularity is due to its effectiveness and simplicity. It provides an optimized constrained path .The decision is based on minimizing the sum of distortion of block and λ times bits needed to code it, where λ is the Lagrangian parameter. Lagrangian methods have many limitation and problems. Firstly, we do not have any control on individual contribution of DVF and DFD. Secondly, due to presence of temporal and spatial dependencies of the rate -distortion costs, the complexities increases, when applied to block based hybrid video codec such as H.264/AVC or MPEG-1/2/3/4. Thirdly, it cannot adjust speedily, according to variation of different constrains and bit rate requirement. Considering, the bandwidth available for transmission or bit rate required as dynamic parameter, since its value may change at any time. Whenever the dynamic parameter is changed, it is expected to call MCSP (multiple constraints shortest path) procedure each time to find best feasible solution. It is time consuming process. To adjust speedily according to the dynamic parameter, we require K-MCSP (K-multiple constraints shortest path) method. This is speeder since we are selecting a feasible path from multiple precomputed paths. We

48

require a MCSP method which can control contribution of different constraints individually and provide with K paths to choose, according to the variation of dynamic parameter 2.

PROBLEM DEFINATION

The RD optimization problem using Lagrangian technique is NP-hard, and optimal solution is not guaranteed. We convert it to KMCSP (K- multiple constrained shortest paths) problem or NP complete. We search k-shortest paths instead of a single shortest path and use the best one of the pre calculated k-shortest paths to predict optimal solution as per the need or value of dynamic parameter. Consider a network that is represented by a graph G=(V, E), where V is the set of nodes and E is the set of links. Each link (i,j) E is associated with R nonnegative and additive constraints values: Wr (i,j) , where r = 1,2,3,…R. Given a source node, ‘s’ and a target node ‘t’ and R constraints Cr(s,t), where r =1,2,3,…. R. The problem is to find K shortest path from source node s to target node t such that

(2) Here, K multiple shortest paths are found, which satisfies the equation 2. 3. PROPOSED SOLUTION We use an existing k-shortest path algorithm called A* prune algorithm [3], used in QOS routing, as a base algorithm to find the k-shortest paths subject to multiple constraints. We adopt it here for solving DVF-DFD optimization problem and both are constrained simultaneously. A* prune algorithm gives k - multiple constrained shortest paths between a pair of nodes in a digraph in which each is associated with a several Quality of service metrics. It constructs paths starting at the source and going towards the destination. But at each iteration the algorithm gets rid of all paths that are guaranteed to violate the constraints, thereby keeping only those partial paths that have the potential to be turned into feasible paths, from which the optimal paths are drawn. The choice of which path to be extended first and which path can be pruned depend upon a projected path cost function, which is obtained by adding the cost already incurred to get to an intermediate node to an admissible cost to go the

UbiCC Journal - Volume 3

remaining distance to the destination. The Dijkstra’s shortest path algorithm is used to calculate the admissible cost. Though, the A*prune algorithm successfully calculates K constrained shortest paths and gives optimal solutions, it is not viable to use it in its present form in our application for video compression. The problem is due to its computational complexity. Though it uses inadmissible head path pruning and admissible distances, the complexity still increases significantly with the number of nodes. Since our application in DVF-DFD optimization involves large no of nodes (~ 4096), the algorithm takes very huge time in its original formulation. The time also increases if the costs of the admissible distances (predicted) are very low compared to actual costs. To make A*prune algorithm feasible for use in video compression. We propose the following adaptation to the original algorithm: 1.

Since A* prune algorithm stores list of all possible admissible head paths. We limit the number of head paths to be stored to a pre assigned maximum value. Whenever, a new head path is created, if the limit was already reached, then the new head path displaces an existing head path with the maximum cost and takes its place. In this way we limit the size of Path list. 2. The existing algorithm uses a linear function to calculate the projected cost. However the ratedistortion curve between the DVF and the DFD is a decreasing function .It is proposed to use non- linear weight function .Non -linear weight function converges on the solution quickly compared to linear weight function. This reduces the complexities of the algorithm and the added advantage is that it tries to find a solution towards the center of RD curve. This helps in equally distributed (almost in the ratio of constraints) bit allocation between DVF and DFD. We use the non-linear weight function given in [2]. The equation (3) describes the non linear weight function:

(3) Where C(P) gives the path cost for DVF, D(P) gives the path cost for DFD and ∆c and ∆d gives the maximum constraints for DVF and DFD respectively 4. IMPLEMENTATION AND SIMULATION DETAIL The proposed approach was simulated on

49

MATLAB7.0 platform. In the first step we calculate the of Displacement vector field (DVF) and displaced frame difference (DFD) for each of the block sizes 16 x 16, 8 x 8 and 4 x4. The motion estimation is done using exhaustive search approach. The resulting motion vectors were coded using differential pulse code modulation (DPCM) technique. The quantized DFD values are coded using Huffman entropy coding. We calculated the PSNR values for each of the block sizes. We used an adjacency matrix representation to construct the resulting graph structure, DVF and DFD values as the two link metrics for each link. The DVF and DFD values for each of the block sizes are populated in the graph in the order of Hilbert scan. This ensures that the quad-tree structure is maintained in the graph, i.e. when a macro block is divided into four smaller sized blocks, the metrics of the smaller sized blocks are just below that of the larger macro block. Hilbert scan order also ensures that the blocks are scanned in such ways that for each block, both its predecessor and successor share an edge with a block. Once the graph structure is constructed we run the proposed k-multiple constrained shortest path algorithm over the graph. We compute the number of bits required for DFD and DVF for each of the kshortest paths. We also compute the corresponding PSNR values. We select the best of the shortest paths and use it to reconstruct our frame. We used mother and daughter frames for simulation. Each frame is clipped to be of size 256 x 256. We initially predict the second frame from the first frame. Thereafter, each of the subsequent frames will be predicted from the previously reconstructed frame. Table: 1 shows the values of different parameters for different block size of frame-2. Frame 1 is the reference frame. Table 1: DVF-DFD values for frame 2 block size

16

8

4

MVF DFD total PSNR

512 5082 5594 38.467

3944 3749 7693 38.539

16380 2050 18430 38.71

   Now we apply our modified algorithm with following constraints: Maximum list size: 10; K= 5; MVF constraint : 3000; DFD constraint : 4000; Here K refers to the number of shortest paths, and maximum list size is the maximum number of head

UbiCC Journal - Volume 3

paths that can be stored at a time. Table-2 list the various optimized path with different parameters Here no. of nodes is nodes used in resulting quad tree. It is clear from above that path 2 is best with respect to PSNR and constrained bit rate. Out of five optimal paths found with the given constraints. Now the frame-3 is predicted from the reconstructed frame 2 .The frame-3 has following parameter with respect to different block sizes. (Table :3) Table 2: MVF-DFD values for K paths for frame2 K

1

2

3

4

5

No.nodes MVF DFD total PSNR

923 2372 3406 5778 39.56

926 2370 3408 5778 39.57

923 2378 3414 5792 39.55

940 2380 3414 5794 39.56

925 2374 3424 5798 39.56

Table 3: MVF-DFD values for frame 3 16

Block size MVF DFD total PSNR

521 8658 9179 32

8

4

5090 6452 11542 32.06

20022 3118 23140 31.99

Now we calculate the parameters with our algorithm with following constraints Maximum list size = 10; K = 5; MVF constraint = 1000 DFD constraint = 8000; Count = 3232 The resulting paths are as shown in Table :4 Table 4: MVF-DFD values for K paths for frame3 K nonodes MVF DFD total PSNR

1 392 948 7960 8908 32.55

2 392 950 7964 8914 32.52

3 392 950 7972 8922 32.59

4 390 948 7970 8918 32.6

5 392 951 7976 8927 32.53

Other frames are predicted in the same way. The figure-1 shows the rate obtained for different frames at different block levels. Figure -2 shows the five

50

different shortest path quad tree structures obtained. Figure-3shows the stages of reconstruction of frame 2 after adding blocks of different sizes and there DFD, obtained by selecting the best path from different path calculated.

     Figure2: Quad tree structure for five calculated shortest path for frame 2

   Figure 1: comparison of total bits for encoding 5.

CONCLUSION:

Variable size block matching technique was developed based on constrained shortest path algorithm, which gives lower overall bit rates, at the same time satisfying and taking into account both the DVF and the DFD constraints simultaneously. The total allocation of bits was comparable to that of block size 16, which was significantly lower than the rates for other two blocks. Since, to reduce complexities the algorithm is designed sub optimally, and does not guarantee to give best possible solution. Still, depending on the requirement of dynamic parameter, one of the different constrained paths obtained can be selected. 6. REFERENCE

  Figure 3: Stages of reconstruction for frame 2

UbiCC Journal - Volume 3

[1] G.M. Schuster and A.K. Katsaggelos, An optimal quad-tree based motion estimation and motion compensated interpolation scheme for video compression, IEEE Transactions on Image Processing, Vol. 7, No. 11, November 1998 [2] Hans De Neve and Piet Van Mieghem, “A multiple quality of service routing algorithm for PNNI”, Proceedings 1998 IEEE ATM Workshop, May 26-29, Fairfax, VA, USA, pp.324-328, 1998. [3] Gang Liu, K. G. Ramakrishnan, “A*Prune: An Algorithm for Finding K Shortest Paths Subject to Multiple Constraints”, 0-7803-7016-3, IEEE INFOCOM, 2001

51

WIRELESS BODY AREA NETWORK FOR HIP REHABILITATION SYSTEM Mikael Soini, Jussi Nummela, Petri Oksa, Leena Ukkonen and Lauri Sydänheimo Tampere University of Technology, Department of Electronics, Rauma Research Unit [email protected]

ABSTRACT In Wearable Well-Being project PUHVI, HipGuard system for patients recovering from hip surgery was developed. Novel wireless sensors having 3-axis acceleration and 3-axis magnetic sensors are used to measure patient’s hip and leg position and rotation. Furthermore, capacitive insole sensors are used to measure the force between foot and a shoe. This paper concentrates on how these sensors can be interconnected to a central unit that collects and analyzes the measured information. Body Area Network (BAN) utilized in wearable healtcare application have several application-specific challenges such as low-power operation, low latency data transfer, high system reliability and autonomous network operation. This paper thoroughly analyzes how ANT wireless sensor networking technology operates as BAN – the focus is mainly on energy efficiency, communication latency, network size and reliability issues. Because the main focus of this paper is particularly in the operability of ANT networking, these results can be directly utilized in many other wireless sensor networking applications. Keywords: body area networks, healthcare applications, wireless sensor networks.

1

INTRODUCTION

Wireless sensor networks and sensors have several application areas such as forest fire detection, health monitoring, industrial sensing, and home control. Sensor networks are based on physically small sensors exchanging mainly measured information. Sensors usually have very limited power, processing, and memory resources and so interactions between nodes are limited to short distances and low data rates. Advances in electronics have made these wireless sensor networks viable. For example, sensors have become smaller and more precise, and energy efficiency of radio circuits and microcontrollers has been improved considerably. Sensor networks that are composed of wearable or implanted sensors are also known as Body Area Networks (BAN) or Wireless Body Area Networks (WBAN) depending on how sensors are connected with each other. Some BAN application scenarios, related to medical healthcare, personal fitness monitoring and personal audio systems, are presented in [1]. This study is part of the Wearable Well-Being project where HipGuard system was developed for patients who are recovering from hip surgery. The idea behind the system is that on the one hand it is vital to keep hip and leg movements on certain range. On the other hand, it is utmost important to strengthen the muscles sufficiently to enhance rehabilitation. HipGuard system is depicted in Fig. 1.

UbiCC Journal - Volume 3

Figure 1: HipGuard rehabilitation [3].

pants

for

hip

patient

This system monitors patient’s leg and hip position and rotation with embedded wireless sensors having 3-axis accelerometers and 3-axis magnetic sensors. The system also measures the force between foot and a shoe with a capacitive insole sensor [2]. The Central Unit attached to waist collects measured information from sensors and calculates leg and hip

52

position and rotation, and the force directed on foot. Alarm signals can be sent to patient’s Wrist Unit if hip or leg positions or rotations are false. The Central Unit can be attached wirelessly to a mobile phone with Bluetooth. Furthermore, the mobile phone can be used to transfer log, alarm and history information over Internet to enable remote patient monitoring and diagnostic services. Therefore, HipGuard system can provide useful real-time information for patient rehabilitation process. The system architecture and operation is presented thoroughly in [3]. This paper especially concentrates on WBAN issues. There have been several studies that have concentrated on WBANs. MobiHealth [4] implemented a Bluetooth based sensor network for health monitoring and [5, 6] have used UWB (UltraWideband) to build ultra-low-power and low complexity sensors. Lately, IEEE 802.15.4 based approaches have been the most popular research field in this area [7, 8, 9]. Instead of wireless approach, flexible electrically conductive fabrics could be used to implement BAN. Reference [10] presents a wearable monitoring system based on DC power line communication [11]. Because sensors would not require local batteries, the solution would be lightweight and small. Furthermore, Intra Body Communication (IBC) system [12] could be used for sensor networking to obtain low signal attenuation in low frequencies (<1 GHz). In this work, wireless ANT technology is used to interconnect HipGuard system sensors. The focus is especially on ANT’s energy efficiency, low communication latency, network size and reliability. The rest of the paper is organized as follows. Section 2 discusses how BAN sensors can be connected. Section 3 briefly introduces ANT wireless sensor networking technology. Section 4 thoroughly discusses how ANT operates in this kind application. Finally, section 5 concludes the paper. 2

INTERCONNECTING NETWORK SENSORS

BODY

AREA

Sensors can be interconnected to Central Unit either with or without wires. Both of these approaches have their pros and cons. Regardless of chosen method, reliable and low latency data transfer is needed to produce useful and accurate data for hip and leg position and rotation calculations. Wireless approach enables system transferability and flexibility. Sensors can be attached, for example, with straps. Sensors can also be easily replaced if needed. There are challenges related to communication reliability because human body strongly attenuate RF signal and other radio systems can cause interference. Also, wireless sensors should be very low-power and chargeable. Batteries should endure without a recharge at least a week. In wired systems data and power is transferred

UbiCC Journal - Volume 3

with wires, therefore only the Central Unit needs recharging. There are challenges related to durability of wires and connectors embedded to clothing under severe stress, for example in machine wash. Wired systems have poor transferability. Replacement of broken sensors and wires can also be challenging. In this work, wireless approach is chosen because of system transferability and flexibility. The rest of the paper focuses on wireless networking. 3

ANT WIRELESS SENSOR NETWORKING TECHNOLOGY

In this study ANT wireless sensor networking technology is utilized. ANT is an ultra-low power short range low data rate technology that uses GFSK (Gaussian Frequency Shift Keying) modulation and TDMA (Time Division Multiple Access) based communication. Fixed packet sizes (overhead and data) and predefined slots are used for communication reducing the amount of collisions. At the same time, Zigbee sensor networking technology uses different packet sizes. ANT suits especially for repetitive measurements where low latency is required. Table 1 highlights ANT features. [13] Table 1: ANT technology in a nutshell. ANT sensor networking technology features 1

Operating frequency

2,4-2,524GHz: 125 1MHz channels

2

Communication range

up to 10 meters

3

Operating principle

TDMA

4

Modulation

GFSK

5

True data throughput

up to 20 kbps

6

Code space

16kB

7

Network topology

star, tree or mesh networks

8

Network devices

up to 2^32

9

Data packet size

17B (8B payload)

10 Packet types

Broadcast, Burst, Acknowledged

11 Transmission power

0,01 - 1mW (-20dBm to 0dBm)

12 Receiver sensitivity

-80dBm

As presented in Table 1, ANT protocol has three different message types: Acknowledged, Broadcast and Burst. Acknowledged message requires acknowledgements which are not usable in real-time communication where only fresh new data is essential. Broadcast is the simplest ANT message (8 bytes payload) which is sent on dedicated slot on each time frame. Burst is a message that consists of two or more sequential ANT messages (at least 16 bytes). Fig. 2 presents ANT packet structure.

Figure 2: ANT packet structure.

53

ANT enables to implement various different sensor network topologies; in this case, a simple star architecture is used where Central Unit operates as a network master. The star architecture, presented in Fig. 3, is chosen because the amount of network nodes is low and low latency is needed in communication. If needed, Central Unit can also operate as a bridge to external databases and users.

Figure 3: Network architecture for HipGuard system. A channel must be established before ANT nodes can communicate. In the establishment procedure, the network master (in this case Central Unit) chooses channel parameters (network number, RF frequency and channel period) and advertises them by sending packets with chosen period. A slave (in this case Sensor Unit) listen channel traffic and checks for the packets that master is sending. Connection is established after slave has been synchronized to master data packets. Master and slave can be further paired if communication between the devices is continuous. 4

Figure 4: Sensor Unit current consumption with broadcast and burst messages.

ANT OPERABILITY

In this section, the operability of ANT network is studied. Evaluation parameters are sensor energy consumption, system latencies, network size and communication reliability. As a comparison, IEEE802.15.4 based BAN operability has been studied in [14] and [15] as a function of throughput, latency and network size. 4.1

Energy consumption Energy consumption is an important parameter in wireless systems and devices because decent battery life times are needed for usability reasons. Here, Sensor Unit and Central Unit energy efficiency is evaluated. Sensor Unit is a wireless sensor having 3-axis accelerometer and 3-axis magnetic sensors. Central Unit operates as WBAN master collecting data from Sensor Units. In these measurements, the transmission power was set to maximum (1 mW) because it has no significant effect on sensor node total power consumption and it provides better reliability and less retransmission in this challenging environment. Operating voltage was set to 3 V. Fig. 4 and Fig. 5 present the current consumption of a Sensor Unit and Central Unit.

UbiCC Journal - Volume 3

Figure 5: Central Unit current consumption per slave with broadcast and burst messages. Sensor measurement results are 16 bytes in length. This consists of 10-byte accelerometer data and 6-byte magnetic sensor data. Measurement results can be transmitted either with one 16-byte burst packet or with two 8-byte broadcast packets. In this section broadcast and burst packets are compared from energy efficiency perspective. To achieve equal payload data rate broadcast packets must be sent at double rate compared to burst packets; in this case, payload data rate required by the application is 256 bytes per second that is 16 messages per second × 16 bytes (burst) or 32 messages per second × 8 bytes (broadcast). In Sensor Unit case (see Fig. 4), sending one burst packet consumes 1.6 % more current compared to two broadcast packets, when data rate is 256 bytes per second. The difference is negligible. In Central Unit case (see Fig. 5), using two broadcast packets increase Central Unit’s current consumption about 18 % compared to one burst packet, when data rate is 256 bytes per second. This

54

is for case where Central Unit has one slave; having multiple slaves (n) will increase current consumption n times. In the simplest case, Central Unit has three sensors that are attached to thigh, shin and metatarsus. In CSMA (Carrier Sense Multiple Access) based sensor networking, the receiver current consumption is usually dominant because receiver must be active practically all the time if low latency is needed. However, TDMA based technique, used in ANT, enables low power receiver operation because predefined slots are used and reception of one ANT packet takes less than 1ms. Measurement data transmission frequency has the most significant effect on current consumption. Lower data transmission frequency would enable longer battery lifetimes but it would degrade the application operability because of longer latencies. The longer latency would decrease the accuracy of position, rotation and force calculations. In this work it was estimated that, at least, data rate of 256 bytes per second is needed for this application. 4.2

Communication latencies Real-time operation is vital in this type of application where user adjusts his or her behaviour according to measurements. Next, ANT based system start-up and data transmission latencies are studied. 4.2.1 Start-up latency Start-up latency is the time from sensor wake-up to completed synchronized connection. If sensors are active, they will normally stay synchronized and this start-up phase can be omitted. Start-up phase is needed when sensor is started up due to initial setup, reconfiguration, battery reload or if sensor is resynchronized to network. Table 2 presents the measurement results where synchronization latency is studied in a function of message rate. Transmitter is the master node sending synchronization messages and receiver is the sensor node in synchronization mode. Results show that there is a compromise between start-up latency and energy consumption. Table 2: Sensor start-up latency in ANT. Transmitter (master)

Receiver (slave)

Message rate

Synchronization time

1

8 messages/s

1490 ms (avg)

2

16 messages/s

630 ms (avg)

3

32 messages/s

270 ms (avg)

4

64 messages/s

80 ms (avg)

UbiCC Journal - Volume 3

4.2.2 Data transmission latency In addition to start-up latency, there is data transmission latency. This is the time where data is transmitted from Sensor Unit to Central Unit when the receiver and the transmitter are in active mode that is they are synchronized. The durations of different phases related to transmission and reception of 8-byte ANT message were measured with an oscilloscope. Results are shown in Fig. 6.

Figure 6: ANT packet transmission and reception. The data transmission phases and their durations are presented in Table 3. It can be seen that the transmission of one message lasts for 19 ms. Table 3: Data transmission latency in ANT. Different phases in data transmission

Duration

1

Packet formation in μC, transmission to radio circuit

6 ms

2

Packet handling at the transmitter

4 ms

3

Packet transmission over the air

1 ms

4

Packet handling at the receiver, transmission to μC

8 ms

Total time

19ms

4.3

Network size The used NRF24AP1 radio circuit can handle about 200 eight byte ANT packets per second. In this work the measurement data was 16 bytes in length and therefore one burst or two broadcast packets are required for transmitting one measured value from Sensor Unit to Central Unit. Thus Central Unit can handle maximum of 100 measurements per second. As mentioned above, the measurement data transmission frequency needs to be at least 16 Hz. Therefore, the maximum number of Sensor Units in this ANT based WBAN is 6. Lower data transmission frequency would enable more network nodes but it could degrade the application operability. 4.4

Data transfer reliability Data transfer reliability is important parameter in ANT operation. Only fresh new data is essential in this type of system, thus retransmissions are not used. Measurement results considering ANT data delivery reliability in unobstructed path are presented in Fig. 7. Transmission power was set to 0.01 mW. These results are used as reference for cases where Bluetooth and human body interference in ANT is studied.

55

Table 4: Bluetooth interference in ANT. 1000 packets are transmitted between ANT devices Test

Figure 7: ANT communication reliability in unobstructed path. From the reference measurements, it can be seen that reliable ANT communication range is over 5 meters even with the lowest possible transmission power (0.01 mW) in unobstructed open air propagation environment. However, Bluetooth and human body are potential sources of interference in ANT network operation which are taken into consideration. 4.4.1 Bluetooth interference Bluetooth interference in ANT network operation is important to study because data transfer from Central Unit to a mobile phone was implemented with Bluetooth. ANT and Bluetooth are operating at the same 2.4 GHz ISM (Industrial, Scientific and Medical) band. Bluetooth utilizes FHSS (Frequency Hopping Spread Spectrum) technique using 79 1 MHz bandwidth channels, whereas ANT uses single dedicated 1 MHz channel. Fig. 8 shows the measurement setup for evaluation. Bluetooth and ANT transmission power were set to 1 mW.

Description

Received

1

Bluetooth (BT) OFF at position A

99,80 %

2

Bluetooth (BT) ON at position A

99,80 %

3

BT ON at position B, BT data transfer is ON

97,30 %

4

BT ON at position A, BT data transfer is ON

87,40 %

It can be seen that when Bluetooth device is transmitting inside the ANT network some packet loss is experienced. Because Bluetooth uses frequency hopping technique these losses are tolerable. Also, Bluetooth data transfer is ON only for a short period of time and it was seen that active Bluetooth device without data transfer do not affect ANT communication. Furthermore, Bluetooth can avoid crowded frequencies by using AFH (Adaptive Frequency-hopping spread spectrum) defined in Bluetooth specification v1.2. If IEEE802.11x would be used, ANT should be configured to operate on different channel than IEEE802.11x to enable communication [16]. 4.4.2 Human body interference Human body causes large signal attenuation which has a remarkable effect on wireless communication reliability [17]. This causes challenges for sensor node positioning. Electromagnetic channel model for human body could be used to help sensor positioning [18]. In this study, human body interference was evaluated by strapping transmitting Sensor Units to seven different positions, presented in Fig. 9. The Central Unit receiving measurement data was attached to test person’s waist. The transmission power was set to 1 mW. Measurements were performed outside to prevent radio wave reflections from environment.

Figure 8: Bluetooth interference measurement setup. The results considering the effect of Bluetooth on ANT communication reliability are shown in Table 4. Figure 9: Human body interference measurement setup and different sensor positions.

UbiCC Journal - Volume 3

56

In these measurements packets were sent from Sensor Units to Central Unit. Measurement results, presented in Table 5, indicate how human body interfere ANT communication. Table 5: Human body interference in ANT. 1000 packets are transmitted between ANT devices Test Sensor location

Received

1

Outer thigh

80,20 %

2

Front thigh

90,60 %

3

Outer shin

45,00 %

4

Front shin

97,80 %

5

On top of metatarsus

99,30 %

6

Inner metatarsus

97,50 %

7

Outer metatarsus

98,90 %

From the result it can be seen that the ANT network reliability is highly dependent on sensor position. When comparing test cases 3 and 4 which have equal transmitter receiver separation, it can be seen that line of sight (LOS) improves communication reliability considerably. 5

CONCLUSIONS

This paper concentrated on the utilization of wireless ANT sensor network to HipGuard system. The focus was on networking issues. This paper analyzed ANT protocol features and operation through extensive practical measurements. It was shown that low power, low latency, small size and reliable ANT based WBAN can be realized. With 1 mA power consumption, it is possible to implement sensors operating for several days even with small batteries such as Li-ion coin battery (220 mAh). Burst packets can be used to enhance energy efficiency of Central unit. Transmission latency is very short and network synchronization latency is tolerable. HipGuard system requires data rate of 256 bytes per second for measurement result updates to obtain accurate data for determining hip and leg position and rotation, and force directed on foot. This causes limitations to network size. To implement highly reliable ANT based WBAN, several aspects should be taken into consideration. LOS path between receiver and transmitter antennas is recommendable. Bluetooth, IEEE802.11x and other 2.4 GHz radio systems cause interference in ANT network operation. Therefore, if possible, ANT should be configured on a different RF channel. Transmission power does not affect considerably to power consumption, therefore it should be set to a maximum to improve communication reliability. The focus of this paper was particularly in ANT networking operability. Therefore, these results can be directly utilized in many other wireless sensor networking applications.

UbiCC Journal - Volume 3

6

REFERENCES

[1] S. Drude: Requirements and Application Scenarios for Body Area Networks, Proc. 16th IST Mobile and Wireless Communications Summit, Budapest, Hungary (2007). [2] T. Salpavaara, J. Verho and J. Lekkala: Capacitive insole sensor for hip surgery rehabilitation, Proc. 2nd Int. Conf. on Pervasive Computing Technologies for Healthcare, Tampere, Finland, pp. 311-314 (2008). [3] P. Iso-Ketola, T. Karinsalo, and J. Vanhala: HipGuard: A wearable measurement system for patients recovering from a hip operation, Proc. 2nd Int. Conf. on Pervasive Computing Technologies for Healthcare, pp. 196-199 (2008). [4] D. Konstantas, A. Van Halteren, R. Bults, K. Wac, V. Jones, and I. Widya: MobiHealth: ambulant patient monitoring over public wireless networks, Proc. Mediterranean Conf. on Medical and Biological Engineering, Naples, Italy (2004). [5] B. Gyselinckx, C. Van Hoof, J. Ryckaert, R.F. Yazicioglu, P. Fiorini, and V. Leonov: Human++: Autonomous Wireless Sensors for Body Area Networks, Proc. 27th Conf. on Custom Integrated Circuits, San Jose, CA, USA, pp. 13-19 (2005). [6] T. Zasowski, F. Althaus, M. Stäger, A. Wittneben, and G. Tröster: UWB for noninvasive wireless body area networks: Channel measurements and results, Proc. IEEE Ultra Wideband System Technology Conf., Reston, VA, pp. 285-289 (2003). [7] B. P. L. Lo, S. Thiemjarus, R. King, and G. Z. Yang: Body sensor network-A wireless sensor platform for pervasive healthcare monitoring, Proc. 3rd Int. Conf. on Pervasive Computing, London, UK (2005). [8] B. Zhen, H. B. Li, and R. Kohno: IEEE Body Area Networks for Medical Applications, Proc. 4th Int. Symp. on Wireless Communication Systems, pp. 327-331 (2007). [9] E. Wade and H.H. Asada: Wearable DC Powerline Communication Network Using Conductive Fabrics, Proc. IEEE Int. Conf. on Robotics and Automation, Vol. 4, New Orleans, LA, USA, pp. 4085-4090 (2004). [10] E. Wade and H.H. Asada: Broadcasting Modem Hardware Design Using DC Power-Line Communication, IEEE/ASME Transaction on Mechatronics, Vol. 11, No. 5, pp. 533-540 (2006). [11] J. A. Ruiz, J. Xu, and S. Shimamoto: Propagation Characteristics of Intra-body Communications for Body Area Networks, Proc. IEEE Consumer Communications and Networking Conference, Las Vegas, USA, pp. 509-513 (2006).

57

[12] Dynastream Innovations Inc., Cochrane, Alberta, Canada, ANT Message Protocol and Usage (ver 2.12). Available: http://www.thisisant.com (2008) . [13] D. Domenicali, and M. G. Di Benedetto: Performance Analysis for a Body Area Network composed of IEEE 802.15.4a devices, Proc. 4th Workshop on Positioning, Navigation and Communication, pp. 273-276 (2007). [14] M. Sukor, S. H. S. Ariffin, N. Fisal, S. K. S Yusof, and A. Abdallah: Performance Study of Wireless Body Area Network in Medical Environment, Proc. IEEE Asia Int. Conf. on Modelling and Simulation, Kuala Lumpur, Malaysia, pp. 202-206 (2008). [15] E. Monton, J. F. Hernandez, J. M. Blasco, T. Herve, J. Micallef, I. Grech, A. Brincat, and V. Traver: Body area network for wireless

UbiCC Journal - Volume 3

patient monitoring, IET Communications Journal, Vol. 2, No. 2, pp. 215-222 (2008). [16] L. Sydanheimo, M. Keskilammi, and M. Kivikoski: Performance issues on the wireless 2.4 GHz ISM band in a multisystem environment, IEEE Transactions on Consumer Electronics, Vol. 48, No. 3, pp. 638-643 (2002). [17] S. L. Cotton, and W. G. Scanlon: A Statistical Analysis of Indoor Multipath Fading for a Narrowband Wireless Body Area Network, Proc. IEEE 17th Int. Symp. on Personal, Indoor and Mobile Radio Communications (2006). [18] A. Gupta, and T. D. Abhayapala: Body Area Networks: Radio channel modelling and propagation characteristics, Proc. Australian Communications Theory Workshop, pp. 58-63 (2008).

58