Jacek Rzeniewicz
email: jrzeniewicz@gmail.com

Julian Szymański
email: julian.szymanski@eti.pg.gda.pl

W Lodzis Law Duch

Adaptive Algorithm for Interactive Question-based Search

Keywords: information retrieval, semantic search, decision trees

Popular web search engines tend to improve the relevance of their result pages, but the search is still keyword-oriented and far from "understanding" the queries' meaning. In the article we propose an interactive question-based search algorithm that might come up helpful for identifying users' intents. We describe the algorithm implemented in a form of a questions game. The stress is put mainly on the most critical aspect of this algorithm -the selection of questions. The solution is compared to broadly used decision trees learning algorithms in terms of knowledge inconsistencies tolerance, efficiency and complexity.

Introduction

Recent years we have observed semantic technology slowly making its way into the web search [START_REF] Studer | Editorial-special issue semantic search[END_REF]. Result pages of the most popular searchers like Google, Yahoo or Bing, provide us not only with references to the websites containing desired keywords, but also with additional information on the entities those sites represent. Hints with similar queries are displayed to the users as they type, helping them to express themselves more precisely and receive more relevant results. Finally, synonyms are used to broaden the search.

Moreover, a number of native semantic searchers has been launched last years eg. Duckduckgo, Hakia. However, despite offering categorization of results by context (eg. Yippy!), that aims to lead to better relevance, they generally haven't attracted wide audience yet. Finally, the question answering field has been developed significantly [START_REF] Forner | Overview of the clef 2008 multilingual question answering track[END_REF]. A number of both general (eg. Yahoo! Answers, Ask.com) and vertical (eg. StackExchange) Q&A engines are available on the Web, offering billions of answers.

On the other hand, broadly used search engines still cannot be considered as semantic in terms of "understanding" users' queries. The same query formulated different ways is usually served with different results [START_REF] Signorini | If you ask nicely, i will answer: Semantic search and today's search engines[END_REF]. Search is still mostly keyword-oriented. Users need to know proper words related to the subject in order to set the searcher on the right track and obtain relevant results. This is easy when user is searching the Web for a famous artist or a nearby restaurant, but gets tricky if he or she doesn't know any keywords (index phrases) that are distinctive for the desired entity. Let us consider this example: you saw a suricate in a ZOO and after returning home you want to learn more about it on the Web. The problem is, you can't recall its name and any keywords you can think of relate only to its appearance. You will spend a few minutes adjusting those keywords and clicking result links forth and back, or scrolling image results until you come across some information about suricates. When lacking proper keywords, users are required to devote a significant amount of time and effort looking for the information. That work should be performed by the search engine.

When imagining a perfect semantic searcher, it is handy to consider the notion of a Human Search Engine (HSE) [START_REF] Signorini | If you ask nicely, i will answer: Semantic search and today's search engines[END_REF]. This is a hypothetical searcher acting like a human being in terms of understanding the query. Back to the suricate example -how could the HSE help the user to find desired information? We imagine it being able to direct the search by prompting the user to provide more specific details. This way, the stress would be put less on the keywords selection and more on what the user interacting with the search engine has in mind -meaning of the query and particularly relevant answer in the form of provided search results. Some of today's searchers limitations might be overcome by a web searcher displaying the ability to take over the initiative and ask questions in the form of simple dialogues. Such an approach requires an effective algorithm: one that asks the minimum number of questions to recognize the appropriate meaning of the user's query.

In this article we address just that: a question-based search algorithm, especially its critical aspect -the selection of questions. The structure of this paper is as follows: in section 2 we introduce a question-based search model in a form of a word game. In section 3 the question-based search algorithm is described and compared to typical decision trees algorithms. We also gave an outline of our future plans in section 4.

Questions game -a computational linguistic challenge

A simple model of dialogue-based search can be approximated in the form of a game of questions. This is a word game where one player thinks of some concept and the other one asks a series of yes/no questions regarding that object. After at most twenty questions the latter guesses what was the concept his partner was thinking of.

The question-based search algorithm described in the following sections was implemented in the form of a questions game that is available on the Internet at http://kask.eti.pg.gda.pl/winston. There users can play the questions game with an avatar called Winston. The avatar took the role of asker and guesser, site visitors need to pick up a concept and answer avatar's questions. The core of the knowledge base was imported from the WordNet dictionary [START_REF] Miller | Wordnet: a lexical database for english[END_REF].

To test the approach we limit the domain to the information related to the animals branch of WordNet.

Apart from providing the means for the search algorithm evaluation, the questions game has another application. Upon completing each game, some knowledge can be added to the system. This is not only limited to the user answers during the game. After clearing up what the subject of the game was, the player is requested to answer yet another question: what can you tell me about the [subject]? User can reply to that by typing in a fact in a form of object-relationfeature. For example, to make the fact that suricates are burrowing animals come across, one can type can and burrow into the text fields. This way both the amount of assertions and the system's vocabulary expand.

The question-based search algorithm

In the first section the need for a question-based search algorithm has been justified. The task of assigning a proper meaning to user's input generally relates to the classification problem. However, before any algorithm is discussed, a few assumptions regarding the problem's conditions ought to be stated:

1. Matching target object may not be present in the system. 2. System's knowledge about given concept may be incomplete or partially incorrect. 3. Knowledge base may contain false assertions or represent a different point of view than user's.

Decision trees

One of the machine learning approaches that can be adopted to the search problems are decision trees algorithms. There are many of their variants: ID3

[5], C4.5 [START_REF] Mitchell | Machine Learning[END_REF] or latest successor See5/C5.0 [START_REF] Quinlan | Data mining tools see5 and c5.0[END_REF]. Those algorithms provide efficient mathematical model, so it requires a little number of steps and computing power to finalize the search: using binary decisions in nodes it is possible to index over one million classes performing only 20 tests. However, there are strong disadvantages to the decision trees approach when confronted with the stated assumptions. The process of searching develops towards a single hypothesis.

Usually it is unlikely that there will be a target concept that matches given input very well. Thus we are interested in receiving a set of most matching answers rather than just one. Decision trees don't facilitate that. Neighbor of the top matching leaf is not necessarily the second best match. Another crunch with decision trees is that the search paths are only optimized globally. According to the assumptions made in the beginning of this section, it can happen that the system's and user's knowledge differs. Occurrence of an answer that does not conform to the system's knowledge makes the decision tree take a wrong path, which must end up fatal for the overall search.

The next issue is that for a construction of a typical decision tree we usually have many examples and only a few classes. In the case of web search the problem is opposite: there are many potential classes (web pages relevant to user query) and each of them is described with a single example.

Knowledge representation for the question-based search algorithm

The approach presented here is mainly based on fuzzy semantic network as an underlying knowledge model [START_REF] Szymański | Information retrieval with semantic memory model[END_REF]. Specifically, the network consists of concepts interconnected with relations by connections called triples of knowledge, expressed in the vwORF notation:

O -the object described R -the type of relation, denoting how the object is related to the feature F -the feature expressing given property of the object v -confidence: the real number in the range 0, 1 describing, how this atom of knowledge is reliable. 0 denotes no certainty at all, 1 means the information is sure. w -support: the real number in range -1, 1 describing, to what extent the feature is related to the object. Allows to express adjectives such as "always" (1), "frequently" (˜0.5), "seldom" (˜-0.5) or "never" (-1). Figure 1 depicts an example assertion expressed in the vwORF notation. Here the fact that birds have wings was associated with parameters support w = 0.85 and confidence v = 0.97. This means that a bird most usually has a wing and that this assertion is almost sure to be true. The vwORF notation is capable of expressing elementary sentences. More complex assertions, e.g. that birds usually have two wings, cannot be expressed this way, but this could be enabled by allowing a whole triple on the "object" side of another triple.

As mentioned before, the questions game that is running the system is not only used to evaluate the efficiency of the search algorithm, but also to provide new assertions to the knowledge base. Therefore it is necessary to update triple's w and v parameters whenever a new assertion related to this triple appears. The support value is a simple weighted mean of individual assertions:

w = N i=1 |α i | • α iw N i=1 |α i | (1)
where: N -total number of assertions |α i | -weight of the i-th assertion α iw -support of the i-th assertion and the confidence value is a function of the weighted standard deviation of individual assertions:

σ 2 = N i=1 |α i | • (w -α i ) 2 N i=1 |α i | (2) v = 1 2 • (1 + cos (πσ)) ( 3
)
where σ is a non-negative value denoting the weighted standard deviation. In the Figure 2 the relationship between the standard deviation and confidence is presented. When all the individual assertions indicate equal feature support, the standard deviation is 0 and the confidence value equals 1. The confidence decreases as standard deviation goes up for incoherent assertions; in a boundary case of opposite assertions (such of support values 1 and -1), standard deviation approaches 1 and confidence tends to 0.

The semantic network is an economic (in terms of cognitive economy [START_REF] Conrad | Cognitive economy in semantic memory[END_REF] that allows to reduce redundancy) and powerful model [START_REF] Sowa | Principles of semantic networks[END_REF] that allows flexible complex model utterances. Such knowledge representation is easily browsable for humans using interactive graphs [START_REF] Szymański | Cooperative wordnet editor for lexical semantic acquisition[END_REF] and convenient to process, i.e. to perform inferences based on relation types interpretation that are related to the edges. On the other hand, only little amount of the overall information stored in the semantic network is stated explicitly and therefore it is hard to do any live computations on it. For this reason, for the sake of making the search computations easier, the knowledge is translated into the form of a semantic space.

The semantic space is an N-dimensional space where one dimension is associated with a unique pair (relation, feature). Those pairs are referred to as questions. Each concept in the semantic space is represented by a Concept Description Vector (CDV) [START_REF] Duch | Concept description vectors and the 20 question game[END_REF]. Every element e of each CDV holds two real numbers e w and e v denoting respectively support of the connection and the confidence of knowledge. Those values are copied from corresponding triple if exists or inherited from another concept, provided that there is a positive support triple with relation IS A pointing to that concept.

