Informatica 36 (2012) 167-176 167
A Market Based Approach for Sensor Resource Allocation in the Grid
Li Chunlin, Huang Jin Hui and Li LaYuan
Department of Computer Science, Wuhan University of Technology, Wuhan 430063, P.R.China E-mail: chunlin74@yahoo.com.cn, jwtu@public.wh.hb.cn
Keywords: sensor, grid computing, market
Received: August 5, 2011
The paper studies a market based approach for sensor resources allocation in sensor enabled grid computing environment. The paper presents an efficient mechanism to assign sensor resources to appropriate sensor grid users on the basis of negotiation results among participants. We model the sensor allocation problem by introducing the sensor utility function. The goal is to find a sensor resource allocation that maximizes the total profit. The paper proposes a distributed optimal sensor resource allocation algorithm. The performance evaluation of proposed algorithm is evaluated and compared with other resource allocation algorithm for sensor grid.
Povzetek: Predstavljena ja postavitev senzorjev v omrežje na osnovi pogajanj med udeleženci.
1 Introduction
Grid computing is based on the concept of the coordinated sharing of distributed and heterogeneous resources to solve large-scale problems in dynamic virtual organizations. The grid computing paradigm can be extended to include the sharing of sensor resources in sensor networks. Integrating sensor networks and grid computing in sensor-grid computing is like giving 'eyes' and 'ears' to the computational grid. Real-time information about phenomena in the physical world can be processed, modeled, correlated and mined to permit on-the-fly decisions and actions to be taken on a large scale [1, 16]. Sensor grids extend the grid computing paradigm to the sharing of sensor resources in wireless sensor networks. By combining the complementary strengths of sensor networks and grid computing, sensor grids can support applications that require real-time information from the physical environment and vast amount of computational and storage resources. Examples include environment monitoring with prediction and early warning of natural disasters, and missile detection, tracking and interception [3].
However, sensor enabled grid is a widespread distributed system and maybe consists of many sensors belonging to individual user who does not know with other users at all. They would like to do the things that benefit themselves most, which means they are rational and selfish. Therefore, sensor grid needs to provide incentives to encourage every user to contribute their resources to other users. Sensor grids being a relatively new area of research, there are many issues left unaddressed regarding their design. One of the major challenges in the design of sensor enabled grid is how to efficiently schedule sensor resource to user jobs across the collection of sensor resources. Due to the energy limitation and also to prolong the lifetime of the sensor
grid, conservation of energy consumed is an important consideration in managing sensor grids. Making decisions on how best to utilize limited sensor resources in order to satisfy grid users' demands without conflict and without wasting resources is the key issue in sensor grid. The resource allocation in grid computing systems has been extensively studied in the past. There are some important differences between sensor resource and computational resource. Thus, existing allocation algorithms for traditional grid environment may not work well in sensor enabled grids.
In this paper, we present a market based approach for sensor resources allocation in sensor enabled grid computing environment. Since sensor users' tasks might compete for the exclusive usage of the same sensing resource we need to allocate individual sensors to sensor users' tasks. Sensor grid tasks are usually characterized by an uncertain demand for sensing resource capabilities. We model this allocation problem by introducing the sensor utility function. The goal is to find a sensor resource allocation that maximizes the total profit. The paper proposes a distributed optimal sensor resource allocation algorithm. The performance evaluation of proposed algorithm is evaluated and compared with other resource allocation algorithm in sensor grid. The paper also gives the application example of proposed approach.
The rest of the paper is structured as followings. Section 2 discusses the related works. Section 3 presents a market based approach for sensor resource allocation in the grid. Section 4 describes sensor resources allocation algorithm. In section 5 the experiments are conducted and discussed. Section 6 gives the conclusions to the paper.
168 Informática 36 (2012) 167-176
L. Chunlin et al.
2 Related Works
There are certain researches aiming to combining grid environments with wireless sensor network [1~17], which incorporate sensors into the existing grid systems as the consumers of grid resources and provide sensor services to other grid nodes. Peter Komisarczuk et al. [1] discusses research direction in an Internet sensor grid for malicious behavior detection, analysis and countermeasures. They outline some experiences with these sensors and analyzing network telescope data through Grid computing as part of an "intelligence layer" within the Internet. M. Pallikonda Rajasekaran et al. [2] propose a wireless sensor grid architecture for monitoring the health status of different groups of patients to provide a platform for physicians and researchers to share information with distributed database and computational resources to facilitate analysis, diagnosis, prognosis and drug delivery. Hock Beng Lim et al. [3] design an integrated and flexible scheduler for a sensor grid testbed based on the SPRING framework. Several scheduling and load balancing algorithms were implemented within this scheduler to suit the unique characteristics of sensor jobs. The scheduler can use an appropriate scheduling or load balancing algorithm to suit the requirements of the resource owner and users. Nikolaos Preve et al. [4] proposed the sensor grid enhancement data management system, called SEGEDMA ensuring the integration of different network technologies and the continuous data access to system users. The main contribution is to achieve the interoperability of both technologies through a novel network architecture. Huang-Chen Lee et al. [5] discuss the considerations of designing a low-cost WSN-based rain gauge grid, which provides high resolution mapping of precipitation. Preliminary experimental results are presented. Fox, G. et al. [6] propose a collaborative sensor grid framework to support the integration of a sensor grid with collaboration and other grids. The framework includes a grid builder tool for discovering and managing grid services and remote, distributed sensors. It provides a real-time collaborative client to enable distributed stakeholders to have a consistent view of displayed sensor streams. They illustrate the versatility of the framework by constructing a robot based customizable application for shared situational awareness. Hock Beng Lim et al. [7] aim to build a large-scale sensor grid infrastructure that can seamlessly integrate heterogeneous sensor resources from different projects distributed across a wide geographical area. Sanabria, J. et al. [8] discussed a deployment framework, which leverages on existing grid computing technologies to provide middleware that integrates wireless sensor networks and grid infrastructures. They demonstrated the work on enabling a sensor grid infrastructure for acoustic surveillance applications. Hock Beng Lim et al. [9] developed a sensor grid architecture framework, called the Scalable Proxy-based aRchItecture for seNsor Grid (SPRING). They designed the National Weather Sensor Grid (NWSG), a large-scale cyber-sensor infrastructure for
environmental monitoring. The NWSG integrates mini weather stations deployed geographically across Singapore for weather data collection, processing and management. Toshihiro Matsui et al. [10] deal with distributed resource allocation problem for distributed sensor networks. Distributed optimization algorithm is used to understand the problems and to design the cooperative protocols. A distributed cooperative observation system using agency model has been developed. Yan YuJie et al. [11] described the architecture of wireless sensor grid, also designed a connecting platform named MPAS. The advantage of MPAS is that it is based on Web service resource framework, with the ability of integrating multiple sensor networks with grid; also it can actuate sensor network and support interoperability among multiple sensor networks. Mohammad Mehedi Hassan et al. [12] discuss one of the most important issues in Sensor-Grid, i.e., to develop a fast and flexible content-based publish/subscribe information dissemination (CBPSID) system for automatic fusion, interpretation, sharing and delivery of huge sensor data to consumers as the entire Sensor-Grid environment is very dynamic.
Se-Jin Oh et al. [13] present the design and implementation a u-Healthcare SensorGrid gateway to connect transparently a sensor network and a Grid network for providing convenient and speedy u-Healthcare services to users. They implement a mobile monitoring system for monitoring patient's status by using a mobile device such as PDA. Xiaolin Li et al. [14] propose an autonomic management framework (ASGrid) to address the requirements of emerging large-scale applications in hybrid grid and sensor network systems. They proposed the autonomic sensor grid system concept in a holistic manner targeted at non-trivial large applications. Toshihiro Matsui et al. [15] propose a model of distributed resource allocation problem for distributed sensor networks. Several models based on constraint network and another model based on concept of agency, are compared. The constraint network formalization which are similar to resource allocation problem of agency model, is shown. Yong-Kang Ji et al. [17] discuss the selfish problems of Sensor Web and resolve them using specific designed mechanism, and describe several scenarios of the applications in Sensor Web. The works [18~22] mainly deal with resource allocation, QoS optimization in the computational grid and don't consider exploiting services of sensor to support sensor enabled grid. The differences between paper [20] [21] and this paper are that this paper deals with optimal sensor resources allocation, paper [20] considers two level market solution for optimal resource scheduling in computational grid; paper [21] considers multiple QoS optimization in computational grid. Computational grid is different from sensor grid. In sensor grid environment, sensor nodes have present severe limitations in terms of processing, memory capabilities and energy, but computational grid doesn't have energy problem, and also have enough processing, memory capabilities. Considering all these limitations of sensor nodes, it is important for the sensor grid system to
A MARKET BASED APPROACH FOR.
Informatica 36 (2012) 167-176 169
manage energy consumption without compromising system's performance. Our proposed optimization in sensor grid considers energy consumption in the sensor node. The objective of the paper is to maximize the utility of the system without exceeding the total energy available, the expense budget, and deadline.
3 A Market based Approach for Sensor Resource Allocation in the Grid
3.1 System Model
The paper formulates optimal sensor resources allocation in sensor enabled grid computing environment by adopting computational economy framework. The proposed model consists of two types of agents: the sensor resource agents that represent the economic interests of the underlying sensor resources providers of the sensor grid, the sensor user agents that represent the interests of grid user using the grid to achieve goals. Interactions between the two agent types are mediated by means of market mechanisms. Market mechanism in economics is based on distributed self-determination, the variation of price reflects the supply and demand of resources, and market theory in economics provides precise depiction for efficiency of resource scheduling. Sensor user agents are allowed to specify their requirements and preference parameters by a utility model. As a result, a market based sensor grid model inherently supports sensor users with diverse requirements for the execution of their sensor jobs. The utility values are calculated by the supplied utility function that can be formulated with the sensor job parameters. The request is analyzed by the scheduler of grid market. Whenever a new sensor user agent is created, it is first given an endowment of electronic cash to spend to complete its sensor job. A sensor job can be characterized by deadline, budget, and sensor task requirements. The sensor grid market mechanism allows multiple sensor resource agents and sensor user agents to negotiate simultaneously, it uses price-directed approach to allocate appropriate sensor resources. In this price-directed approach, an initial set of prices is announced to the sensor user agent. Sensor users could update their allocations based on the sensor provider's price policy, and iteratively approach an optimal solution. In each iteration, sensor user agents individually determine their optimal allocation and communicate their results to the sensor resource agents. Sensor resource agents then update their prices and communicate the new prices to the sensor user agents and the cycle repeats. Prices are then iteratively changed to accommodate the demands for resources until the total demand equals to the total amount of sensor resources available. Sensor resource agents publish sensor descriptions to the market. Sensor providers compete actively for sensor jobs from sensor users and execute them for gaining profits. Every sensor provider tries to maximize its profit based on its resource
capability and energy consumption. We assume that the sensor resource agents do not cooperate. Instead, they act non-cooperatively with the objective of maximizing their individual profits. The sensor resource agents compete among each other to serve the sensor user agents. The sensor user agents do not collaborate either, and try to purchase as much sensor resource as possible with the objective of maximizing their net benefit.
3.2 Mathematic Formulation
In this section, we set up the mathematical models for optimal sensor resources allocation in sensor enabled grid computing environment.
First gives notations to be used in the following sections: Pj: the price of the sensor resource unit in sensor j. Bt : the expense budget given to a sensor grid application i
Ej: the energy limit of sensor resource j
uj : money paid to the sensor resource j by sensor grid user i
q": sensing task of ith sensor grid application's nth sensor job
t«: the time taken by sensor grid application i to complete sensor job n
Ti: time limits given by sensor grid application i to complete all sensor jobs
eSj: energy consumption of unit resource of sensor j
ecJj : energy dissipation of sensor resource j for completing sensor grid application i
x. : sensor allocated to sensor grid application i by
the sensor resource j
It is assumed that the sensor grid system consists of multiple grid sites that contain sensor nodes and ordinary fixed grid nodes. Sensor nodes consist of a collection of sensors M connected by sensor network. In sensor grid, an application set is denoted as App = {App1, App2...Appt} and a sensor resource
set is denoted as s = {s1, s2, sj...} , Cj is the available capacity of the sensor resource Sj. Sensor node estimates its energy consumption rate es ■ for executing the application set, and the energy constraint is Ej. If the energy consumption is proportional to sensor resource unit, as is the case with battery energy. x. is sensor
allocated to sensor grid application i by the sensor resource j. The energy limitation of the sensor imposes a constraint as follows:
i	i
2ecj = 2esX < Ej	(3.1)
i=1 i=1
The sensor jobs are assumed to acquire real time data from sensor grid node, mutually independent, and can be
168 Informática 36 (2012) 167-59
L. Chunlin et al.
executed at certain sensor grid node. As soon as a sensor job arrives, it must be assigned to one sensor grid node for processing. When a sensor job is completed, the executing sensor node will return the results to the originating sensor nodes or ordinary fixed grid node of the job. We use SJ to denote the set of all sensor jobs generated by sensor grid application i, SJi = {SJ1, SJ^...SJ" } . Each sensor job can be described as SJ" = (t", q") , in which t" stands for the time taken by the i-th sensor grid application to complete n-th sensor job, qn. stands for sensing task of ith sensor user' s nth sensor job. There are no dependencies among the sensor jobs, so the submission order and completion order won't impact on the execution result.
We assume that sensor user has an associated utility
function Ui (xj)if the allocated sensor resource is xi •
Now, we formulate the problem of optimal sensor resources allocation in sensor enabled grid environment as constraint optimization problem, the utility of the sensor grid system is defined as the sum of sensor grid user utilities.
xj is sensor resource allocation obtained by sensor user i from the sensor provider j. The utility function for sensor user application Ai depends on allocated sensor
resources xij . The objective of sensor resource allocation optimization is to maximize the utility of the sensor grid system without exceeding the sensor capacity, the energy limit of sensor, expense budget and the deadline. We formalize the problem using nonlinear optimization theory; the sensor resource allocation optimization in sensor grid can be formulated as follows.
,p% ,Yi)=m (xi)-4 (£uj - b )-P (ztn-T )
MaxU<,
= XU (xi)
Subject to Bi > £ U , Tt > £11
j	n=1
f^ecj < Ej, c j >£ xj
-% (£eci - Ej)-7 (Z xj - cj)
(3.4)
9L/ =VU, (xj) /9 xj

