Developers have began to wrap desired functionalities into widgets based on Web 2.0 techniques on mobile devices. Demand for these light-weight Web applications is expected to grow rapidly in near future. Since a widgets can be recognized as a unit providing a speci¯c service, from the perspective of choreography, this paper adapts widgets into a mobile Peer-to-Peer (P2P) environment and proposes a light weight group discovery approach to assist service discovery based on domain ontologies and semantic clustering. Latent Semantic Indexing (LSI) and Singular Value Decomposition (SVD) are employed and assist our approach in building up a Knowledge Base (KB) on each peer. This approach can prune the service search space and trigger the initial formation of peer communities. Its performance is also assessed via simulation results. A framework for porting widgets to di®erent widget engines has been designed, making use of the above ontologies, and a basic widget transformation platform is implemented and tested in a case study.
A widget is a light-weight Web application, which can be used to implement a
single function and access to Internet with Web 2.0 techniques. At time of this
writing, there is no uni¯ed de¯nition for a widget and di®erent organizations
gave diverse descriptions for this kind of Web application, such as widget [
Each widget or mobile application can be treated as a unit providing a
speci¯c service. Several solutions [
The remainder of the paper is organized as follows. Section 2 present related work. Section 3 illustrates the P2P network structure for mobile widget sharing. Section 4 presents our light-weight group discovery approach and gives a choreography-based solution for widget searching. Section 5 describes a framework for porting widgets to di®erent widget engines. Section 6 discusses our group discovery approach through a simulation and gives a case study of widget transformation. Section 7 concludes the paper and outlines our future directions. 2
Widgets, created based on standard Web 2.0 techniques, are becoming widely
used on mobile devices day by day. Due to the traditional structure of the
mobile network, bandwidth and widgets provided are both limited by servers in
a centralized network. It is therefore interesting to explore if a P2P
environment that caters to the user's needs could be designed and applied to widget
sharing. One of the core problems of adapting P2P architectures and Sematic
Web techniques to mobile devices is how to cope with the computational costs.
Orchestration and choreography are two perspectives from which researches
currently investigate Web Services. The former describes the behaviors of a single
peer and the latter describes a service system in a top view manner. Focusing on
orchestration, several approaches have been proposed for applying semantics to
Web Services, such as OWL-S [
Moreover, limited computation capability of the mobile device also hampers the progress of service description strategies.
At time of this writing, there are two transformation tools for widgets in di®erent formats as follows: Amnesty Generator and Widgetop. Amnesty Generator gives a way of transforming from Google Gadget, GrazrRSSreader and YouTube video to gadgets in the side bar. Widgetop is a Web desktop service based on AJAX techniques using the MAC UI style. However, these two tools both have their limitations. Amnesty Generator can only transform from Google Gadgets to gadgets running in the side bar of Window Vista and Widgetop can only transform from Apple Dashboard widgets to Web widgets. 3
The overall P2P network structure for widgets sharing among mobile devices is depicted in Figure 1. In this ¯gure, each peer has an operating system, a PAMP bundle, a KB including an RDF repository and widget ontologies, and a searching UI. The ontologies and UI are provided and updated by a peer that plays the provider role. Here, we also assume that this role can assure that the exchanging process is quick and secure. When a requester asks for a widget, based on his or her inputs, several groups will be established based on the approach described in Section 4. Then IMs will be invoked as a protocol between peers in a group until all members are searched. Then the searched widgets, regarded as candidates, will be returned to the original requester. Meanwhile, these candidates are sorted by the values of their rank properties descendingly. Finally, the requester decides which widgets will be downloaded. 4
In order to e±ciently search for required widgets on peers, a possible strategy is discovering a peer group that can prune the search space for each query. A group is a collection of peers that have common interests. In this section, we present our approach for clustering peers into groups. Suppose each peer holds an RDF snippet that describes all the widgets holden by itself. This RDF snippet can describe the relevant properties of each widget such as its URL, title, publisher, platform, categories, size, rank and so on. Due to the heterogeneity of widget properties described by di®erent Web sites, we de¯ned widget domain ontologies that will be introduced in Section 5. So it is unnecessary diverse Web sites use a generic ontology vocabulary to describe their issued widgets but just o®er their matchmakers. After being mapped, the aliases will be uni¯ed by speci¯c prede¯ned concepts in widget ontologies. Based on these ontologies and a speci¯c matchmaker, the RDF snippets could be automatically generated from a widget publication page in virtue of information extraction techniques. Finally, all the installed widgets on each peer are described by a single RDF ¯le that forms its pro¯le and will be stored in its local repository.
If an RDF snippet is matched with the requirer's query, the host peer will
provide its address for download. Alternatively, the peer can provide the original
URL of the widget on another peer from which it downloaded this widget before
in case the peer has removed this widget but still retained the old version of
the RDF repository. By analyzing the widgets on Widgipedia3, we assume that
features and descriptions are capable of indicating the functionalities of widgets
and the peers that a requester originally wants to contact are previously recorded
in its contact list. For instance, widget °ickrstrator has following features:
article, blog, °ash, °ickr, images, photo, random, and web. Given these assumption,
we present our group discovery process including feature extraction, dimension
reduction, group-name extraction and peer distribution as follows:
-Feature Extraction. Several methods have been proposed for selecting
document features. Taking e±ciency and limited computation resources into
consideration, we use a Vector Space Model (VSM) to model the features of peers by
querying the RDF repository on each peer. From the following query described
in SPARQL [
WHERE f ?wi rdf:type wp:WidgetInfo. ?wi wp:feature ?feature.
?wi wp:description ?description.g According to VSM, each peer can be denoted by a feature vector with n dimensions: (®w1 ¢ tfw1 ; ®w2 ¢ tfw2 ; :::; ®wn ¢ tfwn ), where n denotes the number of values for node \feature" in the local repository, tfwi denotes the frequency of the ith values and ®i denotes the weighting factor of the ith value. We use the inverse document frequency, denoted by idfwi , as the weighting values so the feature vector can be denoted by (tfw1 ¢ idfw1 ; tfw2 ¢ idfw2 ; :::; tfwn ¢ idfwn ). Here, idfwi = log(N=dfwi + 0:01), where dfwi is the document frequency that denotes the number of peers in which the ith value appears, and N denotes the total number of peers in the requester's contact list. The requester's contact list can
be represented by a feature-peer matrix. Here, a feature denotes the value of a
feature node. Suppose there are in total m peers in the contact list and they
contain n di®erent features. Then this contact list can be denoted by a m £ n
matrix M . The row vectors of M are named feature vectors, and the column
vectors of M are named peer vectors. We use the su±x array [
P (¾i2) i=1 s rM
P (¾i2) i=1
> ½ d¤ = dT VkT Sk¡1 Here, rM denotes the rank of matrix M , ¾i denotes the ith singular value, and jjM jjF denotes the Frobenius norm of matrix M . We can map the original feature vectors to a new feature space and ¯nally reduce their dimension by: Here, d denotes the original feature vector of a peer and d¤ denotes the new one after dimension reduction. -Group-Name Extraction. Here, the distance between two feature vectors is calculated by cosine distance. We use this distance to select the most representative name for each group. Since group names may be not only terms but also phrases, we reconstruct a new matrix R with the dimension m £ (r + m), which expresses both terms and phrases in the column space of the feature-peer matrix. Here, r denotes the total number of the phrases in the requester's contact list. After SVD, each column vector of matrix Uk denotes the abstract features of widgets for a peer. We can calculate the cosine distance between a abstract feature vector and a term-and-phrase vector and get the distance matrix D = UkT R. For each row vector, we ¯nd out the maximum score. Its corresponding term or phrase is regarded as a candidate group name. Since a group name should be concise, we should deal with the names which have duplicate semantics. Regarding the candidate names as peers, we construct another feature-peer matrix S with scores as its elements. After length normalization, we can get the matrix containing similarities between candidate names by formula ST S. For each row of this matrix, only the name with the highest score will be retained. The e®ect for this step can be see in Table 2 and Table 3 in Section 6. -Peer Distribution. After above three steps, we can determine the number of groups in the requester's contact list. Then we make all the peers fall into these groups. We de¯ne a matrix P in which each group label is represented by a column vector. Then we can get a clustering matrix C = P T M whose element cij denotes the similarity between the jth peer and the ith group, where M is the original feature-peer matrix. If similarity cij exceeds the prede¯ned distribution threshold distmin, the jth peer will be classi¯ed into the ith group ¯nally. We will further discuss the selection of distmin in Section 6.
When a requester sends out a searching request, the local RDF repository
will be ¯rst searched in order to assure that the requested widget has not been
installed locally. Otherwise, the local server will remind the requester of
overwriting or updating the existing widget or substituting it with a di®erent one. If
the requested widget can not be found locally, the requiring message will be sent
to the peers that are in the same group with the requester. Normally, one peer
may belong to several groups simultaneously, and di®erent groups may have
intersection subgroups. So we should ¯nd out which group of the requester should
be searched ¯rst. On the other hand, if peers in the requester's contact list
belong to more than one group to which the requester also belongs, they will be
searched more than once. In order to avoid overlapping searches, we maintain
a list to record peers that has been searched. The overall searching process is
like the above Peer Distribution process. The query phrase (i.e., the request)
is represented by a feature vector, Q, whose dimension is equal to the
dimension of the feature vector after the Dimension Reduction process. Then we can
get a vector C0 = P T Q whose element Ci0 denotes the similarity between the
query phrase and the ith group. By ranking these similarities descendingly, we
can ¯nd out the most relevant group that should be searched ¯rst. If the found
widgets are not satisfactory, the group with the second highest similarity will be
searched consequently. When the requester adds a new peer in his or her contact
list, the new peer will be ¯rst classi¯ed into an existing group or regarded as a
member of a new group and the local group information will be also updated.
The concrete method is analogous to the above method for matching a query
phrase and will not be described here for the sake of brevity. The above group
discovery approach triggers the formation of peer communities by providing the
basic community seeds. Community is a non-empty set of peers that share a
nonempty set of interests that they have in common [
WHERE f ?peer rdf:type wp:Peer. ?peer foaf:holdsAccount ?user.
?group sioc:has member ?user.g for each peeri from ?peer
SELECT ?friend WHERE f ?friend rdf:type wp:Peer. peeri foaf:knows ?friend
g
Peer is a unit that is capable of achieving speci¯c goals. From the perspective of
choreography discussed in Section 2, peers collaborate with each other through
interactions. We use Lightweight Coordination Calculus (LCC) to describe these
interactions. LCC is a language used for describing the interactions between
peers and supporting decentralized systems [
An requester, R, sends out a message to a potential widget advertiser, A, in order to retrieve required widgets, Widgets; then A sends back a message to R and transfers the found widgets to R. The set W idgets contains all the widgets that R wants to retrieve. A receives the message containing the R's required widgets; then A changes role to being the advertiser over the set W idgets and ¯nds out if A contains the widgets in W idgets; then all the found widgets are saved into set F ound and sent back to R. F ound is a set containing all the found widgets required by R. The advertiser A searches for a widget, W , in turn from the set W idgets; then if W is found in A's local widget repository, W will be added in set F ound; otherwise, W will be ignored. a(requester; R) :: require(W idgets) ) a(advertiser; A) à need(W idgets)then transf er(F ound) ( a(advertiser; A) a(advertiser; A) :: require(W idgets) ( a(requester; R)then a(advertiser(W idgets; [ ]; F ound); S)then transf er(F ound) ) a(requester; R) a(advertiser(W idgets; BuildU p; F ound); S) :: null à W idgets = [ ] ^ F ound = BuildU p or 0 a(requester(WR; new; F ound); S) à W idgets = [W jWR] ^ f ind(W; WF ) ^ add 1 BB@ (WFo;rBuildU p; N ew) ACC a(advertiser(WR; N ew; F ound); S) à W idgets = [W jWR] ^ not(f ind(W; WF ))
Fig. 2. Widget retrieving IM
In Table 1, we can see that each type of the widget contains a
con¯guration ¯le, a main ¯le and several JavaScript ¯les. Although requesters can use
the group discovery approach and the IM described in Section 4 to search other
peers and ¯nd out the expected widget with formats they support, usually the
widget publishers, especially independent developers, do not provide multiple
versions of their widgets. In this section, we propose an automatic transforming
framework based on domain ontologies, see in Figure 3. This process will be also
wrapped in an OKC held by each peer acquiescently. Following this ¯gure, we
now describe the transforming process as follows:
-Template Repository. According to the requester's requirement, the target
template corresponding to a target widget is ¯rst selected. A Template is a kind
of description that depicts the ¯le buildup, the naming method, the
con¯guration ¯le and the main ¯le of a widget with a speci¯c format.
-Unpacking and Packing Modules. We use java.util.zip package included in
JDK for unpacking and packing widget ¯les.
-Preprocessing Module. This module uni¯es formats of main ¯les from
di®erent types of widgets and prepares inputs for the next mapping process. Basically,
there are two types of main ¯les: HTML ¯les and XML ¯les. Here, we use XML
to standardize the format of main ¯les.
-Analyzing Module. This module identi¯es the format of the original widget
by analyzing the ¯le bundle after the unpacking process.
-Mapping Module. This module associates the elements within the original
template with the elements within the target template.
-Updating Module. Our widget ontologies should be updated constantly,
according ontology evolution [
Features-Based
Descriptions-Based 0.2
Though description-based discovery (Table 3) contains 3 more groups than feature-based discovery (Table 2), there are 100 more widgets that can not be grouped in Table 3 than in Table 2. Moreover, some of the GN s in Table 3 are obscure, e.g., Save Time, List and so on. The reason for this is because natural language is more °exible but less uncontrollable and the descriptions are more heterogenous compared to features. We can also see this from Blog and Blog Website in Table 3, which actually have the same meaning. Feature-based group discovery outperforms description-based group discovery. According to Table 2, 627 peers, accounting for 36.56% of the contact peers, ¯nally fall into other group. They do not associate with other peers very well. Studying the RDF snippets, we ¯nd that most of them use unusual words (or phrases) to describe their features. Moreover, a few of them lack feature information or are very badly tagged using just one or two unrepresentative words (or phrases).
For the format transformation part, we take a widget with unknown format as an example and give a case study of changing it to Nokia S60 widget supported by Symbian 60 Feature Pack 2. Needless to say, the target template should be the one for Nokia S60 widgets. After being unpacked, the original widget is converted to a bundle of ¯les. This bundle contains a con¯guration ¯le named info.plist whose content will be compared to the templates in the template repository. Then the original format will be identi¯ed by the comparison result, e.g., a Dashboard widget. The Mapping Module uses our widget ontologies to associate the elements in the original ¯les with the ones in the target template. For example, the property CFBundleIdenti¯er from a Dashboard widget is corresponding to the property Identi¯er from a Nokia S60 widget and the property CFBUndleVersion from a Dashboard widget is corresponding to the property Version from a Nokia S60 widget. Based on the above semantic alignments, the values in the original widget are ¯lled in the target template in the end. Sometimes, the corresponding target elements will not be found after the mapping process and this means the target widget engine does not have these functionalities that the original widget engine has. In this case, these elements will be ignored by the Mapping Module. Alternatively, this kind of elements can be made up manually. Under this circumstance, our transformation approach will still save a great deal of manpower. Figure 5 illustrates the transformation from a prevailing Dashboard widget iStatpro (top sub¯gure) to a widget running on Nokia S60 FP2 (bottom sub¯gure). Within the process of creating onologies, we do our best to guarantee the °exibility and extendability of the hierarchy. The We propose an approach for sharing and reusing widgets between mobile devices and also adapt it in P2P environment. Based on domain ontologies and semantic clustering, a light-weight group discovery approach is presented for pruning the search space and cutting down the bandwidth limited by each peer. We also propose a framework for transforming widgets with diverse formats and give a case study to demonstrate it. After being grouped, a peer can more e±ciently ¯nd others that have similar interests with itself in the pruned search space. Also, these basic groups trigger the initial formation of the peer community. Any peer can invite friends who have similar interests to join its group and then bene¯t the overall community. Our future work includes adding multilanguage support within group discovery. A peer ranking approach should be applied to our widget transferring process for possibly enhancing the widget search. In order to expedite search, generated RDF ¯les should be indexed, which is also a challenge. Currently we are working on the evolvement of discovered groups, including peer-membership update (entering or leaving a group) and group merging.
The research has been supported by the Open Knowledge project (FP6-027253).