The algorithm

The search algorithm operates on the semantic space constructed from the semantic network. Over the consecutive iterations, a subspace S of candidate vectors is maintained. Any CDV can enter or leave S in between two iterations. The answers that user gives build up a vector ANSV. Each time a new answer appears, similarity s between ANSV and every CDV is computed:

cos (φ) = q:AN SV [q] =0 CDV [q] • AN SV [q] q:AN SV [q] =0 CDV [q] • q:AN SV [q] =0 AN SV [q] (4)
s = max (cos (φ), 0)

where CDV [q] denotes the confidence and support product of CDV's element for dimension q. Applying the max function in the end of calculations puts similarity into the range 0, 1 , which makes computations more convenient.

The main flow of the question-based search algorithm is as follows:

1. Include each CDV into S. 2. Ask the most informative question according to S. [START_REF] Signorini | If you ask nicely, i will answer: Semantic search and today's search engines[END_REF]. Obtain an answer to the question and update ANSV. 4. Compute similarity between every CDV and ANSV. 5. If maximum number of questions has been asked: return vector with the highest similarity to ANSV. 6. Rearrange S so that it include most similar vectors. 7. Go back to step 2.

Note that upon adding a new answer to the ANSV, all vectors' similarities are updated, even those excluded from S. This way no concept can ever be permanently eliminated, even if it doesn't go well with answers in the beginning.

It is also more accurate to always take all possible dimensions into consideration when evaluating a CDV. In practice it often happens that system asks questions that are unrelated to what the user thinks of. But somehow even those seemingly unrelated and unspecific features can help a lot to identify the right object [START_REF] Eckersley | How unique is your web browser?[END_REF][START_REF] Sweeney | Simple demographics often identify people uniquely[END_REF]. Global evaluation of a vector guarantees the most accurate results.

Selection of a question

In each iteration system picks a question that is the most informative across the candidates subspace S. Any CDV is included into S with probability p:

p =        0, if s ≤ s l 1 2 -1 2 cos π s-s l su-s l if s l < s < s u 1, if s ≥ s u (6)
where: s u -safety threshold parameter equal to s max -0.1 s l -rejection threshold parameter equal to s max -0.5 s max -highest similarity between CDV and ANSV in this iteration Figure 3 presents a sample plot of inclusion probability.

Once the subspace S is defined, information gain IG for each question q can be computed:

IG = - ω ⊘ ω • ω ⊖ ω ⊘ log 2 ω ⊖ ω ⊘ + ω ⊕ ω ⊘ log 2 ω ⊕ ω ⊘ (7)
where: ω -total weight of all CDV in S ω ⊘ -total weight of all CDV in S such that CDV [q] = 0 ω ⊕ -total weight of all CDV in S such that CDV [q] > 0 ω ⊖ -total weight of all CDV in S such that CDV [q] < 0 and a similarity between CDV and ANSV is considered CDV's weight. The question-based search algorithm described above to some extent can be considered opposite to the decision trees approach. As pointed out before, decision trees return only a single concept, because they are optimized globally and may very often reject correct branches due to local in-compliances between user's input and knowledge base state. Presented algorithm is more careful: in each step we process all possible concepts and evaluate them according to all possessed information. Any rejections are valid only within a single iteration, which eliminates the risk of decisions. At any time the algorithm can deliver a collection of best matching results, precisely defining how much they relate to the user specifications.

On the other hand, such approach lacks significant features that searching in decision trees has. Every step of the algorithm requires considerable amount of computations. Specifically, for a semantic space of N vectors and M questions iteration cost consist of: Second major drawback lies in the efficiency of the algorithm. Maintaining a broad set of candidate objects is safe and guarantees each concept a fair chance to be found in the assumed unstable conditions. Consequently, it can happen that obviously incorrect concepts are considered candidates.

Finally, it is noticeable that the algorithm presented here rejects to process according to common sense hierarchy. Assume there is a knowledge base containing 10 dog concepts and 100 related to cats. Human would most likely ask whether the concept is a cat or a dog. The algorithm promotes high-cardinality branches over those less numerous, and such a behaviour is unjustified.

Described question-based search algorithm overcomes significant drawbacks that searching in decision trees has. On the other hand, it introduces a cost of computation complexity and efficiency fall. In the next part of this section we address those issues.

Question asking strategies

Certain patterns of the system state that may result in algorithm's incorrect behaviour were distinguished in previous section. For each of these patterns, there is a strategy determining how to select a question:

1. A gap between the best-and the second best-matching concept: probability of inclusion of a CDV to the candidates subspace S depends on the difference between its similarity to the ANSV and maximum similarity in current step. Therefore it is unfortunate when incorrect concept remains top-matching for a number of iterations, since it worsens other concepts' odds. Appropriate strategy that should be applied here is to ask user about a feature that relates to that object's specific feature. 2. Numerous group of best-matching concepts: it happens that there is a whole group of very similar objects at the top of the candidates list. The algorithm is then unable to select a question separating this group since it maintains a broad candidates subspace S. In such case, S should be reduced only to the size of those top-matching set. 3. Mutually exclusive questions asked one after another: system happens to ask questions inconsistent with the latest answer. In example, once user gives positive answer to "is it a feline?" question, candidates subspace can still contain vectors describing dogs. Therefore a question "is it a canine?" is likely to be asked next. To avoid such contradictions, the following strategy was implemented: if user answers "yes" to a question q containing relation "IS A", then the candidates subspace S should only be composed of such CDV's that CDV [q] > 0. This way, in the scope of one step, the process resembles searching in a decision tree built on the hypernym relationship. The quality of avoiding incorrect rejections is abandoned, but chances for fast identification of specific features increase instead.

The search algorithm has been rearranged to allow applying the most appropriate strategy in each step. Previous logic of question selection was also encapsulated into a strategy. Algorithm's step 2 has been defined as follows:

a. Instantiate each strategy. b. Rank each strategy according to the state of the system. c. Draw one strategy with probability proportional to its rank. d. Ask a question returned by the selected strategy.

The rank of a strategy depends on the distribution of similarities between CDV's and ANSV, the index of current iteration and the previously picked strategies.

Actual question selection is delegated to the picked strategy.

Discussion and future plans

We have shown that typical approach used in decision trees are not suitable for applications where uncertainties and inconsistencies happen both on the knowledge base level and on the user's side. Our proposed algorithm proved the ability of being resistant to such inconsistencies. On the other hand, it introduces a demand for additional computations and is less efficient than typical decision tress. Several behaviour strategies have been implemented into the algorithm, and presented adaptive approach improves algorithm's efficiency significantly. It also demonstrates the flexibility of the algorithm -we showed that it is possible to apply a strategy that temporarily turns system's operation into decision trees alike. It seems that by tweaking this adaptive approach specifics we can achieve a high search efficiency in the end.

Our implementation employs lexical database provided by WordNet. The initial results obtained by the algorithm strongly depend on the knowledge quality stored in this repository. It should be stressed that the system interaction with the humans allows to introduce new, and correct already possessed knowledge. We employ this approach to crowdsourcing lexical knowledge [START_REF] Szymański | Context search algorithm for lexical knowledge acquisition[END_REF] and extending the Wordnet by large amount of interactions with people playing the word game.

During the following months we will attempt to overcome major remaining problems. The algorithm promotes branches of higher cardinality over smaller ones -this characteristic may be removed by filtering out the concepts that are too specific. This way, also the amount of computations will decrease. The scheme of assigning weights to answered questions can also improve the relevance of candidate concepts. Finally, implementation of more accurate behaviour strategies will increase the algorithm's efficiency as well. We believe that high flexibility of the approach we work on allows finding the right balance between limiting incorrect rejections and search efficiency.

Successful application of the presented approach has served us as a test bed of the question-based search algorithm. Implementation in limited domain of animals, employing knowledge from the WordNet dictionary, shows the ability of specifying the search according to interaction with the user. Now we scale up the solution and apply the algorithm for improvement the search in Wikipedia. For now we have created a prototype system for refining the query based search results using the category system in Polish and Simple English Wikipedia. The first results, deployed under http://bettersearch.eti.pg.gda.pl are promising, and they indicate the proposed method can be applied for improvement of

Fig. 1 .

 1 Fig. 1. Example assertion in the vwORF notation.

Fig. 2 .

 2 Fig. 2. Relationship between assertions standard deviation and the triple's confidence.

Fig. 3 .

 3 Fig. 3. CDV's probability of inclusion into S depending on similarity to ANSV vector.

-

  CDV's similarity update: O (N ) (assuming ANSV iteration complexity O (1)) -candidates subspace S re-arrangement: O (N ) -IG's update: O (N • M ) which results in the overall iteration complexity of O (N • M ), a considerable requirement compared to decision trees' O (1).

information retrieval precession.

ACKNOWLEDGMENTS:

The work has been supported by the Polish Ministry of Science and Higher Education under research grant N N516 432338.


Yonghong Yu

Yang Gao
email: gaoy@nju.edu.cn

Constraint Programming-Based Virtual Machines Placement Algorithm in Datacenter

Keywords: Datacenter, Virtual Machine Placement, Constraint Programming, CloudSim

As underlying infrastructure of cloud computing platform, datacenter is seriously underutilized, however, its operating costs is high. In this paper, we implement virtual machines placement algorithm in CloudSim using constraint programming approach. We first formulate the problem of virtual machines placement in virtualized datacenters as a variant of multi-dimensions bin packing problem, and then exploit constraint solver to solve this problem with the objective of minimizing number of physical machines that host virtual machines. Finally, we compare different virtual placement algorithms for evaluating constraint programming-based virtual machine placement algorithm including the built-in virtual machine placement algorithm in CloudSim and FFD algorithm. The experimental results show that constraint programmingbased virtual machines placement algorithm can efficiently reduce the number of physical machines to achieve the goal of reducing datacenter operating costs and improving resource utilization.

