Le Gruenwald', Matilde Montealegre², Chuo N. Lau' 'University of Oklahoma, School of Computer Science, Norman,

OK 73019, ggruenwald@ou.edu 'Universidad Surcolombiana, matildemm@usco.edu.co

Key worils

Mobíle computing, real-time database, transaction management, ad-hoc netwroks

Abstract

A Mobile Ad-hoc NetWork (MANET) is an autonomous system of mobile hosts (MHs) with similar transmission power and computation capabilities that communicate over relatively bandwidth constrained wireless links. Applications sucli as emergency/rescue operations, conferences/meetings/lectures, disaster relief efforts, bluetooth (Personal Area Network) and military networks can be conceived as applications of MANET due to the fact that they cannot rely on centralized and organized connectivity. In these environment transactions are time-critical and require to be executed not only correctly but also within their deadlines, that is, the user that submit a transaction would like it to be completed before a certain time in the future. This study focuses on the comparison of four scheduling techniques based on the policy of assigning priorities to transactions on the system. The techniques are: First Come First Serve (FCFS) [1,2], Earliest Deadline (ED) [1,2,5], Least Slack (LS) [1,2,8] and Least Slack Mobile (LSM) proposed in [3] where some modifications to the Least Slack Technique with respect to energy constraints, disconnection and transaction type (firm/soft) are considered. Applying these modifications to Earliest Deadline, the performance of the system will be evaluated to measure the percentage of transaction missing deadlines and the total energy consumption in the mobile hosts. The performance evaluation of the techniques will be carried out by means of simulation. The simulation model is implemented using Visual Slam/Awesim [7].

Key words

Computación móvil, bases de datos en tiempo real, manejo de transecciones y redes ad hoc

RESUMEN

Una red Mobile Ad-hoc (MANET) es un sistema autónomo de servidores mobiles (MHs) con capacidades computacionales similares que se comunican entre si a través de una red wireless. Se consideran como aplicaciones MANET las operaciones de emergencia/rescate, conferencias/reuniones/clases magistrales, ayuda en caso de desastres, bluetooth (Personal Area Network) y redes militares, debido a que estos sistemas no pueden contar con una conexión centralizada y directa de los diferentes servidores que interactúan en el proceso. En este tipo de redes las transacciones son dependientes directamente del tiempo y requieren ser ejecutadas antes que expire el tiempo asignado para su ejecución, por lo tanto, el usuario que requiere la ejecución de una transacción espera que esta sea completada antes de un cierto tiempo en el futuro.