7,
j - P,
j (9U, (xj )
xj (

(3.2)
(3.3)
7
7 (Z xi - Cj) = 0,
-- P
9 tn
9 tn/
/9 xi ,) = 0
p (z tn - t ) = o
n
% (Z eci - Ej) = 0
(3.5)
(3.6)
Equation 3.2 is the sensor grid system utility maximization formulation. The sensor grid utility is defined as the sum of utilities for all sensor users. The cost overhead accrued to complete jobs cannot exceed the expense budget Bi . The time for completing all sensor jobs of user application i cannot exceed the deadline Tt. The total energy consumed by sensor j for executing sensor user applications cannot exceed an energy limits Ej. Aggregate allocated resource does not
exceed the total sensor capacity c j .
We can apply the Lagrangian method to solve such a problem. The Lagrangian approach is used to solve constrained optimization problems. Let us consider the Lagrangian form of sensor resource allocation optimization problem in sensor grid:
Where , P , 7i is the Lagrangian multiplier of
sensor user i. Thus, given that the sensor grid knows the
utility functions Ui(xj) of all sensor user i, this
optimization problem can be mathematically tractable. However, in practice, it is not likely to know all
the Ui (xj) , and it is also infeasible for sensor grid
environment to compute and allocate sensor resource in a centralized fashion. Solving the objective function
Max USensorGrid requires global coordination of all
sensor users, which is impractical in distributed environment such as the sensor grid.
The system model presented by (3.2) is a nonlinear optimization problem with N decision variables. Since the Lagrangian is separable, the maximization of the Lagrangian can be processed in parallel for sensor users and sensor providers respectively. The sensor resource
allocation{xj}solves problem (3.2) if and only if there
exist a set of nonnegative shadow costs {7 i}. Generally
solving such a problem by typical algorithms such as steepest decent method and gradient projection method is of high computational complexity, which is very time costing and impractical for implementation. In order to reduce the computational complexity, we decompose the sensor utility optimization problem (3.2) into two subproblems for sensor users and sensor providers. The shadow costs suggest a mechanism to distribute the sensor resource optimization between the sensor users and the sensor grid. We consider the Lagrangian
multipliers 7i to be the prices charged by sensor resource
providers in sensor market, equation (3.7) describes sensor user's behavior in sensor market as a sensor consumer, and equations (3.8) describe the sensor provider's strategy as a sensor supplier. By decomposing the Kuhn-Tucker conditions into separate roles of sensor user and sensor supplier at sensor market, the centralized problem (3.2) can be transformed into a distributed problem. Sensor user's payment is collected by the sensor providers. The payments of sensor users paid to sensor providers are the payments to resolve the optimality of sensor resource allocation in the sensor
n
9
9
9
9
x
x
i=1
i=1
A MARKET BASED APPROACH FOR.
Informatica 36 (2012) 167-176 169
market. We decompose the problem into the following two subproblems (3.7) which is sensor user optimization problem and (3.8) which is sensor providers optimization problem, seek a distributed solution where the sensor provider does not need to know the utility functions of individual sensor user. Two maximization subproblems correspond to sensor user optimization problem as denoted by (3.7)
SA = Max{( B,uj ) + (Ttf )}
j	n=1
N
stT >Xtf
(3.7)
and a sensor provider optimization problem as denoted by (3.8) .
SR = Max£ uj log xj + (E, - X ecj )
i=1
i
s.t.Cj >X xil, £ ecj < Ej
(3.8)
In (3.7), for the sensor user optimization problem, the sensor user gives the unique optimal payment to sensor provider under the deadline constraint to maximize the
sensor user's benefit. (Bi -X uj ) represents the money
j
surplus of sensor user, which is obtained by budgets subtracting the payments to sensor providers. So, the objective of (3.7) is to get more surpluses of money at the some time complete jobs for sensor user as soon as possible. In (3.8), for the sensor provider's optimization problem, different sensor providers compute optimal sensor resource allocation for maximizing the revenue of their own and minimizing the energy consumption for completing sensor grid application. We could have chosen any other form for the utility that increases
with x. . But we chose the log function because the
benefit increases quickly from zero as the total allocated sensor resource increases from zero and then increases slowly. Moreover, log function is analytically convenient, increasing, strictly concave and continuously differentiable. The benefits of sensor provider are affected by payments of sensor users, allocated resources and energy consumption. It means that the revenue increases with allocated sensor resources increasing and payment increasing, also with energy consumption decreasing. The objective of sensor providers is to
i
maximize u/log xj and minimize X ecj under the
i=i
constraints of their energy limit. Sensor providers can't dissipate energy more than Ej, which is the upper limit
of energy presented by sensor providers. (Ej -X ecj )
i
represents the energy surplus of sensor provider which is obtained by the energy limit subtracting energy dissipation. Thus, the optimization framework provides a distributed approach to the sum utility maximization problem. Sensor user layer problem adaptively adjusts
sensor user's resource demand based on the current sensor resource conditions, while the sensor resource layer adaptively allocates sensor required by the upper layer. The interaction between the layers is now controlled through the use of the variable yi, which is the
price charged from sensor users by sensor provider and coordinates the sensor user demand and the supply of sensor resource.
For the sensor user optimization problem, the sensor user gives the unique optimal payment to sensor provider under deadline constraint to maximize the sensor user's satisfaction.
In equation (3.7), Let Pj denote the unit price of sensor j, Let the pricing policy, p = (p1,p2, • • •,Pj) ,
denote the set of sensor prices of all the sensor providers at the sensor resource layer. The sensor user i receives sensor resource proportional to its payment relative to the
sum of the sensor provider's revenue. Let x. be the
sensor resource units allocated to sensor user i by sensor provider j.
The time taken by the ith sensor user to complete «th sensor job is:
q«Pj
tn=-
(3.9)
cu
We reformulate sensor user optimization problem as
N qfp,
Max{( B,-X uj ) + (T-X^f )}
(3.10)
n=1 CjUj
We take derivative and second derivative of SA with respect to u j :
SA-(,,j) = fA = j -1
dui «=1(uj) c
SA"(u{) =
d2 SA(uj) d (uj)2
N

= -X- 3
n=1(uj ) cj
SA"(uj) < 0 is negative due to u/ > 0 .The
extreme point is the unique value maximizing the sensor user's utility under completed time limits. The Lagrangian for the sensor user's utility is L(u j ) .
Nq fPj
L(uj) = (Bi -Xuj) + (T -X^j) + XT -It«)
j «=1 cjui «=1
(3.11)
Where X is the Lagrangian constant. From Karush-Kuhn-Tucker Theorem we know that the optimal
solution is given dL(u' / . = 0for X>0.
/duj
dL^y =-1+
/du	c, (uj)2 Cj (uj )2
(3.12)
Let
dL(uj )
du,
= 0 to obtain
n=1
1=1
168 Informática 36 (2012) 167-61
L. Chunlin et al.
= (
(1 +
1/2
(3.13)
L( xj) = Yuj log xi + ( Ej - £ esjx-j) + 5(Ej - £ es^-j)
Using this result in the constraint
equation Ti = £ t ", we can determine 0 = 1 + A as
t=£>; =£%=£^(0^) (3.
-1/2
14
n=1	n=1 C jUi
CJ	CJ
We obtain
(0)-1/2 = -
T
k
£ )
k=1 C,
1/2
We get ui
k 1/2 £ ( q pk )
1/2 £ (-)
f = (-1 i fi) ui =( )
q Pà k=1 c
J
T
(3.16)
uj is the unique optimal solution to sensor user
optimization problem. It is the optimal payment of sensor user i to sensor provider j under the completion time constraint to maximize the sensor user's benefits.
For the sensor provider's optimization problem, different sensor providers compute optimal sensor allocation for maximizing the revenue of their own under constrains of energy limit.
In equation (3.8), £u ¡log xi presents the revenue
obtained by sensor resource j from sensor users. The energy consumption of sensor provider for executing
users' task can't exceed more than Ej , which is the
upper limit of sensor power.
The energy dissipation of sensor resource j for completing grid application i be written:
(3.17)
We reformulate sensor provider's optimization problem as
i
SR = Max£ uj log xj + (E} - £ esrf ) (3.18)
¿=1
We take derivative and second derivative with respect to xi :
ecj = eSjXj
SR '( xj) =
u
- es j , SR"( xj) = --2
j	xi
SR"(xJ) < 0 is negative due to 0 < xj .The extreme point is the unique value maximizing the revenue of sensor provider. The Lagrangian for SR is L(xj)
i=1
I
= £ (uj log xj - (5 + 1)eSj.xj) + (5 + 1)Ej
i=1
(3.19)
Where G is the Lagrangian constant. From Karush-Kuhn-Tucker Theorem we know that the optimal
solution is given dL(x)/ = 0 for X >0.
(3.15)
Ôx
ÔL(xjK j = ^ - (S + l)esJ /ô xi xJ	J
(3.20)
Let ÔL( x)/x = 0
xi =
(S + l)es.
(3.21)
Using this result in the constraint equation, we can determine g = 1 + 5 as
E = 7 £
7 =
7 =
£
k=1
ui
E,
We obtain
uJE,.
esi £ u
(3.22)
j^k
k=1
J
xi is the unique optimal solution to sensor provider's optimization problem. It means that sensor providers allocate xij to sensor user to maximize its revenue.
4 Description of Algorithms
The objective of market based sensor allocation is to maximize the utility of the sensor grid system without exceeding the energy limit, expense budget and the deadline. The proposed algorithm decomposes optimal sensor resource allocation optimization problem into a sequence of two sub-problems via an iterative algorithm. In each iteration, in sub problem 1, the sensor user computes the unique optimal payment to sensor provider under expense budget and the deadline constraint to maximize the sensor user's benefit. The sensor user individually solves its fees to pay for sensor resource to complete its all sensor jobs, adjusts its sensor demand and notifies the sensor provider about this change. In sub problem 2, different sensor providers compute optimal sensor resource allocation for maximizing the revenue of their own under energy constraint. Sensor provider updates its price according to optimal payments from sensor user, and then sends the new prices to the sensor user s and allocates the sensor resource for sensor user, and the cycle repeats. The iterative algorithm that achieves sensor resource allocation optimization is described as follows.
)
u
i=1
i=1
C
n=1
)
u
u
*
x
x
A MARKET BASED APPROACH FOR.
Informatica 36 (2012) 167-176 169
Algorithm 1 Market based Sensor Allocation Algorithm (MSA)
Sensor user i
Receives the new price p . from the sensor resource j;
//calculates ui
to
ui = Max Usa (ui ) ;
maximize USA (u. ) If B >y U
Then Return ui to sensor resource j ; Else Return Null;
Sensor resource j
Receives optimal payments ui from sensor user i;
xj("+1)* = MaxUSR(xj); // Calculates its optimal
( n+1)*
sensor resource x.
pj+1) = max{&, pj + r(xJp.(n) - c.)} ; // Computes a new price
// XJ = Z Xj, r > 0 is a small step size parameter, n is iteration number
Return sensor resource price p(n+1) to all sensor users;
5 Simulations
In this section, the performance evaluation of our mechanism is conducted. The sensor grid simulator is implemented on top of the JAVASIM network simulator [22]. In the experiments, 150 sensors are uniformly deployed in a field that is 500m x 500m in area. There are also 16 base stations that are deployed based on a uniformly random distribution. Sensor tasks are created in uniformly distributed locations in the field. There are a total of 150 sensor resources and 600 sensor users are taken for experimental evaluation of the system. Energy consumption is represented as a percentage of the total energy required to execute all job and meet deadlines. Assume that the maximum power, Pmax, corresponds to
running all jobs with the maximum processing frequency. The maximum frequency is assumed to be fmax = 1 and the maximum frequency-dependent power
is Pmax = 1. When the power capacity for each interval is
limited, we can only consume a fraction of P when
'	^	max
processing requests during a given interval. Jobs arrive at each site si, i=1, 2,..., n according to a Poisson process
with rate a. The energy cost can be expressed in grid dollar that can be defined as unit energy processing cost. The initial price of energy is set from 10 to 500 grid dollars. Sensor users submit their jobs with varying deadlines. The deadlines of sensor user application are chosen from 100ms to 400ms. The budgets of sensor
applications are set from 100 to 1500 grid dollars. Each experiment is repeated 6 times and 95% confidence intervals are obtained.
The experiments are conducted to compare proposed market based sensor allocation algorithm (MSA) with an integrated and flexible scheduler for a sensor grid [3], which makes use of several scheduling and load balancing algorithms to suit the characteristics of sensor jobs in sensor grid environment. The reason for choosing reference [3] as the comparison is that both our work and reference [3] provide a resource scheduling and allocation algorithm for sensor grid environment. In [3], they adapted four existing multiprocessor scheduling algorithms to suit the sensor grid scenario: Earliest Deadline First (EDF), First Come First Served (FCFS), Least Laxity First (LLF), and Shortest Job Next (SJn). EDF is a scheduling algorithm that allocates higher priorities to jobs closer to their deadline. As an alternative to the static priority schedulers, it guarantees schedulability when node utilization is full. In the case where deadlines are equal, we modified the algorithm to use the duration of the job as a tie breaker, with shorter duration jobs given a higher priority. FCFS is the simplest of the four scheduling algorithms. Using a queue structure, this algorithm simply adds new jobs to the end of the queue as they arrive, picking jobs for execution only from the front of the queue. A derivative of EDF, LLF is a scheduling algorithm that allocates priorities on the amount of laxity a job has: the lower the laxity, the higher the priority. The laxity, or slack time, is the time left until its deadline after the job is completed, assuming that the job could be executed immediately. SJN allocates priorities statically depending on the duration of jobs. Shorter jobs are favored, and are given higher priorities. Similar to LLF, the modification made to the algorithm was to allocate a higher priority to the job with the nearer deadline when durations are equal.
The paper performed the evaluations to measure the impact of the algorithms using several performance metrics, and test whether the algorithm can satisfy performance objectives such as sensor resource utilization, allocation efficiency, sensor job execution success, response time and energy consumption ratio. We study the performances of proposed market based sensor allocation algorithm (MSA) with several scheduling and load balancing algorithms for a sensor grid [3]. We choose the performance metrics and simulation parameter according to the reference [3]. Performance metrics include in terms of allocation efficiency, execution success ratio, response time and energy consumption ratio, resource utilization ratio. Allocation efficiency is defined as the percentage of allocated sensor among total available sensor resources. Execution success ratio is the percentage of sensor jobs executed successfully before their deadline. Energy consumption ratio is defined as the percentage of consumed energy of sensors to complete the jobs. We compare the algorithms by varying load factor to study how they affect the performance of the algorithms.
The following four figures (Figs.1, Figs.2, Figs.3, and Figs.4) are to study resource allocation efficiency,
168 Informática 36 (2012) 167-63
L. Chunlin et al.
execution success ratio, response time, energy consumption ratio and resource utilization ratio under different load factor (LF) respectively. Load factor varies from 0.1 to 0.9. Fig.1 shows the effect of load factor on allocation efficiency. When LF=0.5, allocation efficiency of MSA is as much as 17% less than that with LF=0.1. The allocation efficiency is larger when the load factor (LF) is smaller. When load factor increases, system load increases; some sensor user agent's requirements can't be processed on time. The sensor user agents with low budget don't have enough money to buy sensor and can't complete jobs before deadline; this leads to low allocation efficiency. When load factor is 0.5, allocation efficiency of MSA is 27% more than FCFS. Compared with FCFS and SJN, the allocation efficiency of MSA decreases more slowly when the load factor increases. When the load factor is 0.6, the allocation efficiency of LLF decreases to 54%, the allocation efficiency of MSA decreases to 84%. The allocation efficiency of MSA is better than SJN, LLF and FCFS. Considering the execution success ratio, from the results in Fig.2, when load factor is 0.5, the execution success ratio of SJN is 28% less than that using MSA. When load factor increases, execution success ratio of SJN and FCFS deteriorate quickly. SJN and FCFS scheduling algorithms don't consider optimization of both sensor resource providers and sensor users, it wants to minimize the runtime of sensor jobs. EDF has higher execution success ratio than MSA. When the load factor increases, fewer requests from sensor user agents can be admitted into the system due to the increase of system burden, so, fewer requests from sensor user agents can be executed successfully before their deadline. Fig.3 shows the energy consumption ratio under different load factors. When load factor increases, more requests need to be processed within one interval and the energy consumption ratio increases. When increasing the load factor by LF=0.7, the energy consumption ratio of MSA is as much as 25% more than LF=0.4. Under same load factor (LF=0.8), the energy consumption ratio of MSA is 16% less than that of EDF. The energy consumption ratio of MSA and EDF is less than that of SJN, LLF and FCFS. Fig.4 shows the effect of load factor on the response time. The smaller is LF, the lower is the response time. When LF=0.7, the response time of MSA is as much as 30% more than that by LF=0.2. SJN provides the shortest response times amongst all algorithms. The response time of LLF is longest among other algorithms. The value of LF is low, the system is lightly loaded, the price of the sensor provided by sensor resource agent is cheap; sensor user agents with low budget can choose cheap sensor resources to complete jobs under the deadline, so the satisfaction of the sensor user agent is high. When the system is heavily loaded, the price of the sensor resource is expensive; some sensor user agent need more time to complete tasks.
I 1 ■ 20.8 -
TS0.6 I-
Jo.4 I-
CÖ
o
= 0-2 -
0
MSA	—♦—LLF —	EDF
FCFS	* SJN	
_l_I_I_L_
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 load factor
Figure 1: allocation efficiency under various load factor.
■3 1	-
«	.
Ü0.8	-
o
§0.6	-
§0.4	-
§0.2	-
x	•
" 0	-
MSA	—♦—LLF -	-A—EDF
FCFS	* SJN	

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 load factor
Figure 2: execution success ratio under various load factor.
S 0.6
3
m
o 0.4
o
M 0.2
MSA	—♦—LLF —	EDF
FCFS	—*— SJN	
MSA	—♦—LLF —	A—EDF
FCFS	X SJN	
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 load factor
Figure 3: energy consumption ratio under various load factor.
600 12 500 ~|400 'IS 300
m
no200
CX
er100 0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 load factor
Figure 4: response time under various load factor.
no 0.8
O A u 0
A MARKET BASED APPROACH FOR.
Informatica 36 (2012) 167-176 169
6 Conclusions
The paper presents market based sensor resources allocation in sensor enabled grid computing environment. Since sensor users' tasks might compete for the exclusive usage of the same sensing resource we need to allocate individual sensors to sensor users' tasks. Sensor grid tasks are usually characterized by an uncertain demand for sensing resource capabilities. We model this allocation problem by introducing the sensor utility function. The goal is to find a sensor resource allocation that maximizes the total profit. The paper proposes a distributed optimal sensor resource allocation algorithm. The performance evaluation of proposed algorithm is evaluated and compared with other resource allocation algorithm for sensor grid. In the future, we will consider moving our method to a real grid platform to test its feasibility.
Acknowledgement
The authors thank the editor and the anonymous reviewers for their helpful comments and suggestions. The work was partly supported by the National Natural Science Foundation of China (NSF) under grant (No. 60970064,No.61171075), National Key Basic Research Program of China (973 Program) under Grant No.2011CB302601,0pen Fund of the State Key Laboratory of Software Development Environment under Grant (No.SKLSDE-2011KF-01), Program for New Century Excellent Talents in University, China (NCET-08-0806), Fok Ying Tong Education Foundation, China (Grant No. 121067). Any opinions, findings, and conclusions are those of the authors and do not necessarily reflect the views of the above agencies.
References
[1]	Peter Komisarczuk and Ian Welch, Internet Sensor Grid: Experiences with Passive and Active Instruments, IFIP Advances in Information and Communication Technology, pp. 132-145, 2010
[2]	M. Pallikonda Rajasekaran, S. Radhakrishnan, and P. Subbaraj, Sensor grid applications in patient monitoring, Future Generation Computer Systems, 2010, 26(4):569-575
[3]	Hock Beng Lim and Danny Lee, An Integrated and Flexible Scheduler for Sensor Grids, UIC 2007, LNCS 4611, pp. 567-578, 2007.
[4]	Nikolaos Preve, SEGEDMA: Sensor grid enhancement data management system for Health Care computing, Expert Systems with Applications, 2011,38(3):2371-2380
[5]	Huang-Chen Lee, Chun-Yu Lin, Chuan-Yu Cho, Chen-Lung Chan,Yao-Min Fang,Bing-Jean Lee, Chung-Ta King, The design considerations of a sensor grid for monitoring precipitation in debris-flow-prone areas, IPSN '10 Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks, 2010, 362-363
[6]	Fox, G.; Ho, A.; Rui Wang; Chu, E.; Isaac Kwan; A Collaborative Sensor Grids Framework ; Collaborative Technologies and Systems, 2008. CTS 2008. International Symposium on, 2008, pp.29 - 38.
[7]	Hock Beng Lim; Iqbal, M.; Wenqiang Wang; Yuxia Yao; A Large-Scale Service-Oriented Sensor Grid Infrastructure, Consumer Communications and Networking Conference, 2009. CCNC 2009. 6th IEEE, 2009, pp: 1 - 2
[8]	Sanabria, J.; Rivera, W.; Rodriguez, D.; Yunes, Y.; Ross, G.; Sandoval, C.; A Sensor Grid Framework for Acoustic Surveillance Applications, INC, IMS and IDC, 2009. NCM '09. Fifth International Joint Conference on, 2009, pp: 31 - 38
[9]	Hock Beng Lim, Mudasser Iqbal, Wenqiang Wang, Yuxia Yao, The National Weather Sensor Grid: a large-scale cyber-sensor infrastructure for environmental monitoring, International Journal of Sensor Networks, 2010,7( 1-2):19 - 36
[10]	Toshihiro Matsui and Hiroshi Matsuo, A constraint based formalisation for distributed cooperative sensor resource allocation, International Journal of Intelligent Information and Database Systems, 2010, 4(4):307 -321,
[11]	Yan YuJie; Wang Shu; Hao Zhao; MPAS: a Connecting Platform for Integrating Wireless Sensor Network with Grid, Communications, 2005 Asia-Pacific Conference on, 2005 , pp.1000 - 1004
[12]	Mohammad Mehedi Hassan, Biao Song and Eui-Nam Huh, A dynamic and fast event matching algorithm for a content-based publish/subscribe information dissemination system in Sensor-Grid, The Journal of Supercomputing, 2010,54(3):330-365
[13]	Se-Jin Oh; Chae-Woo Lee; u-Healthcare SensorGrid Gateway for connecting Wireless Sensor Network and Grid Network, Advanced Communication Technology, 2008. ICACT 2008. 10th International Conference on, Volume: 1, 2008, pp.827 -831
[14]	Xiaolin Li; Xinxin Liu; Huanyu Zhao; Nanyan Jiang; Parashar, M.; Autonomic Management of
Hybrid Sensor Grid Systems and Applications ; Computer Communications and Networks, 2008. ICCCN '08. Proceedings of 17th International Conference on, 2008, pp:1 - 6.
[15]	Toshihiro Matsui, Hiroshi Matsuo, A Formalization for Distributed Cooperative Sensor Resource Allocation, KES-AMSTA 2008, LNAI 4953, pp. 292-301, 2008
[16]	Chen-Khong Tham and Rajkumar Buyya, SensorGrid: Integrating Sensor Networks and Grid Computing, CSI Communications, pages 24-29, Vol.29, No.1, Computer Society of India (CSI), Mumbai, India, July 2005
[17]	Yong-Kang Ji, Yi Zhang, Zhicheng Xu, and Min-You Wu, Truthful Resource Allocation in Selfish Sensor Web, MSN 2007, LNCS 4864, pp. 683-693, 2007.
168 Informática 36 (2012) 167-65
L. Chunlin et al.
[18]	Chunlin Li, Layuan Li, Agent Framework to Support Computational Grid, Journal of Systems and Software, 2004, 70(1-2):177-187
[19]	Chunlin Li, Layuan Li, Joint QoS Optimization For Layered Computational Grid, Information Sciences, 2007, 177(15):3038-3059
[20]	Chunlin Li, Layuan Li, A Distributed Utility-based Two Level Market Solution For Optimal Resource
Scheduling In Computational Grid, Parallel Computing, 2005,31(3-4 ):332-351
[21]	Chunlin Li, Layuan Li, Utility based QoS Optimisation Strategy For Multi-Criteria Scheduling on the Grid, Journal of Parallel and Distributed Computing, 2007, 67(2):142-153
[22]	JAVASIM, http://javasim.ncl.ac.uk