Introduction

As an emerging computing paradigm, Cloud Computing can provide users with on demand IT services and elastic computing platforms. Many institutes and companies recently focus on cloud computing technology. Some notable companies have designed and set up their cloud computing platforms respectively, such as Amazon EC2, IBM Blue Cloud, Microsoft Windows AZure, and Salesforce Sales Force. These cloud computing platforms offer customers storage, computing power, deploying environments and IT services at different layers. The development of cloud computing abilities is closely related to supports of underlying datacenters, which provide a powerful parallel computing power and massive data storage for cloud computing.

Operating costs of datacenters is rapidly increasing with scaling of datacenters. However, datacenters resources are seriously underutilized. Energy consumptions of IT devices in servers clusters is the largest contributor to operating costs. It is estimated that in 2006 the total electricity consumptions of datacenters in US cost of about $4.5 billion. Furthermore, US energy consumption by datacenters could nearly doubled again in 2011 [START_REF] Brown | Report to congress on server and data center energy efficiency[END_REF]. However, statistics in sports, e-commerce, and financial domains show the average server utilization varies between 11% and 50% [START_REF] Dasgupta | Workload management for power efficiency in virtualized data centers[END_REF]. The leading reason of underutilization is that administrator allocates hardware resources for hosting applications according to peak requirements of applications, although peak workloads of applications may not appear frequently. Furthermore, workloads of applications are dynamic, as well as there are stringent requirements for applications performance, such as applications throughput, response time, and cloud computing platform must meet applications SLA(Service Level Agreement). It is a big challenge for cloud datacenters to reduce operating costs and improve resource utilization while meet applications SLAs.

Server virtualization technology is an effective approach to improve the efficiency of resources and save energy while provides performance guarantees for applications. Using server virtualization technology, application runtime environment is encapsulated in a VM(Virtual Machine), and one or more virtual machines host on a PM(Physical Machine). Virtualization technology can provide performance isolation between VMs resided on the same PM, and avoid performance degradation caused by greedy or malicious applications . Moreover, it is helpful to improve resource utilization and save costs by multiplexing of datacenters resources across applications. Furthermore, virtualization technology enables VM live migration to handle dynamic workloads and meet application performance requirements.

However, adjusting the configuration of virtual machine and performing live migration manually obviously does not meet the needs of datacenters management. We need automate and intelligent approaches to address virtual machine management issue. Management of virtual machine consist of two phases: initial plan and runtime management. In initial plan stage, given a set of virtual machines and resource requirements of each virtual machine, as well as a set of physical servers, we need map each virtual machine onto physical machines. The goal of initial plan stage is to minimize the number of physical servers that host all virtual machines. In runtime management stage, we need to adjust configuration of virtual machines or perform live migration of virtual machine according to dynamic workloads. The purpose of runtime management is to minimize the number of virtual machines migration considered migration costs, while meet application SLAs. In this paper, we focus on the problem of virtual machine placement appeared in initialization plan stage of datacenters management with the goal of minimizing the number of physical machines. We first formulate the problem of virtual machine placement as a variant of multi-dimensions bin packing problem, and then exploit constraint solver to solve this problem with the objective of minimizing number of physical machines. Finally, we implement virtual machines placement algorithm using constraint programming technique in CloudSim [3]. Experimental comparison with other heuristic methods verifies the effectiveness of constraint programming-based approach.

The remainder of this paper is organized as follows. Section 2 describes related work. Then, Section 3 formulates virtual machine placement problem and describes in detail constraint programming-based virtual machines placement algorithm. Evaluation results are presented in Section 4. Finally,Section 5 concludes this paper and presents future work.

Related Work

Recently, several prototypes and methods have been proposed to address problems of virtual machine management by making a trade-off between applications performance, energy consumption and migration costs.

Verma et al. [START_REF] Verma | pmapper: power and migration cost aware application placement in virtualized systems[END_REF] have proposed pMapper, which is a power-aware application placement controller in heterogeneous server clusters. pMapper exploited heuristic to address virtual machine placement problem. Moreover, working set sizes of applications are considered while placing applications on physical machines. Wood et al. [START_REF] Wood | Sandpiper: Black-box and gray-box resource management for virtual machines[END_REF] presented Sandpiper, a system that automates the tasks of monitoring datacenters and detecting overloaded virtual machines, determining a new mapping relations between virtual machines and physical machines. Sandpiper implements a black-box approach which is fully OS-and application-agnostic as well as a gray-box approach that can leverage information collected from OS and application. To coordinate the actions taken by platform management and virtualization management in datacenters as well as support existing multivendor solutions, Kumar et al. [START_REF] Kumar | vmanage: loosely coupled platform and virtualization management in data centers[END_REF] explored a practical coordination solution that looselycouple platform and virtualization management in datacenters. In particularly, their solution designed a stabilizer component that prevent unnecessary virtual machine migrations by making a migration decision based on probability with which such a decision remains valid over certain duration in the future. In [7], Dhiman et al. present vGreen, a multitiered software system for energy-efficient virtual machine management in virtualized clusters environment. The most important feature of vGreen is that it implements policies for scheduling and power management of virtual machine using novel hierarchical metrics which capture energy consumption and performance characteristics of both virtual machines and physical machines. To handle local optimization problem of virtual machine placement in datacenters, Hermenier et al. investigated global optimization technique and proposed Entropy resource manager for homogeneous clusters, which utilizes constraint programming [8] to perform dynamic virtual machine consolidation with the aim of minimizing migration overhead. Our work draws upon the methods used in Entropy. On the contrary, we focus on virtual machine placement problem occurred in initial plan stage, and implement virtual machine placement algorithm based on constraint programming in CloudSim.

The above studies focus on configuration of virtual machine during runtime management of datacenters. Besides the above literatures, there're still some other research work similar to our work that is only concerned about initial plan task of datacenters. For example, Campegiani et al. [START_REF] Campegiani | A genetic algorithm to solve the virtual machines resources allocation problem in multi-tier distributed systems[END_REF] presented a genetic algorithm to search the optimal allocation strategy of virtual machines ,and designed penalty function to deal with unfeasible solutions. Bellur et al. [START_REF] Bellur | Optimal placement algorithms for virtual machines[END_REF] proposed linear programming and quadratic programming techniques to solve the problem. Jing XU et al. [START_REF] Xu | Multi-objective virtual machine placement in virtualized data center environments[END_REF] presented a two level control system to find the mapping of workloads to virtual machines and virtual machines to physical resources using an improved genetic algorithm with fuzzy multi-objective evaluation.

Constraint Programming-Based Virtual Machine Placement Algorithm

The problem of virtual machine placement can be formulated as a variant of multidimensional bin packing problem, which is combinatorial NP-hard problem. For this problem, several heuristics have been developed, such as FFD(First Fit Decreasing), BFF(Best First Fit), which can quickly provide sub-optimal solution.

In this section, we first formulate the problem of virtual machine problem, and then describe in detail virtual machine algorithm based on constraint programming.

Formalization of Virtual Machine Problem

In virtual machine placement problem, virtual machines are viewed as boxes, where various resource requests of each virtual machine are considered as dimensions of box with non-negative values. Physical servers are considered as bins, where CPU, memory and bandwidth capacities are regarded as properties of box. The goal of virtual machine placement problem is to determine the minimum number of physical machines required by the set of virtual machines. The problem of virtual machine placement in datacenters is defined as : given a set of virtual machines V M = {vm 1 , vm 2 , ..., vm n } and a set of physical machines P M = {pm 1 , pm 2 , ..., pm m }, where each vm i is a triplet vm i = (cpu i , ram i , bw i ), 1 ≤ i ≤ n denoted cpu,memory and bandwidth requirements of virtual machine respectively, each pm j is also a triplet pm j = (cpu j , ram j , bw j ), 1 ≤ j ≤ m denoted resource capacity of physical machine. In addition, x ij , 1 ≤ i ≤ m, 1 ≤ j ≤ n and y i , 1 ≤ i ≤ m are decision variables, x ij = 1 if and only if vm j is mapped onto pm i , y i = 1 if pm i is used to host virtual machine. The objective is to minimize m i=1 y i while finding all values of x ij . There are several implicit constraints in the above definition: (1) each virtual machine can be hosted on only one physical machine; (2) for each type of resource, the amounts of resource requests of virtual machines sharing the same physical machine are smaller or equal to capacity of physical machine hosting them; (3)the number of physical machines that host virtual machines are not more than m, m j=i y i ≤ m.

Constraint Satisfaction Model of Virtual Machines Placement Problem

In this section, we describe how to tackle virtual machine placement problem in datacenters using constraint programming approach.

Constraint programming has been widely used in a variety of domains such as production planning, scheduling, timetabling and product configuration. The basic idea of constraint programming is that user formulates a real-world problem as a CSP(constraint satisfaction problem) and then a general purpose constraint solver calculates solution for it. Formally, a CSP is defined by a triplet (V ariables, Domains, Constraints), where Constraints are the set of constraints being responsible for pruning the search space.

Combining the definition of virtual machine placement problem and the basic idea of constraint programming, the problem of virtual machine placement can by modeled by CSP in the following way:

Variables -X = {x ij |i ∈ [1, m] , j ∈ [1, n]} denote placement solution of virtual machine in datacenters. -Y = {y i |i ∈ [1, m]}, if the physical machine pm i is used, then y i = 1. -Load CP U = {load CP U i |i ∈ [1, m]},

Domains

-

∀x ij ∈ X, x ij ∈ [0, 1] -∀y j ∈ Y, y j ∈ [0, 1] -∀load CP U i ∈ Load CP U, load CP U i ∈ [0, pm i .cpu i ] -∀load RAM i ∈ Load RAM, load RAM i ∈ [0, pm i .ram i ] -∀load BW i ∈ Load BW, load BW i ∈ [0, pm i .bw i ] -solutionN um ∈ [0, m]
Constraints -C1: the total of resource requests of virtual machines sharing the same physical machine are smaller or equal to resource capacity of physical machine hosting them. 1. ∀i,