Este estudio se centra en la comparación de cuatro técnicas de programación de tareas (scheduling techniques) basadas en la política de asignación de las mismas de acuerdo con las prioridades que tengan dentro del sistema. Estas técnicas son: First Come First Serve (FCFS) [1,2], Earliest Deadline (ED) [1,2,5], Least Slack (LS) [1,2,8| and Least Slack Mobile (LSM) propuestas en [3], en donde se citan estas técnicas como trabajo futuro de la Investigación realizada por Mr. Banik Shankar, "Energy-Efficient Transaction Management for Real-Time Mobile Databases in Ad-hoc Network Environments" el cual fue presentado como trabajo de grado para optar el titulo de Master of Science en la Universidad de Oklahoma. Por tanto, esta investigación es continuación del trabajo hecho por Mr. Shankar. Aqui se presentan algunas modificaciones a la técnica de Least Slack con respecto a las limitaciones de energía, desconexiones y tipo de transacciones (firm/soft). Tales modificaciones son aplicadas también a la técnica de Earliest Deadline para evaluar el comportamiento del sistema y medir el porcentaje de transacciones que no alcanzan a ser ejecutados dentro del tiempo límite y para medir la cantidad de energía consumida por los servidores mobiles.

La evaluación del sistema se realizó usando simulación. El modelo de simulación es implementado usando Visual Slam/Awesim [7],

INTRODUCTION

In a Mobile Ad-hoc Network (MANET) there is no static infrastructure such as base stations. In an ad hoc network each node acts as a potential router, routing packets for two communicating nodes that may not be radio contad with each other. If two hosts are not within radio range, all message communication between them must pass through one or more intermedíate hosts. Thus communication may be via múltiple wireless hops. The hosts are free to move around randomly, thus changing the network topology dynamically. Applications such as emergency/rescue operations, conferences/meetings/lectures, disaster relief efforts, bluetooth (Personal Area Network) and military networks can be

store the corresponding ID of the LMH for each local schema. This Global Schema ¡s required to ¡dentify which data object ¡s stcredin which LMH.

In our environment, a global transaction is defined as a transaction, which requires data items from different sites. The part of a global transaction, which is executed in a particular site, is defined as a sub-transaction. It is assumed that for a particular global transaction there will be one sub-transaction for one site.

The SMH will initiate a global transaction and submit it to an LMH. This LMH will act as a coordinator for this global transaction. Then the LMH coordinator will check the global schema to find which data item is stored at which LMH and will divide the global transaction into sub-transactions. These LMHs are the participant sites for the global transaction. The LMH coordinator will submit the sub-transactions of the global transaction to the respective LMH participants. Then, the LMH coordinator with the help of the LMH participants will commit/abort the global transaction and will return the result to therequestingSMH.

In order to provide a balance of energy consumption among MHs and to reduce the number of transactions that must be aborted due to miss their deadlines the SMH must submit their finn transactions to the nearest LMH and their soít transactions to the LMH with the highest energy available. Here, we are sacrificing the first deadlines of soft transactions in favor of balancing the energy consumption because soft transactions canstill be executed aftertheirfirst deadlines liave expire [3].

A LMH can receive two types of transactions: global transactions from an SMH or sub-transactions from other LMHs (called Participant sites). Each LMH has three parts:

Transaction Scheduler (TS): schedules all global transactions and sub-transactions.

£ Transaction Coordinator (TC): divides the global transaction into sub-transactions and submits them to corresponding LMHs, and returns the results to the requestiny MH.

. Transaction Manager (TM): manages the execution of sub-transactions.

The TS at LMH will use one of the real-time energy-efficient dynamic scheduling algorithms described in section 4 to schedule transactions. Transactions will be organized in a queue that reflects its priorities.

SCHEDULING TECHIMIQUES

When a LMH receives a transaction from a SMHs or other LMHs, it has to assign priorities among transactions in order to schedule them. In our environment the scheduling algorithm has to consider not only transaction types (firm and soft), transaction deadlines, but also the energy limitations of the

MHs. In order to handle the above considerations the following algorithm will be used:

Beyin

Calcúlate the deadline/slack time for all transactions using Equation 1,2 or 3.

Sort all the transactions according to their deadlines/slack times.

Assign higher priorities to transactions with shorter deadlines/slack times.

If two firm transactions or two soft transactions have the same deadline/slacktime

Then give priority to the one whose requesting MHs have less energy.

If two transactions have equal energy Then give priority to the one that arrives first End if Endif

If the deadline/slack time of a firm transaction is equal to the

deadline/slack time of a soft transaction

Then give a higher priority to the firm transaction.

End if End

In our environment when a transaction arrives to the system,

Lhefollowing Information will be known:

Release time: It is the earliest time the transaction can be

started and is usually the arrival time (AT) of the transaction.

•S Deadline |D): Itis the desired máximum committime.

SS Runtime Estímate (RE): It approximates the duration of the transaction on an unloaded system. It takes into account boththe CPU and diskaccess times.

^FM Slack Factor (SF): Itis a constant valué that determines the tightness/slackness of deadlines.

K- Slack Time (S): It is the máximum amount of time that a transaction can spend without executing and still complete within its deadline.

First Come First Serve Technique (FCFS)

As described in [1], This policy assigns the highest priority to the transaction wi1h the earliest release time. If release times equal arrival times then we have the tradltíonal versión of FCFS. The primary weakness of FCFS is that it does not make use of deadline information. FCFS will discrimínate against a newly arrived task with an urgent deadline in favor of an older task that may not have such an urgent deadline.

Earliest Deadline (ED)

As described in [1], The transaction with the earliest deadline has the highest priority. A major weakness of this policy is that it

Least Slack (LS)

This technique is based in equation (2) [1,2,8]. In the LS technique, transactions with less slack time are scheduled before transactions with more slack time. Figure 2 explains the principie of equations 1 and 2.

D = AT + RE* SF (I)

S - D-(AT + RE) (2)

AT+RE

_ RE

equation for% Missed deadline is as follows:

. #of transactions missed dealine #of transactions processed

% Missed deadline = 100¹

The energy consumption for a resource is obtained by multiplying the power of the resource with the length of the time the resource was in the active/doze mode to process transactions.

Energy consumption of a resource = (Power of the resource in the active mode) * (The time the resource was in the active mode) + (Power of the resource in the doze mode)* (The time the resource was in the doze mode)

(5)

Simulation Parameters