n j=1 x ij × vm j .cpu j ≤ pm i .cpu i , i ∈ [1, m] 2. ∀i, n j=1 x ij × vm j .ram j ≤ pm i .ram i , i ∈ [1, m] 3. ∀i, n j=1 x ij × vm j .bw j ≤ pm i .bw i , i ∈ [1, m]
-C2: assign y j = 1 if there are some virtual machines packed in physical machine pm j . In this paper ,we only consider cpu load of physical machine. ∀y j ∈ Y, y j = 1 ⇔ load CP U j > 0 -C3: each virtual machine can be packed in only one physical machine. ∀j,

m i=1 x ij = 1, j ∈ [1, n
] -C4: the number of physical machines that host virtual machines are not more than m. solutionN um = m i=1 y i ≤ m

In addition, we can set timeout for this algorithm to reduce the search time of constraint solver, and constraint solver will return local or global optimal solution until timeout expired.

Evaluations

To evaluate constraint programming-based virtual machine placement algorithm, we implement this algorithm in CloudSim and conduct two experiments to compare with FFD algorithm.

CloudSim is developed for simulation of cloud computing platform and support system modeling of datacenters, resource management and task scheduling. In CloudSim, the task of virtual machine placement is mainly completed by V-mAllocationPolicySimple class which selects a physical machine with the most number of available process units to create virtual machine iteratively. The virtual machine placement policy will use up all physical machine as long as the number of virtual machines is greater than the number of physical machines in datacenter, and this motivated us to design a virtual machine placement policy to reduce the number of physical machines that can host all virtual machines.

We define four classes of virtual machines representing different types of virtual machines respectively. The characteristics of each type of virtual machine are described in Table 1. Among four classes of virtual machine, VM1 represents Computing-intensive applications, VM2 and VM3 represents IO-intensive middle scale applications, VM4 represents small scale applications. There are two classes of physical server in datacenter. Their hardware parameters are described in Table 2. Throughout experiments we use a machine with a Intel(R) Core(TM)2 Duo CPU E7500@2.93 and 2GB memory installed CloudSim 3.0, Choco2.1.3 and JDK 1.7. The simulated datacenter consists of 50 physical machines, and each type of physical machine occupies half of the total. In order to verify constraint programming-based virtual machine placement algorithm that can efficiently reduce the number of physical machines required, we compare our approach with the built-in virtual machine placement algorithm of CloudSim and FFD at different ratios of the number of virtual machines to physical machines, in which we set timeout = 1 second for constraint programming-based virtual machine placement algorithm. The experimental results are plot in Figure 1. The results show that FFD algorithm and constraint programming algorithms is obviously better than CloudSim built-in algorithm in term of the number of physical machines used to host all request virtual machine in the same situations. When the ratio of number of virtual machines to number of physical machines equal to 1, CloudSim built-in algorithm occupies all physical machines, and other two algorithms only need about 20 physical machines. Comparing FFD algorithm with constraint programming-based virtual machine placement algorithm, the differences between FFD algorithm and constraint programming approach is small when the ratios are relatively lower, whereas with the increase of ratios of number of virtual machine to the number of physical machines, constraint programming approach can reduce more number of physical machines than FFD algorithm. In addition, when tmeout =1,2,3,4,5 minutes for constraint programming algorithm, we find the same result as Figure 1. It indicates that constraint programming algorithm can compute approximately global optimization solution within timeout.

To analyze the overhead of constraint programming-based virtual machine placement algorithm, we run each algorithm 10 times and average running time of each algorithms at different ratios, and setting timeout=1 minute for constraint programming approach. The experimental results are shown in Table 3.

From Table 3, we can find that the performance of FFD algorithm is optimal and valid that FFD algorithm can provide a fast and but often non-optimal solution. When the ratio of number virtual machines to number physical machines Our experiments conclude that constraint programming-based virtual machine placement algorithm can find better solution than FFD algorithm and CloudSim built-in placement algorithm with the goal of minimizing the number of physical machines hosting all requested virtual machine within timeout. Although constraint programming approach suffers from relatively long running times, we argue that time performance of virtual machine placement algorithm based on constraint programming is also acceptable because initial configuration of virtual machines is a task of planning and normally takes a long time. In practice, it is needed to trade-off between minimizing the number of physical machines and performance.

Conclusion and Future Work

In this paper, we focus on the problem of virtual machine placement appeared in initial plan stage of datacenters management and implement virtual machine placement algorithm exploiting constraint programming approach in CloudSim. The objective is to cut datacenters operating costs and improve resource utilization by reducing the number of physical machines and using virtualization technology. In order to achieve this objective, we formulate the virtual machine placement problem as CSP, and then choose Choco to solve this problem. We experimentally evaluate our approach and compare it with the built-in virtual machine placement algorithm in CloudSim and FFD algorithm. Experimental results show that constraint programming-based virtual machine placement algorithm can efficiently reduce the number of physical servers compared with FFD algorithm and CloudSim built-in placement algorithm, although suffers from relatively long search times.

A salient feature of cloud computing is to provide on-demand resource allocation strategy for applications in order to handle dynamic workloads. As part of future work, we are planning to study how to apply reinforcement learning and virtual machine live migration technologies to intelligently deal with dynamic peak workloads.

Fig. 1 .

 1 Fig. 1. The number of Physical machines used

  load CP U i denotes the total of cpu requests of virtual machines hosted on pm i .-Load RAM = {load RAM i |i ∈ [1, m]},load RAM i denotes the total memory requests of virtual machines hosted on pm i . -Load BW = {load BW i |i ∈ [1, m]}, load BW i denotes the total bandwidth requests of virtual machines hosted on pm i . -solutionN um denotes the number of physical machines used in the solution for virtual machine placement problem.

Table 1 .

 1 virtual machine types

	VM category CPU(MIPS) RAM(MB) BW(Mbit/s)
	VM1	2500	870	100000
	VM2	2000	1740	100000
	VM3	1000	1740	100000
	VM4	500	613	100000

Table 2 .

 2 Hardware parameters of physical servers

	PM category CPU(MIPS) RAM(MB) BW(Mbit/s)
	PM1	2*1860	4096	1000000
	PM2	2*2660	4096	1000000

Table 3 .

 3 Average running time of three algorithms , constraint programming-based virtual machine placement algorithm is able to return solution within timeout. However, when the number of virtual machine increase, constraint solver have not search whole space until timeout expired and only return approximately global optimal solution.

	VM/PM CloudSim FFD	CP
	10/50	5.48ms 1.58ms 47ms
	20/50	8.72ms 1.68ms timeout
	50/50 11.56ms 2.53ms timeout
	75/50 13.25ms 3.08ms timeout
	100/50 15.38ms 3.87ms timeout
	is 10/50

Acknowledgments. We would like to acknowledge the support for this work from the National Science Foundation of China (Grant Nos.61035003, 61175042, 61021062), the National 973 Program of China (Grant No. 2009CB320702), the 973 Program of Jiangsu, China (Grant No. BK2011005) and Program for New Century Excellent Talents in University (Grant No. NCET-10-0476).


Qiang Yang
email: qyang@cse.ust.hk

Transfer learning and Applications

In machine learning and data mining, we often encounter situations where we have an insufficient amount of high-quality data in a target domain, but we may have plenty of auxiliary data in related domains. Transfer learning aims to exploit these additional data to improve the learning performance in the target domain. In this talk, I will give an overview on some recent advances in transfer learning for challenging data mining problems. I will present some theoretical challenges to transfer learning, survey the solutions to them, and discuss several innovative applications of transfer learning, including learning in heterogeneous cross-media domains and in online recommendation, social media and social network mining.


Haohao Yuan

Jianhe Zhou

Suqiao Li

FPGA-based Image Acquisition System Designed for Wireless

Keywords: Digital image sensor, SBBC interface, FPGA, wireless transmission

Introduced micro-wireless transmission system image acquisition the overall structure, each part of the overall design ideas and works theory. Designed SBBC camera interface and data cache control module, analysis of the TCP / IP communication protocol standard structure and characteristics, and on this basis, the design of a non-standard short-range wireless communication protocol. System which controlled by the input and output module is based on FPGA, the system collected data alternately to the outer SDRAM, this realized the image data collection; Ethernet interface controller also designed in FPGA to achieve the image data transmit through wireless. The results show that: under normal conditions, the wireless communication module can be complete, accurate, stable wireless data transceiver functions.

Introduction

Along with the fast developing of computer, network transmission technology and communication technology, wireless remote video transmission has become a trend, this technology has gradually be applied in remote monitoring, aerial photo taken, conference call, etc. Video monitoring now generally use the following solutions [START_REF] Zhang Zhilu | Design and Implementation of Wireless Video Transmission System Based on i[END_REF][START_REF] Zheng Yehan | Design and implementation of wireless image capturing system[END_REF] : use high imaging quality of image sensor camera, through the S-VIDEO terminals transmission data in real-time, this plan need a camera and acquisition device connectivity, and the monitoring center also need large storage space to store image and video clips, this scheme is high real-time, but big energy consumption and high cost, so it is suitable for public security and monitoring. While the wireless image acquisition system based on FPGA with its low power consumption and reconfigurable characteristics being perfect choice. In the condition of the wireless application protocol has been developed, the center of gravity of the research is to image sensor used by the hardware platform and streams of data processing, at present the main schemes are: ①DSP+FPGA, use FPGA to complete data storage and preprocessing work, using DSP chip high-speed processing power to compress and process the image, this plan suitable for need data parallel processing and more numerical JPEG data flow.

② FPGA+ video codec chips, use the parallel processing ability of FPGA transmit and processing of images and video data simultaneously, because FPGA is reconfigurable in hardware, this plan suitable for the experimental stage. ③CPU + FPGA, use as the central control and interface CPU control role, use the FPGA to complete image processing tasks. MicroBlaze32 a soft processor core of Xilinx company is the industry's fastest soft handling solutions, running in the 150 MHz clock, it can provide 125 D-MIPS , very suitable for design in view of the network, data communication, embedded of complex system, so that the plan three with the CPU inside FPGA to design the wireless image acquisition system [START_REF] Xia Tao | Research and Implementation of Embedded Vide o Surveillance Streaming Server System in Mobile Network[END_REF] .

Design Thought

Wireless image acquisition system Based on FPGA is mainly collection site image signal, and the collected image data will be transmit to upper computer in real-time through Ethernet, at the same time can receive instruction data from upper computer, the whole system diagram shown as in figure 1. System mainly consists of four modules: image sensor module, image acquisition and control module, image storage and processing module, network data transmission module. In the process of operation, the FPGA will storage the CMOS sensor data to the expansion SRAM [4] , every full of a frame processor read data from SRAM and FPGA kernel processor by MicroBlaze will sent the data to the upper machine through the Ethernet chips. writing control module and based on the soft nuclear Ethernet interface were designed, below will make a detailed description for each part .

Image Acquisition and Interface Design

In the system the Omni vision company OV7620 type CMOS image sensor [5] was adopted as image sensor, it support continuous and interlaces the two scanning mode, with 10 double channel A/D converter, output eight image data; the highest pixels is 664 x 492, frame rate is 30 FPS; data formats including YUV, YUV, RGB three types, can satisfy the requirement of general image acquisition system, can programming configuration internal registers through SCCB bus. Meet the power supply and working in the crystals can output digital streaming of video at the same time also provide pixel clock PCLK, line reference signal----HREF、vertical synchronized signal----VSYNC, can use the clock signal above to determine each frame output image starting bit and end bit, meet the requirements of the external circuit read image Fig. 2. OV7620 and FPGA interface SCCB bus timing is similar to the I2C bus timing , SIO-0 equivalent to SDA, SIO-1 equivalent to SCL. The system set OV7620 work in slave mode, its interface with FPGA connection as shown in figure 2. The camera work mode can be set through write corresponding data to different registers, in the process of writing register first send OV7620 ID address, and then write the purpose of sending data register addresses, and finally to write data sent by setting the corresponding register, can make the image sensor work in a different model.

Data Storage Module

The data storage use company of ISSI IS61LV25616AL type chip, it is the static RAM, system of each frame resolution for the 640*480 grayscale image need 2457600 bit, less than its storage capacity 4194304 bit, can meet the storage requirements. To meet the real time requirement, data storage using high-speed SRAM switch mode, called "table tennis" mode. The specific process as follows: the data of image data flow distribution to two SRAM through FPGA output and output control module. In the first period, the input data cache to SRAM1, in the second period through the input data flow choice unit storage the date to SRAM2, at the same time, to sent the first cycle of data cached in SRAM1 to subsequent module through the FPGA output data choice unit, the third cycle the input data stream select units will storage data to SRAM1, at the same time, to sent data in SRAM2 last cycle through the output data choice unit to the follow-up module. So again, to realize the seamless data buffer, ensure the integrity of the image data.

Transmission

In the network transmission module, the chip BCM5221 made by BroadCom company was used in the physical, use the soft MicroBlaze32 nuclear as controller in the EDK development environment to generate the basic framework and related documents by generation wizard , the architecture of the soft nuclear as shown in figure 3. In the system, the DDR (double-data-rate) use the OPB DDR controller connect with OPB high-speed bus, and the Ethernet physical chip----BCM5221 connect with OPB bus through the Ethernet MAC, they are all OPB bus high-speed equipment; GPIO (General Purpose I/O) is the low speed terminal controller also can be connected in OPB bus, links such as LED and some terminals not high demand for the speed. MicroBlaze Debug modules MDM (MicroBlaze Debug Module) is responsible for download and test software.

The system adopts the TCP/IP protocol, divided into fluctuation two parts to realize [6, 7] . The physical layer realized by the hardware BCM5221 chip, the MAC layer realized by xilinx company Ethernet MAC IP nuclear ; The top of the transport layer by the software code realization, the LwIP agreement module, this module is one set for the embedded system is an open source TCP/IP protocol, the main purpose of LwIP is to keep the TCP/IP protocol in the main functions of the case to reduce the use of RAM, at present LwIP is widely used in all kinds of top-grade of embedded system. LwIP also support server mode and client mode, in the upper part of the agreement we adopt LwIP agreement module.

JTAG

Conclusion

After research of the traditional image acquisition module deeply, based on disadvantages of transmission to the traditional image acquisition module, designed the image acquisition and wireless transmission module for portable embedded system. The system realized the original data collection and image storage, ensure the image data of wireless transmission continuously and completely, with small size, low power consumption, speed advantages.

Fig. 1 .

 1 Fig.1. System diagram

Fig. 3 .

 3 Fig.3. Soft nuclear basic framework


Zhixin Li

Weizhong Zhao
email: zhaoweizhong@gmail.com

Zhiqing Li
email: lizhiqingchina@gmail.com

Zhiping Shi
email: shizhiping@gmail.com

Automatic Image Annotation and Retrieval Using Hybrid Approach

Keywords: automatic image annotation, continuous PLSA, semantic learning, hybrid approach, image retrieval

We firstly propose continuous probabilistic latent semantic analysis (PLSA) to model continuous quantity. In addition, corresponding Expectation-Maximization (EM) algorithm is derived to determine the model parameters. Furthermore, we present a hybrid framework which employs continuous PLSA to model visual features of images in generative learning stage and uses ensembles of classifier chains to classify the multi-label data in discriminative learning stage. Since the framework combines the advantages of generative and discriminative learning, it can predict semantic annotation precisely for unseen images. Finally, we conduct a series of experiments on a standard Corel dataset. The experiment results show that our approach outperforms many state-of-theart approaches.

Introduction

Content-based image retrieval (CBIR) has been studied and explored for decades. Its performance, however, is not ideal enough due to the notorious semantic gap [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF]. CBIR retrieves images in terms of their visual features, while users often prefer intuitive text-based image searching. Since manual image annotation is expensive and difficult to be extended to large image databases, automatic image annotation has emerged as a striking and crucial problem [START_REF] Datta | Image retrieval: ideas, influences, and trends of the new age[END_REF].

The state-of-the-art techniques of automatic image annotation can be categorized into two different schools of thought. The first one is based on discriminative model. It defines auto-annotation as a traditional supervised classification problem [START_REF] Carneiro | Supervised learning of semantic classes for image annotation and retrieval[END_REF][START_REF] Chang | CBSA: content-based soft annotation for multimodal image retrieval using bayes point machines[END_REF][START_REF] Li | Automatic linguistic indexing of pictures by a statistical modeling approach[END_REF][START_REF] Wang | Multi-label sparse coding for automatic image annotation[END_REF], which treats each semantic concept as an independent class and creates different classifiers for different concepts. This approach computes similarity at the visual level and annotates a new image by propagating the corresponding words. The second perspective takes a different stand. It is based on generative model and treats image and text as equivalent data. It attempts to discover the correlation between visual features and textual words on an unsupervised basis by estimating the joint distribution of features and words. Thus, it poses annotation as statistical inference in a graphical model. Under this perspective, images are treated as bags of words and features, each of which are assumed generated by a hidden variable. Various approaches differ in the definition of the states of the hidden variable: some associate them with images in the database [START_REF] Feng | Multiple Bernoulli relevance models for image and video annotation[END_REF][START_REF] Jeon | Automatic image annotation and retrieval using crossmedia relevance models[END_REF][START_REF] Lavrenko | A model for learning the semantics of pictures[END_REF], while others associate them with image clusters [START_REF] Barnard | Matching words and pictures[END_REF][START_REF] Duygulu | Object recognition as machine translation: learning a lexicon for a fixed image vocabulary[END_REF] or latent aspects (topics) [START_REF] Blei | Modeling annotated data[END_REF][START_REF] Liu | Image annotation via graph learning[END_REF][START_REF] Monay | Modeling semantic aspects for cross-media image indexing[END_REF]. Both these two kind of approaches have their own advantages and disadvantages. This paper will show that it is feasible to combine the advantages of these two formulations.

As a latent aspect model, PLSA [START_REF] Hofmann | Unsupervised learning by probabilistic latent semantic analysis[END_REF] has been successfully applied to annotate and retrieve images. PLSA-WORDS [START_REF] Monay | Modeling semantic aspects for cross-media image indexing[END_REF] is a representative approach, which achieves the annotation task by constraining the latent space to ensure its consistency in words. However, since traditional PLSA can only handle discrete quantity (such as textual words), this approach quantizes feature vectors into discrete visual words for PLSA modeling. Therefore, its annotation performance is sensitive to the clustering granularity. In the area of automatic image annotation, it is generally believed that using continuous feature vectors will give rise to better performance [START_REF] Blei | Modeling annotated data[END_REF][START_REF] Carneiro | Supervised learning of semantic classes for image annotation and retrieval[END_REF][START_REF] Lavrenko | A model for learning the semantics of pictures[END_REF]. In order to model image data precisely, it is required to deal with continuous quantity using PLSA.

This paper presents continuous PLSA, which assumes that feature vectors of images are governed by a Gaussian distribution under a given latent aspect other than a multinomial one. In addition, corresponding EM algorithm is derived to estimate the parameters. Then, each image can be treated as a mixture of Gaussians under this model. Furthermore, we propose a hybrid framework to learn semantic classes of images. The framework employs continuous PLSA to model visual features of images in generative learning stage, and uses ensembles of classifier chains to classify the multi-label data in discriminative learning stage. We compare our approach with some state-of-the-art approaches on a standard Corel dataset and the experiment results show that our approach performs more effectively and precisely.