The environment of the simulation is assumed to be a closed área of 10001000 units in which the initial positions (coordinate

where D¹ is the deadline, 'AT' is the current time (currenttime is equal to arrival time since the slack time is calculated when transaction arrives to the system), RE' is the runtime estímate, Pd¹ is the probability of disconnection during execution and ’Td' is the average time loss due to disconnection.

SIMULATION MODEL AND RESULTS

Description of the simulation model

The simulation model is implemented using Visual Slam/Awesim [7], Global transactions are defined as entities in the simulation model. The attributes associated with each transaction are Transaction Creation Time, Transaction ID, Number of site transactions, Number of operations per site transactions, Runtime Estímate, Deadline, slack time, Transaction Type (firm or soft) and ID of the SMH which initiates thetransaction.

The mobile hosts are defined as resources in the simulation model. The attributes associated with each resource are Resource ID, Positíon which consists of X coordinate and Y

Experiments

In this section, we describe different sets of experiments and analyze their results to evalúate the performance of our techniques. For each set of experiments, we run the simulation with Inter Arrival Time of 100 ms and slack factor of 10. These valúes were chosen because the experiments of varying the Inter Arrival Time on percentage Missing Deadlines for All Firm and Soft Transactions (see Figures 16,17} show the best results. Each run continúes until a total of 1000 transactions are completed in the system.

The impact of disconnection was evaluated by using the technique proposed in [3], Figure 3, shows that the percentage of transaction missing deadline increases with the probability of disconnection for All Firm and Soft Transactions. In order to implement equation 3 to run for LSM technique, an average valué for probability of disconnection of 0.4 was assumed for a periodof5seconds [13].

% Missed Deadline (Varying the InterArrival Time)

O    0.2 0.4 0.6 Probability of Disconection 0.8

- All Firm

Figure 3. Varying the Probability of Disconnection on % Missed Deadline Jor All Firm and Soft Transactions

Algorithm FCFS misses a greater number of deadlines for all the runs. This technique is included in this study for comparison with scheduling techniques that gives higher priority to transactions with least deadline/slack time. It can be observed from all the experiments that these techniques perform better because they allow transactions with more urgent deadline/slack time to preempt transactions with less urgent deadline/slack times.

Varying the IMumber of LMHs

In this experiment, we have varied the number of LMHs for Firm and Soft transactions. From Figure 4 and 5, we can observe that the percentage of transactions missing deadline decreases as the number of LMHs increases for all scheduling techniques. The LMHs in our environment are servers; then with more servers available the transactions will spend less time to be processed, henee fewer transactions missing its deadlines. For all Soft transactions, the percentage of transactions missing deadline is lower than for Firm transactions. This is due to the fact that soft transactions are aborted when they miss its second deadline, which is twice of their first deadline. Earliest Deadline performs better than the two Least Slack techniques because as shown in Figure 16 and 17 this technique performs better at lower load of the system. Here we are running for Inter Arrival time of 100 ms which is the lower load of the system.

The results can also be explained by analyzing the equations 2 and 3 to determine the priority, or slack time. We can notice that with LS priority assignment there is no correlation between the Arrival Time of the transactions and their slack time. By the contrary, with Earliest Deadline there is a direct correlation. Thus, a transaction T, that arrives much later than a transaction T, is more likely to have a deadline that is greater than the one for T, Then it is less likely that transaction T₂ will preempt transaction T,. These can be clear by the following example. Transaction T, arrives at time 10, has a slack time of 5 and a deadline of 20. Transaction T₂ arrives a time 20, has a slack time of 4 and a deadline of 28. If we used LS to schedule the transactions then T, will preempt transaction T, since it has least slack time. However, if we used ED, transaction T₂ will not preempt T, since its deadline is higher.

LMH and SMH Moving with Same Speed in Random Directions

Speed

_4-All Soft FCFS    -All Soft ED

.    -All Soft LS    --•--All Soft LSS

Future research can also test the techniques examined here after implementing the Sleep mode of mobile hosts ¡n the system.

REFEREINICES

1. Abbott R., H. Garcia-Molina, "Scheduling Real-Time Transactions: A Performance Evaluation". ACM Transactions on Database Systems, Volumen 17, No 3, September 1992, Pages 513-560.

11.    Ko, Y., N. Vaidya, "Location-Aided Routing (LAR) in Mobile Ad-Hoc Networks", M0BIC0M 1998, Pages 66-75.

12.    Gruenwald L, Shankar M. Banik, Chuo Ning Lau, Matilde Montealegre. Managing Real-Time Database Transactions in Mobile Ad-Hoc Networks. This is a paper submitted for publication. Chuo Ning Lau and Matilde Montealegre contributed with the implementation of the speed at which the mobile hosts move. A special study at the University of Oklahoma, summer 2001.