The rest of the paper is organized as follows. Section 2 presents the continuous PLSA model and derives corresponding EM algorithm. Section 3 proposes a hybrid framework and describes the training and annotation procedure. Experiment results are reported and analyzed in section 4. Finally, the overall conclusions of this work are presented in section 5.

Continuous PLSA

Just like traditional PLSA, continuous PLSA is also a statistical latent class model which introduces a hidden variable (latent aspect) z k (k 1, …, K) in the generative process of each element x j (j 1, …, M) in a document d i (i 1, …, N). However, given this unobservable variable z k , continuous PLSA assumes that elements x j are sampled from a multivariate Gaussian distribution, instead of a multinomial one in traditional PLSA. Using these definitions, continuous PLSA [START_REF] Li | Automatic image annotation with continuous PLSA [C[END_REF] assumes the following generative process:

1. Select a document d i with probability P(d i ); 2. Sample a latent aspect z k with probability P(z k |d i ) from a multinomial distribution conditioned on d i ;

3. Sample x j ~ P(x j |z k ) from a multivariate Gaussian distribution N(x|μ k ,Σ k ) conditioned on z k .

Continuous PLSA has two underlying assumptions. First, the observation pairs (d i , x j ) are generated independently. Second, the pairs of random variables (d i , x j ) are conditionally independent given the latent aspect z k . Thus, the joint probability of the observed variables is obtained by marginalizing over the latent aspect z k , The mixture of Gaussian is assumed for the conditional probability P(.|z). In other words, the elements are generated from K Gaussian distributions, each one corresponding a z k . For a specific latent aspect z k , the condition probability distribution function of elements x j is

1 / 2 1/ 2 1 1 ( | ) e x p ( ( ) ( (2 ) | | 2 T j k j k k j k D k P x z x x μ π - = - - ∑ ∑ ) ) , μ - k ( 2
)
where D is the dimension, μ k is a D-dimensional mean vector and Σ k is a D×D covariance matrix. Following the maximum likelihood principle, P(z k |d i ) and P(x j |z k ) can be determined by maximization of the log-likelihood function

(3) 1 1 1 1 1 1 ( , )log ( , ), ( )log ( ) ( , )log ( | ) ( | ). N M i j i j i j N N M K i i i j k i j i i j k n d P d n d P d n d P z d P z = = = = = = = = + ∑∑ ∑ ∑∑ ∑ x x x x L
where n(d i , x j ) denotes the number of element x j in d i .

The standard procedure for maximum likelihood estimation is the EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. In E-step, applying Bayes' theorem to (1), one can obtain

1 ( | ) ( | ) ( | , ) . ( | ) ( | ) k i j k k i j K l i j l l P z d P x z P z d x P z d P x z = = ∑ (4)
In M-step, for any d i , z k and x j , the parameters are determined as

1 1 1 1 ( , ) ( | , ) , ( , ) ( | , ) N M i j k i j j i j k N M i j k i j i j n d x P z d x x n d x P z d x μ = = = = = ∑ ∑ ∑ ∑ (5) 1 1 1 1 ( , ) ( | , )( )( ) , ( , ) ( | , ) N M T i j k i j j k j k i j k N M i j k i j i j n d x P z d x x x n d x P z d x μ μ = = = = - - Σ = ∑ ∑ ∑ ∑ (6) 1 1 ( , ) ( | , ) ( | ) . ( , ) M i j k i j j k i M i j j n d x P z d x P z d n d x = = = ∑ ∑ (7)
Alternating ( 4) with ( 5)-( 7) defines a convergent procedure. The EM algorithm terminates by either a convergence condition or early stopping technique.

As for the parameters, if parameter P(x j |z k ) is known, we could quickly infer the other parameters μ k and Σ k using folding-in method, and vice versa. Folding-in method is a partial version of the EM algorithm. It updates the unknown parameters with the known parameters kept fixed, so that it can maximize the likelihood with respect to the previously trained parameters.

3

Hybrid Generative/Discriminative Approach

Hybrid Framework

On the basis of continuous PLSA, we propose a hybrid framework which combines generative and discriminative learning. The framework firstly employs continuous PLSA to model visual features of images. As a result, each image can be represented as an aspect distribution. Then, this intermediate representation can be used to build ensembles of classifier chains, which can learn semantic classes of images and consider the correlation between the labels at the same time. The framework is shown in figure 2.

In training procedure, we firstly get the parameters μ k and Σ k given aspect z k by modeling visual features of training images with continuous PLSA. At the same time, the aspect distribution P(z k |d i ) of each image is determined. This is the generative learning stage. The parameters μ k and Σ k are parameters of continuous PLSA. According to the independence assumption, these parameters remain valid for documents out of the training set. On the other hand, the aspect distribution P(z k |d i ) is only relative to the specific documents and cannot carry any prior information to an unseen image. This distribution, however, can represent each training image as a K-dimension vector. In addition, all the vectors can construct a simplex. Then, by making use of the aspect distribution and original annotation labels of each training image, we build a series of classifiers in which every word in the vocabulary is treated as an independent class. This is the discriminative learning stage. At this time, every image is represented as an aspect distribution, but has several semantic labels. This circumstance is in conformity with multi-label learning, which can construct multiclass classifiers and integrate correlative information of textual words at the same time. image. After each image in the database is annotated, the retrieval algorithm ranks the images labeled with the query word by decreasing confidence.

Ensembles of Classifier Chains

In discriminative learning stage, we employ ensembles of classifier chains [START_REF] Read | Classifier chains for multi-label classification[END_REF] to accomplish the task of multi-label classification. Each binary classifier is implemented with SVM in classifier chains. Having taken the correlation between semantic labels into consideration, this approach can classify images into several semantic classes and it has higher confidence with acceptable computation complexity. The classifier chain model involves |L| binary classifiers, where L denotes the label set. Classifiers are linked along a chain where each classifier deals with the binary relevance problem associated with label l j L. The feature space of each link in the chain is extended with the 0/1 label associations of all previous links. The training procedure is described in Algorithm 1. Note the notation for a training example (x, S), where S L and x is an instance feature vector. Hence a chain C 1 , C 2 , …, C j of binary classifiers is formed. Each classifier C j in the chain is responsible for learning and predicting the binary association of label l j given the feature space, augmented by all prior binary relevance predictions in the chain l 1 , l 2 , …, l j-1 . The classification process begins at C 1 and propagates along the chain: C 1 determines Pr(l 1 |x) and every following classifier C 2 , …, C j predicts Pr(l j |x i , l 1 , l 2 , …, l j-1 ). This classification procedure is described in Algorithm 2. This training method passes label information between classifiers, allowing classifier chain take into account label correlations and thus overcoming the label independence problem of binary relevance method. However, classifier chain still remains advantages of binary relevance method including low memory and runtime complexity.

The order of the chain itself clearly has an effect on accuracy. This problem can be solved by using an ensemble framework with a different random train ordering for each iteration. Ensemble of classifier chains trains m classifiers C 1 , C 2 , …, C m . Each C k is trained with a random chain ordering of L and a random subset of D. Hence each C k model is likely to be unique and able to give different multi-label predictions. These predictions are summed by label so that each label receives a number of votes. A threshold is used to select the most popular labels which form the final predicted multi-label set.

Experimental Results

In order to test the effectiveness and accuracy of the proposed approach, we conduct our experiments on an annotated image data set which was originally used in [START_REF] Duygulu | Object recognition as machine translation: learning a lexicon for a fixed image vocabulary[END_REF]. The dataset consists of 5000 images from 50 Corel Stock Photo cds. Each cd includes 100 images on the same topic. We divided this dataset into 3 parts: a training set of 4000 images, a validation set of 500 images and a test set of 500 images. The validation set is used to determine system parameters. After fixing the parameters, we merged the 4000 training set and 500 validation set to form a new training set. This corresponding to the training set of 4500 images and the test set of 500 images used by [START_REF] Duygulu | Object recognition as machine translation: learning a lexicon for a fixed image vocabulary[END_REF].

Parameters Setting

An important parameter of the experiment is the number of latent aspects for the PLSA-based models. Since the number of latent aspects defines the capacity of the modelthe number of model parameters, it can determine the training time and system efficiency to a large extent. We choose three aspect numbers (90, 120 and 150) to do experiments. Through a series of experiments, we found that the system performs better when aspect number is 150. Therefore, we use 150 as aspect number, without ruling out the possibility that another aspect number would make the system performs much better. Furthermore, our approach constructs an ensemble including 90 classifier chains. Each classifier chain randomly chooses a subset of 500 images for training. The focus of this paper is not on image feature selection and our approach is independent of visual features. So our prototype system uses similar features to [START_REF] Feng | Multiple Bernoulli relevance models for image and video annotation[END_REF] for easy comparison. We simply decompose images into a set of blocks (the size of each block is empirically determined as 16×16 through a series of experiments on the validation set), then compute a 36 dimensional feature vector for each block, consisting of 24 color features (auto correlogram computed over 8 quantized colors and 3 Manhattan Distances) and 12 texture features (Gabor energy computed over 3 scales and 4 orientations). As a result, each block is represented as a 36 dimension feature vector. Then each image is represented as a bag of features, that is, a set of 36 dimension vectors. All the feature vectors of training images compose the inputs of continuous PLSA. Therefore, this preprocessing procedure provides a uniform interface for continuous PLSA modeling.

Results of Automatic Image Annotation

In this section, the performance of our approach is compared with some state-of-theart approachesthe Translation Model [START_REF] Duygulu | Object recognition as machine translation: learning a lexicon for a fixed image vocabulary[END_REF], CMRM [START_REF] Jeon | Automatic image annotation and retrieval using crossmedia relevance models[END_REF], CRM [START_REF] Lavrenko | A model for learning the semantics of pictures[END_REF], MBRM [START_REF] Feng | Multiple Bernoulli relevance models for image and video annotation[END_REF], PLSA-WORDS [START_REF] Monay | Modeling semantic aspects for cross-media image indexing[END_REF] and SML [START_REF] Carneiro | Supervised learning of semantic classes for image annotation and retrieval[END_REF]. We evaluate the performance of image annotation by comparing the captions automatically generated with the original manual annotations. Similarly to [START_REF] Lavrenko | A model for learning the semantics of pictures[END_REF], we compute the recall and precision of every word in the test set and use the mean of these values to summarize the system performance. We report the results on two sets of words: the subset of 49 best words and the complete set of all 260 words that occur in the training set. The systematic evaluation results are shown in table 1. From the table, we can see that our approach performs significantly better than all other approaches. We believe that using hybrid framework to learn semantic classes is the reason for this result. Several examples of annotation obtained by our prototype system are shown in Table 2. Here top five words are taken as annotation of the image. We can see that even the system annotates an image with a word not contained in the ground truth, this annotation is frequently plausible.

Results of Ranked Image Retrieval

In this section, mean average precision (mAP) is employed as a metric to evaluate the performance of single word retrieval. We only compare our model with CMRM, CRM, MBRM, PLSA-WORDS and SML, because mAP of the Translation model cannot be accessed directly from the literatures. The annotation results ignore rank order. However, users always like to rank retrieval images and hope that the top ranked ones are relative images. In fact, most users do not want to see more than even 10 or 20 images in a query. Therefore, rank order is very important for image retrieval. Given a query word, our system will return all the images which are automatically annotated with the query word and rank the images according to the posterior probabilities of that word. Table 3 shows that our hybrid approach performs better than other models. In summary, the experiment results show that our approach outperforms some state-of-the-art approaches in many respects, which proves that the continuous PLSA and our hybrid approach is effective in modeling visual features and learning semantic classes of images.

Conclusion

In this paper, we have proposed continuous PLSA to model continuous quantity and develop an EM-based iterative procedure to estimate the parameters. Furthermore, we present a hybrid generative/discriminative approach, which employs continuous PLSA to deal with the visual features and uses ensembles of classifier chains to learn semantic classes of images. Experiments on the Corel dataset prove that our approach is promising for automatic image annotation and retrieval. In comparison to some state-of-the-art approaches, higher accuracy and superior effectiveness of our approach are reported.

  the model in terms of a graphical model is depicted in Figure1.

Fig. 1 .

 1 Fig. 1. Graphical model representation of continuous PLSA.

Fig. 2 .

 2 Fig. 2. Learning procedure of hybrid framework.

Algorithm 1 . 4 .

 14 Training procedure of classifier chainInput: Example set D= {(x 1 , S 1 ), (x 2 , S 2 ), …, (x n , S n )}. Output: Classifier chains {C 1 , C 2 , …, C |L| }. for (x, S) D 5. do D' ← D ((x, l 1 , l 2 , …, l j-1 ), l j ) ' 6. Train Cedict binary relevance of l j j to pr 7. C j : D' l j {0, 1}

Algorithm 2 . 3 .

 23 Classifying procedure of classifier chain Input: Test example x. Outpu sults of all classifiers in the chain Y = { l 1 , l 2 , …, l |L| }. do Y Y (l j C j : (x, l 1 , l 2 , …, l j-1 )) 2. for j , 2 , 4. return (x, Y)

Table 1 .

 1 Performance comparison on the task of automatic image annotation.

	Models	Translation	CMRM	CRM	MBRM	PLSA-WORDS	SML	Hybrid Approach
	#words with recall > 0	49	66	107	122	105	137	137
		Results on 49 best words, as in [7,8,10,11]
	Mean Recall	0.34	0.48	0.70	0.78	0.71	-	0.83
	Mean Precision	0.20	0.40	0.59	0.74	0.56	-	0.78
			Results on all 260 words
	Mean Recall	0.04	0.09	0.19	0.25	0.20	0.29	0.32
	Mean Precision	0.06	0.10	0.16	0.24	0.14	0.23	0.28

Table 2 .

 2 Comparison of annotations made by PLSA-WORDS and hybrid approach.

	Image
	Ground truth	grizzly, bear, meadow, grass	head, fox, snow, closeup	trees, sky, frost, ice	sand, water, peo-ple, sky
	Annotations of PLSA-WORDS	bear, grizzly, horse, meadow, sand	clouds, sky, stone, sculpture, rabbit	grass, desert, ice, path, sculpture	beach, iceburg, snow, ice, water
	Annotations of hybrid approach	bear, grizzly, grass, meadow, trees	fox, snow, sky, head, clouds	sky, trees, branch, ice, grass	water, sky, beach, people, snow

Table 3 .

 3 Comparison of mAPs in ranked image retrieval.

	Models	CMRM CRM MBRM PLSA-WORDS	SML	Hybrid Approach
	All 260 words	0.17	0.24	0.30	0.22	0.31	0.35
	Words with recall ≥ 0	0.20	0.27	0.35	0.26	-	0.41
	Words with recall > 0	-	-	-	0.55	0.49	0.67

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Nos. 61165009, 60903141, 61105052), the Guangxi Natural Science Foundation (2012GXNSFAA053219) and the "Bagui Scholar" Project Special Funds.


Tianlong Yun

Wenjia Niu

Xinghua Yang

Hui Tang

Song Ci

Frequency-Adaptive Cluster Head Election in Wireless Senor Network

Keywords: Wireless Sensor Networks, network context, frequency adaptive, clustering

Efficient information routing mechanism is a critical research issue for wireless sensor networks (WSN) due to the limit energy and storage resource of sensor nodes. The clustering-based approaches (e.g. LEACH, Gupta and CHEF) for information routing have been developed. Although these approaches did actually improve the routing efficiency and prolong the network lifetime, the clustering frequency f is usually pre-designed and fixed. However, the network context (e.g. Energy and load) often dynamically changes, which can provide the dynamical adjustment determination for f. Hence, in this paper, we propose a frequency-adaptive cluster-head election approach, which applies the network context for making corresponding f adjustment. Furthermore, an fbased clustering algorithm is presented as well. The case study and experimental evaluations demonstrate the effectiveness of the proposed approach.

Introduction

The rapid development of wireless sensor network (WSN) enables the information gathering from many physical environments [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF][START_REF] Yick | Wireless sensor network survey[END_REF]. In WSN, sensor nodes usually have very limited energy and memory space, but they are densely deployed to guarantee the reliability of sensing. The typical structure of a sensor network includes base station and a lot of homogeneous node [START_REF] Sohrabi | Protocols for self-organization of a wireless sensor network[END_REF]. In this structure, base station is in charge of initiating data requests and all the sensor node should communicate with base station to make the sensing data delivered. In order to reduce the overhead, some nodes will act as storage nodes and receive the data request for other common nodes in their vicinity [START_REF] Ghose | Resilient Data-Centric Storage in Wireless Ad-Hoc Sensor Networks Mobile Data Management[END_REF], then compress the data request result from many nodes and send it to the base station. This method has reduced some energy consumption, however, ''hotspot'' problem may be generated [START_REF] Perillo | An analysis of strategies for mitigating the sensor network hot spot problem[END_REF][START_REF] Shnayder | Simulating the power consumption of large-scale sensor network applications[END_REF]. More specifically, one storage node will not be replaced by other high-energy storage node or even common node. Hence, some storage node will run out its energy and dies at an early stage, which will further affect the data transmission to the base station and effective sensing in some area.

Recently, to solve the hotspot problem, clustering based technique has begun to be used. Typical work involves the LEATH [START_REF] Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF], Gupta [START_REF] Indranil | Cluster-head election using fuzzy logic for wireless sensor networks[END_REF] and CHEF [START_REF] Jong-Myoung | Cluster Head Election mechanism using Fuzzy logic in Wireless Sensor Networks[END_REF]. In these methods, storage node will be replaced by new node which has more energy. The other nodes will select a storage node as their agent so that they don't have to communicate with base station directly. In all of these methods, clustering is done periodically. A completed operation of clustering for one time is called "round". All of the nodes will have to act as storage node sooner or later at some rounds and all of these methods can effectively utilize the overall energy of the sensor network.

However, in such methods, we think that a new round of clustering didn't always happen at a proper time. All of them have a fixed frequency of clustering so that a large amount of energy has been wasted because of the unnecessary re-clustering. For instance, in a WSN-based intelligent building application, the sensing frequency of temperature at working hours should be higher than that at off-duty hours. We will analysis a specific scenario to demonstrate the disadvantage of traditional method. First, we assume that clustering is performing faster than it should be. As we mention above, at off-duty hours when there are barely any data request, the frequency of clustering should be slow down. Otherwise, the new storage node will be elected anyway even if the energy distribution is still balanced. Another situation is that the frequency of clustering is lower than it should be. In this case, the change of network context cannot be utilized immediately. A storage node could run out its energy before the next round of clustering. Hence, in this paper, we propose a re-clustering frequencyadaptive routing approach which utilizes the current network context to achieve effective load balance between all the nodes. Our efforts mainly focus on two aspects: firstly, we define a function to determine when to start a new round of clustering for cluster-head election; secondly, based on this function, we design a corresponding algorithm to improve node's energy consuming.

The rest of the paper is organized as follows. Section 2 discusses the related work, followed by the proposed approach in Section 3. Section 4 presents experimental results that illustrate the benefits of the proposed scheme. Section 5 concludes the paper.

Related Work

Our approach has inspired by a variety of related work, the most famous one is the LEATH. In this approach, the author not only put forward the method itself, but also a completed clustering protocol for WSN. To better distribute the energy consumption among the nodes, LEACH employs a stochastic model which will select several nodes from the network to act as the storage node. The elected storage node is also called as cluster head. The cluster head will then advertise message and all of the other nodes will keep their receiver on to receive the advertisement. The common nodes will choose the cluster head which is nearest to them. Then the common nodes will notice the cluster head it joins. After the cluster head confirms its entire cluster member, it will build a schedule to tell the common node the time to transfer the data. Finally when the cluster gathers all the data of its member, it will compress it and send data packets to the base station. This method is fully distributed and the base station didn't have to involve in the clustering process. The nodes will generate the random number by themselves. And CSMA will be used to prevent the congestion when nodes exchange the message [START_REF] Dam | An adaptive energy-efficient MAC protocol for wireless sensor networks[END_REF]. No This method improves the use of the overall energy but didn't take the network context into consideration. Based on this method, Gupta has put forward a method using fuzzy logic. Three descriptor, energy, concentration and centrality of fuzzy logic are used to better balance the energy consumption. The process of the clustering is conducted in the base station while the CHEF think it is inefficient. CHEF improves Gupta's method by combining the LEATH and Gupta together as well as making the method distributed. Each node will first generate a random number to determine whether or not to elect for a cluster head. The node whose random number is lower than the pre-designed threshold will then do the fuzzy logic calculation, and some of them will be selected as cluster head (See Table .

1).

Although above methods have prolonged the lifetime of the network, the clustering frequency is often fixed. Hence, we try making the clustering frequency dynamically changed based on network context, and aim to achieve better energy consumption.

Cluster-Head Election Model

In this paper, we propose an approach which can be aware of the data request frequency and then adjust the corresponding clustering frequency f. We call this approach frequency-adaptive cluster-head election. The aim of our approach is to balance and reduce the energy consumption by dynamically change the re-clustering frequency. The proposed clustering method is executed by the base station because it is not sensitive to energy consumption. At the initial state, all the cluster head will be assigned randomly. And later, the base station will only communicate with the cluster head for requesting data while other nodes will update their sensing data to their cluster head periodically. When it comes to the re-clustering part, the base station will query the energy information of all the nodes, and let the old cluster head pass their token to the new cluster head [START_REF] Akkaya | A survey on routing protocols for wireless sensor networks[END_REF]. The operation of our method breaks into several rounds. The first round has slightly different because there is no cluster head existing for base station to communicate with. Prior to detail approach description, we present the network organization.

Network Organization

The WSN network consists of plenty of sensor nodes and a base station which is located far away from the nodes (See Fig. 1). In our approach, we assume that all the sensor nodes are deployed in a square zone. The sensors themselves are homogenous and stationary. The base station will obtain the geographic locations of all the nodes using GPS technology [START_REF] Mao | Wireless sensor network localization techniques[END_REF]. Some nodes will be assigned as storage nodes which will in charge of communicating with the base station. The storage node will be initiated by clustering method based on the position and energy level of them. The new storage node will be assigned at another round of clustering while the happen time of the clustering is highly adaptive and dynamic.

Fig. 1. The network organization of the method

System Architecture

Both the base station and the sensor node have their own system architecture. We will start with the description of the base station. The base station is in charge of initiating a data request, communicating with sensor node and doing clustering. Fig. 2 shows that there are five modules in the base station for clustering. Interface with application layer module will communicate with the application layer to get the need for sensing data and data request module will The structure of the storage node is less complicated (See Fig. 2 (b)). Both sender and receiver are necessary parts for any node. For the storage node, it also maintains all the information of the member node and a calculation module which can be used to generate the index of changed nodes.

The Election Process

For the first round of clustering, some node have to be selected as the initial cluster head randomly based on the model in LEATH. First, all of the nodes will generate a random number between 0 and 1. If the number is less than a pre-designed chance parameter P, the percentage of storage nodes in the network, the node will elect itself as cluster head.

Then the elected cluster head should broadcast a notification message for other common nodes. All of the common node which its random number is higher than P should keep their receiver on. These common nodes should also count the number of the advertisement. Once the number exceeds h, the pre-designed cluster amount, it will choose the strongest one as its cluster head. Then the common node will send an answer message, in this time, the storage nodes must keep their receiver on. At the end, all of the storage nodes will have a sheet which includes the ID of all the members and the sheet will be sent back to the base station.

The description above is only applicable for the first time clustering. If there already some cluster heads exist, the cluster process will be different. The new round of clustering in base station is triggered by specific events that we will describe the algorithm to get the specific event in following part. Once the clustering event is triggered, the base station will send a notice to the entire old storage node. And the old storage node will notify its member node to ask for the energy level of them.

The common nodes will return their remaining energy level to the storage node and cluster head will return the information back to the base station. The base station will do the calculation which will be described specifically in the following fuzzy logic clustering controller part. After that, the base station will determine the new cluster head as well as its member nodes and will send messages to the old storage node with the index of new storage node and the member nodes they should include. And the old storage node will transfer its "head token" and the message from the base station to the new one.

The new storage node has to advertise its state as well. However, this advertisement will include the ID of its member node and the common node doesn't have to answer with another message because the storage already has the corresponding sheet. The index for the new storage node will only include the changed member node. So that the overhead is reduced but the old storage should do some extra computation.

When the agent in application layer inquiry some data based on the need of service, the inquiry will be sent to the base station. After identifying the data request, the base station will look up the matching table to check which node should be checked and the corresponding storage node. Finally, the base station will directly get the data from the target storage node.

The calculation of the new cluster head uses the fuzzy logic controller [START_REF] Ross | Front Matter[END_REF][START_REF] Haining | Wireless Sensor Network Lifetime Analysis Using Interval Type-2 Fuzzy Logic Systems[END_REF]. The controller has two descriptors: energy (the energy remain of the node) and distance (the sum of distances between the node and the nodes which is within r distance).A node has more chance to be selected as storage node if the value of the two descriptors is high. After the fuzzy logic operation, the base station will only notice the old storage node with index of nodes which have been changed.

A new round of cluster operation is triggered by specific events. The specific event will be defined as follows: A counter will count the incoming data request amount. Once the amount exceeds the threshold of the counter, a new round of clustering will start. The threshold of the counter is determined by the energy level of the overall network (The base station is aware of the energy level of each node, although it is delayed). Because the storage node is more likely to run out of its energy at a short time if the whole network is at a low energy level, so the next round of clustering should happen in time. Base on the overall remain energy and variance, counter threshold (T) for round t is showed below (k is a constant value depends on the network; N is the cluster number; X ij is remain energy level of each node): )

it t it it X T k X X N ∑ = ∑ -∑ (1)
Preliminaries : N: the number of clusters; Ci: cluster i(i = 0, Our approach prevents the demerit we found in LEATH and other fuzzy logicbased approach at some specific situation. First, remain energy is used to balance the energy consumption of the nodes. Then, it is reasonable that the new round of clustering is based on the amount of incoming data request.

Experimental Evaluations

In previous sections, we have described the structure and method of our method. In this section, we will do some experiment and validate the effectiveness of the proposed approach. We implement the proposed method using MATLAB fuzzy control tool box and we use similar environment setup assumptions to test it to compare its performance with former methods. The basic structure is built upon the LEATH protocol. In order to be compared to the energy consumption with former typical method, we use the energy consumption assumption in LEATH, CHEF and Gupta. And we deployed 400 nodes into in 200*200 areas. The simulation time will be divided into several periods, in the peak periods, there are more data requests from the base station while in other periods, the frequency of data request is relatively low. And the data request obeys Poisson distribution.

Having collected 100 sets of data, we can see a slight improvement in the lifetime of the network if the incoming data request is largely depended on time (See Fig. 4 (a)). However, if the data request is stable, the network lifetime of our approach is shorter than CHEF but still longer than LEACH. Also we can compare another important parameter ∆T, the difference between the dead time of the first node and the last node. We can find that the time difference in our approach is shorter than the former method LEATH and CHEF. The first node fails at the 513rd round and the last node fail at the 678th round so that the ∆T for out method is 165 rounds. The ∆T for LEATH and CHEF is 203 and 187 respectively. This result shows that the energy consumption has a balanced distribution which is good because the intact network has a better performance. If some node fails at a early stage, the sensing cannot be performed in the corresponding zone.

Conclusion

This paper extends the existing clustering method to prolong the lifetime of WSN at some specific situation. The proposed approach can reduce energy consumption when major fluctuations exist in the data request frequency. This improvement is realized by making the clustering frequency f flexible. We put forward a simple but effective method with adaptive clustering frequency adjusting to better utilize and balance the overall energy of all the nodes. In addition, although most of the computation is carried on the base station, the message transmitted between node and the base station can be controlled at a reasonable level at the same time. The simulation result shows that our approach is a meaningful and a reasonable attempt for the improvement in fuzzy logic based approach. In the future, we will focus on extending our method so that it can be used for more complex situations.

Fig. 2 .

 2 Fig. 2. The architecture of the Base Station(a) and Storage Node(b) coordinate with other module to finish the data request task; interface with the node module will communicate with the nodes to get the sensing data and clustering information; the database module will maintain the data of the nodes and request result; the clustering module will conduct the calculation of the clustering.

Fig. 3 .

 3 Fig. 3. Network Lifetime in Time-depend (a) and Stable (b) situationAlso we can compare another important parameter ∆T, the difference between the dead time of the first node and the last node. We can find that the time difference in our approach is shorter than the former method LEATH and CHEF. The first node fails at the 513rd round and the last node fail at the 678th round so that the ∆T for out method is 165 rounds. The ∆T for LEATH and CHEF is 203 and 187 respectively. This result shows that the energy consumption has a balanced distribution which is

Table 1 .

 1 Characteristic between the 3 methods

		LEACH	Gupta	CHEF
	Clustering Method	Stochastic	Fuzzy Logic	Fuzzy Logic
	Base Station process	No	Yes

Acknowledgements

This research is supported by the National Natural Science Foundation of China (No. 61103158), the National S\&T Major Project (No. 2010ZX03004-002-01), the Deakin CRGS 2011 and the Securing CyberSpaces Research Cluster of Deakin University, the Sino-Finnish International S\&T Cooperation and Exchange Program (NO. 2010DFB10570), the Strategic Pilot Project of Chinese Academy of Sciences (No.XDA06010302), and the Ultra-realistic Acoustic Interactive Communication on Next-Generation Internet (No. 11110036).