Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2010.03.013 Byline: Josephina Antoniou (a), Vicky Papadopoulou (b), Vasos Vassiliou (a), Andreas Pitsillides (a) Keywords: Next generation networks; Access network selection; Game theory; Cooperative games; Present value Abstract: Next Generation Communication Networks employ the idea of convergence, where heterogeneous access technologies may coexist, and a user may be served by anyone of the participating access networks, motivating the emergence of a Network Selection mechanism. The triggering and execution of the Network Selection mechanism becomes a challenging task due to the heterogeneity of the entities involved, i.e., the users and the access networks. This heterogeneity results in different and often conflicting interests for these entities, motivating the question of how they should behave in order to remain satisfied from their interactions. This paper studies cooperative user-network interactions and seeks appropriate modes of behaviour for these entities such that they achieve own satisfaction overcoming their conflicting interests. Author Affiliation: (a) University of Cyprus, Dept. of Computer Science, 75 Kallipoleos Street, P.O. Box 20537, CY-1678 Nicosia, Cyprus (b) European University Cyprus, Dept. of Computer Science, 6, Diogenes Street, P.O. Box 22006, CY-1516 Nicosia, Cyprus Article History: Received 19 May 2009; Revised 28 February 2010; Accepted 25 March 2010 Article Note: (miscellaneous) Responsible Editor: A. Capone

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2010.03.024 Byline: Di Wu (a), Chao Liang (b), Yong Liu (b), Keith W. Ross (c) Keywords: P2P applications; Video streaming Abstract: In current multi-channel P2P live video systems, there are several fundamental performance problems including exceedingly-large channel switching delays, long playback lags, and poor performance for less popular channels. These performance problems primarily stem from two intrinsic characteristics of multi-channel P2P video systems: channel churn and channel-resource imbalance. In this paper, we propose a radically different cross-channel P2P streaming framework, called View-Upload Decoupling (VUD). VUD strictly decouples peer downloading from uploading, bringing stability to multi-channel systems and enabling cross-channel resource sharing. We propose a set of peer assignment and bandwidth allocation algorithms to properly provision bandwidth among channels, and introduce substream-swarming to reduce the bandwidth overhead. We evaluate the performance of VUD via extensive simulations as well with a PlanetLab implementation. Our simulation and PlanetLab results show that VUD is resilient to channel churn, and achieves lower switching delay and better streaming quality. In particular, the streaming quality of small channels is greatly improved. Author Affiliation: (a) Department of Computer Science, Sun Yat-Sen University, Guangzhou 510006, China (b) Department of Electrical and Computer Engineering, Polytechnic Institute of NYU, Brooklyn, NY 11201, United States (c) Department of Computer Science and Engineering, Polytechnic Institute of NYU, Brooklyn, NY 11201, United States

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2010.03.002 Byline: Xiaofeng Lu (a), Pan Hui (b), Don Towsley (c), Juahua Pu (a), Zhang Xiong (a) Keywords: Location privacy; Anti-localization; Anonymous routing; Delay Tolerant Network Abstract: This paper focuses on the problem of how to allow a source to send a message without revealing its physical location and proposes an anti-localization routing protocol, ALAR, to achieve anonymous delivery in Delay/Disruption Tolerant Networks. The objectives of ALAR are to minimize the probability of a data source being localized and to maximize the destination's probability of receiving the message. ALAR can protect the sender's location privacy through message fragmentation and forwarding each segment to different receivers. ALAR is validated on two real-world human mobility datasets. This study indicates that ALAR increases the sender's anonymity performance by over 81% in different adversary densities with a 5% reduction in delivery ratio. Author Affiliation: (a) School of Computer Science, Beijing University of Aeronautics and Astronautics, Xueyuan Road 37, Beijing 100191, China (b) Deutsche Telekom Laboratories and TU-Berlin, Berlin, Germany (c) Department of Computer Science, University of Massachusetts, Amherst, United States Article History: Received 9 April 2009; Revised 19 December 2009; Accepted 1 March 2010 Article Note: (miscellaneous) Responsible Editor: J. Misic

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2010.02.013 Byline: Bheemarjuna Reddy Tamma (a), Anirudh Badam (b), C. Siva Ram Murthy (c), Ramesh R. Rao (a) Keywords: Ad hoc wireless networks; Video multicasting; Multicast trees; Path-diversity; Multiple description coding Abstract: In this paper, we address the problem of video multicast over Ad hoc wireless networks. Multicasting is an efficient means of one-to-many communication and is typically implemented by creating a multicast tree. Video multicasting demands high quality of service with a continuous delivery to receivers. However, most of the existing multicast solutions do not guarantee this because they are not resilient to mobility of the nodes and do not exploit error-resilient nature of recently available video coding techniques. Uninterrupted video transmission requires continuous reachability to receivers which emphasizes the usage of path-diversity. Hence, we propose a multiple tree multicast protocol which maintains maximally node-disjoint multicast trees in the network to attain robustness against path breaks. We further enhance the robustness by using the error-resilient multiple description coding (MDC) for video encoding. We prove that finding a given number of node-disjoint multicast trees for a multicast session in a given network is NP-Hard. Then we propose a protocol called K-Tree which maintains the maximal node-disjointedness property of K trees by using a distributed online heuristic. Through extensive simulation experiments, we show how the proposed protocol improves the video quality as we use two or three trees instead of a single tree for multicasting video stream. We also show, through simulations, that the protocol efficiently, in terms of overhead, provides high quality video as compared to an existing two tree video multicast protocol and a well known mesh-based multicast protocol. Author Affiliation: (a) California Institute for Telecommunications and Information Technology, University of California San Diego, CA 92093, USA (b) Department of Computer Science, Princeton University, NJ 08544, USA (c) Department of Computer Science and Engineering, Indian Institute of Technology Madras, TN 600036, India Article History: Received 16 July 2008; Revised 5 February 2010; Accepted 24 February 2010 Article Note: (miscellaneous) Responsible Editor: Prof. Qian Zhang

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.10.025 Byline: Yumei Huo (a), Joseph Y.-T. Leung (b) Keywords: Nested processing set restrictions; Nonpreemptive scheduling; Makespan; NP-hard; Approximation algorithm; Worst-case bound Abstract: We consider the problem of scheduling a set of n independent jobs on m parallel machines, where each job can only be scheduled on a subset of machines called its processing set. The machines are linearly ordered, and the processing set of job j is given by two machine indexes a.sub.j and b.sub.j; i.e., job j can only be scheduled on machines a.sub.j,a.sub.j+1,...,b.sub.j. Two distinct processing sets are either nested or disjoint. Preemption is not allowed. Our goal is to minimize the makespan. It is known that the problem is strongly NP-hard and that there is a list-type algorithm with a worst-case bound of 2-1/m. In this paper we give an improved algorithm with a worst-case bound of 7/4. For two and three machines, the algorithm gives a better worst-case bound of 5/4 and 3/2, respectively. Author Affiliation: (a) Department of Computer Science, CUNY at Staten Island, Staten Island, NY 10314, USA (b) Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA Article History: Received 9 November 2008; Accepted 26 October 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.10.017 Byline: N.M. Mosharaf Kabir Chowdhury (a), Raouf Boutaba (b)(c) Keywords: Network virtualization; Virtual networks; Next-generation Internet architecture Abstract: Due to the existence of multiple stakeholders with conflicting goals and policies, alterations to the existing Internet architecture are now limited to simple incremental updates; deployment of any new, radically different technology is next to impossible. To fend off this ossification, network virtualization has been propounded as a diversifying attribute of the future inter-networking paradigm. By introducing a plurality of heterogeneous network architectures cohabiting on a shared physical substrate, network virtualization promotes innovations and diversified applications. In this paper, we survey the existing technologies and a wide array of past and state-of-the-art projects on network virtualization followed by a discussion of major challenges in this area. Author Affiliation: (a) Electrical Engineering and Computer Sciences, University of California, Berkeley, CA 94702, United States (b) Cheriton School of Computer Science, University of Waterloo, ON, Canada N2L 3G1 (c) Division of IT Convergence Engineering, POSTECH, Pohang KB 790-784, Republic of Korea Article History: Received 3 March 2008; Revised 21 October 2009; Accepted 25 October 2009 Article Note: (footnote) [star] This work was jointly supported by the Natural Science and Engineering Council of Canada (NSERC) under its Discovery program, Cisco Systems, and WCU (World Class University) program through the Korea Science and Engineering Foundation funded by the Ministry of Education, Science and Technology (Project No. R31-2008-000-10100-0).

Byline: Antoine Doucet (1), Helena Ahonen-Myka (2) Keywords: Multiword expressions; Document retrieval; Endogenous resources Abstract: In this paper, we address the problem of the exploitation of text phrases in a multilingual context. We propose a technique to benefit from multi-word units in adhoc document retrieval, whatever the language of the document collection. We present principles to optimize the performance improvement obtained through this approach. The work is validated through retrieval experiments conducted on Chinese, Japanese, Korean and English. Author Affiliation: (1) Department of Computer Science, University of Caen, Caen, France (2) Department of Computer Science, University of Helsinki, Helsinki, Finland Article History: Registration Date: 02/09/2009 Online Date: 03/10/2009

Byline: Helena Medeiros Caseli (1), Carlos Ramisch (2), Maria Gracas Volpe Nunes (3), Aline Villavicencio (2,4) Keywords: Automatic identification; Word alignment; Machine translation; Terminology; Multiword expressions; Lexical acquisition; Statistical methods Abstract: Due to idiosyncrasies in their syntax, semantics or frequency, Multiword Expressions (MWEs) have received special attention from the NLP community, as the methods and techniques developed for the treatment of simplex words are not necessarily suitable for them. This is certainly the case for the automatic acquisition of MWEs from corpora. A lot of effort has been directed to the task of automatically identifying them, with considerable success. In this paper, we propose an approach for the identification of MWEs in a multilingual context, as a by-product of a word alignment process, that not only deals with the identification of possible MWE candidates, but also associates some multiword expressions with semantics. The results obtained indicate the feasibility and low costs in terms of tools and resources demanded by this approach, which could, for example, facilitate and speed up lexicographic work. Author Affiliation: (1) NILC, Department of Computer Science, Federal University of Sao Carlos, Sao Carlos, Brazil (2) Institute of Informatics, Federal University of Rio Grande do Sul, Porto Alegre, Brazil (3) NILC, ICMC, University of Sao Paulo, Sao Carlos, Brazil (4) Department of Computer Science, University of Bath, Bath, UK Article History: Registration Date: 17/07/2009 Received Date: 20/11/2007 Accepted Date: 14/07/2009 Online Date: 14/08/2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.sysarc.2010.03.004 Byline: J.M. Claver (a), P. Agusti (b), M. Arevalillo-Herraez (a), G. Leon (b), M. Canseco (b) Keywords: Computer networks; Quality of Service; FPGA; Handel-C; Performance evaluation Abstract: Nowadays, high performance System and Local Area Networks (SAN/LAN) have to serve heterogeneous traffic consisting of information flows with different bandwidth and latency requirements. This makes it necessary to provide Quality of Service (QoS) and optimize the design of network components. In this paper we present a hardware tool designed to analyze the performance of QoS networks, under given traffic conditions and server models. In particular, a reprogrammable multimedia traffic Generator/Monitor platform has been built. This permits prototyping the communication system of a high speed LAN/SAN on a single FPGA device. Hence, it can be used at design to produce more efficient devices. To illustrate the applicability of the platform we have used the Simple Multimedia Router (SMMR), an existing proposal to provide QoS. The modular structure of the tool and the fact that it has been implemented on an FPGA using a high level hardware programming language makes it flexible, scalable and easy to reconfigure. Besides, the architecture and implementation can be adapted to be used in more recent QoS NoC environments. Author Affiliation: (a) Dept. of Computer Science, Universidad de Valencia, 46100 Burjassot, Spain (b) Dept. of Computer Science and Eng., Universitat Jaume I, 12008 Castellon, Spain Article History: Received 28 July 2009; Revised 28 January 2010; Accepted 21 March 2010 Article Note: (footnote) [star] This work has been jointly supported by the Spanish MEC and MICINN, as well as European Commission FEDER funds, under grants "Consolider Ingenio-2010 CSD2006-00046", "Consolider Ingenio 2010 CSD2007-00018", and "TIN2009-14475-C04".

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.10.042 Byline: Jung-Sing Jwo (a), Yu Chin Cheng (b) Keywords: Software requirements models; Models as mediators; Ontology of models; Learning from models Abstract: A new synthesis of software requirements models called pseudo software is proposed with the aim to cut requirements-related errors. Pseudo software achieves this aim by serving as a mediating instrument to empower stakeholders to participate in requirements elicitation and validation through model construction and manipulation, and to provide guidance to the development team to correctly interpret the requirements in the downstream development activities. Pseudo software obtains its traits as a mediating instrument through the choice of requirements information bits and the use of multimodal representations with tool support to integrate the requirements. Using historical data of fifty projects in the enterprise computing domain, pseudo software is shown to effectively cut the requirements-related errors committed by both the customer and the development team. Author Affiliation: (a) Department of Computer Science and Information Engineering, Tunghai University, 181, Section 3, Taichung Port Road, Situn District, Taichung 407, Taiwan (b) Department of Computer Science and Information Engineering, National Taipei University of Technology, 1, Section 3, Chung-Hsiao East Road, Taipei 106, Taiwan Article History: Received 7 August 2008; Revised 27 October 2009; Accepted 29 October 2009 Article Note: (footnote) [star] A preliminary version of this paper was presented in the 14th Asia-Pacific Software Engineering Conference (APSEC 2007), Nagoya, Japan.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.robot.2009.11.001 Byline: Otar Akanyeti (a), IA[+ or -]aki RaA[+ or -]o (b), Ulrich Nehmzow (c), S.A. Billings (d) Abstract: Previously we presented a novel approach to program a robot controller based on system identification and robot training techniques. The proposed method works in two stages: first, the programmer demonstrates the desired behaviour to the robot by driving it manually in the target environment. During this run, the sensory perception and the desired velocity commands of the robot are logged. Having thus obtained training data we model the relationship between sensory readings and the motor commands of the robot using ARMAX/NARMAX models and system identification techniques. These produce linear or non-linear polynomials which can be formally analysed, as well as used in place of 'traditional robot' control code. In this paper we focus our attention on how the mathematical analysis of NARMAX models can be used to understand the robot's control actions, to formulate hypotheses and to improve the robot's behaviour. One main objective behind this approach is to avoid trial-and-error refinement of robot code. Instead, we seek to obtain a reliable design process, where program design decisions are based on the mathematical analysis of the model describing how the robot interacts with its environment to achieve the desired behaviour. We demonstrate this procedure through the analysis of a particular task in mobile robotics: door traversal. Author Affiliation: (a) School of Computer Science and Electronic Engineering, University of Essex, UK (b) Department of Computer Science and Systems Engineering, University of Zaragoza, Spain (c) School of Computing and Intelligent Systems, University of Ulster, UK (d) Department of Automatic Control and Systems Engineering, University of Sheffield, UK

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.09.004 Byline: Abdul Hasib (a), Abraham O. Fapojuwo (b) Keywords: Heterogeneous wireless network; Network selection; Call admission control; Performance analysis Abstract: This paper proposes a mobility adaptive network selection scheme in the context of wireless wide area network (WWAN) and wireless local area network (WLAN) radio access technologies (RATs) that supports both real-time (RT) and non-real-time (NRT) service classes. Physical layer information based call admission control (CAC) is considered for the two RATs to enforce service specific QoS requirements. The effectiveness of the cross-protocol-layer information for radio resource management (RRM) in integrated WWAN and WLAN networks is assessed analytically for individual service classes in a multi-service environment using the theory of Markov chains. The impact of non-uniform user and mobility distributions due to the existence of hotspot in the macro-cell area and the effect of network selection parameter measurement errors on the RRM performance are also evaluated. Numerical results show that the proposed network selection scheme minimizes the rate of unnecessary vertical handoffs, thereby providing stable communication without degrading the call blocking probability and call outage probability performance metrics. Author Affiliation: (a) Dept. of Elect. Engg. and Computer Science, North South University, Dhaka-1212, Bangladesh (b) Dept. of Elect. and Computer Engineering, The University of Calgary, Calgary, Alberta, Canada Article History: Received 6 November 2008; Revised 23 May 2009; Accepted 11 September 2009 Article Note: (miscellaneous) Responsible Editor: E. Gregori

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.09.008 Byline: Satish Chand (a), Hari Om (b) Keywords: Fast broadcasting scheme; Staircase scheme; Seamless channel transition; Video channel Abstract: Video applications require large amount of bandwidth and also storage space. The Fast Broadcasting (FB) scheme is one of the simplest schemes to provide video services, but it requires considerably large buffer storage. This scheme assumes constant video popularity and thus has fixed amount of bandwidth requirement. The popularity of videos generally does not remain the same. It varies over a period of time and accordingly the bandwidth allocation should be adjusted. The variability in bandwidth requirement for videos based on popularity is overcome by incorporating seamless channel transition mechanism in a broadcasting scheme. After incorporating seamless channel transition mechanism, the scheme still delivers continuous video data to old and new users without jerks and hiccups. The FB scheme with seamless channel transition mechanism requires less buffer storage than the FB scheme. The staircase scheme also allocates a fixed amount of bandwidth to a video. The FB and staircase schemes divide a video into same number of segments; thus have same user's waiting time. The basic difference between the FB and staircase schemes is that in the staircase scheme the segments are further divided into subsegments in order to reduce the buffer requirement. To consider variability of video popularity in the staircase scheme, seamless channel transition for staircase (SCTS) scheme has been discussed. The SCTS scheme performs better than the seamless Fast Broadcasting scheme as regard the buffer storage, while maintaining the same user's waiting time. In this paper, we propose an efficient staircase scheme with seamless channel transition mechanism that performs better than the SCTS scheme. In the proposed scheme, the video (ESS scheme) data is downloaded at slower rate than that in the SCTS scheme without disrupting the user services and requiring less buffer storage. Author Affiliation: (a) Computer Engineering Division, Netaji Subhas Institute of Technology, Sector-3, Dwarka, New Delhi 110 078, India (b) Department of Computer Science and Engineering, Indian School of Mines University, Dhanbad 826 004, India Article History: Received 15 September 2008; Revised 23 June 2009; Accepted 18 September 2009 Article Note: (miscellaneous) Responsible Editor: N. Agoulmine

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.09.037 Byline: W. Eric Wong (a), Vidroha Debroy (a), Byoungju Choi (b) Keywords: Fault localization; Program debugging; Code coverage; Heuristics; Suspiciousness of code; Successful tests; Failed tests Abstract: Locating faults in a program can be very time-consuming and arduous, and therefore, there is an increased demand for automated techniques that can assist in the fault localization process. In this paper a code coverage-based method with a family of heuristics is proposed in order to prioritize suspicious code according to its likelihood of containing program bugs. Highly suspicious code (i.e., code that is more likely to contain a bug) should be examined before code that is relatively less suspicious; and in this manner programmers can identify and repair faulty code more efficiently and effectively. We also address two important issues: first, how can each additional failed test case aid in locating program faults; and second, how can each additional successful test case help in locating program faults. We propose that with respect to a piece of code, the contribution of the first failed test case that executes it in computing its likelihood of containing a bug is larger than or equal to that of the second failed test case that executes it, which in turn is larger than or equal to that of the third failed test case that executes it, and so on. This principle is also applied to the contribution provided by successful test cases that execute the piece of code. A tool, IDebug, was implemented to automate the computation of the suspiciousness of the code and the subsequent prioritization of suspicious code for locating program faults. To validate our method case studies were performed on six sets of programs: Siemens suite, Unix suite, space, grep, gzip, and make. Data collected from the studies are supportive of the above claim and also suggest Heuristics III(a), (b) and (c) of our method can effectively reduce the effort spent on fault localization. Author Affiliation: (a) Department of Computer Science, University of Texas at Dallas, TX 75083, USA (b) Department of Computer Science and Engineering, Ewha womans University, Republic of Korea Article History: Received 3 March 2009; Revised 27 July 2009; Accepted 22 September 2009 Article Note: (footnote) [star] This research was supported by the MKE (Ministry of Knowledge Economy), Korea, under the ITRC (Information Technology Research Center) support program supervised by the NIPA (National IT Industry Promotion Agency) (NIPA-2009-(C1090-0902-0032)).

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.compeleceng.2009.04.002 Byline: Wei Lu (a), Hongtao Lu (b), Fu-Lai Chung (c) Keywords: Image watermarking; Feature detection; Image normalization Abstract: This paper presents a robust watermarking scheme based on feature point detection and image normalization. Firstly some stable feature points are detected from the original image using the proposed multiresolution feature point detection filter. Then, image normalization is applied to the disks centered at these feature points. The watermark is embedded in the subband coefficients of DFT domain of each disk separately. And the watermark detection uses the correlation between the watermark embedding coefficients and the original watermark, and does not need the original image. The proposed scheme combines the advantages of feature point detection and image normalization, which can achieve strong robustness to signal processing and geometrical distortions. The experimental results also demonstrate good performance of the proposed scheme. Author Affiliation: (a) School of Information Science and Technology, Guangdong Key Laboratory of Information Security Technology, Sun Yat-sen University, Guangzhou 510275, China (b) Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China (c) Department of Computing, Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong Article History: Received 5 June 2007; Revised 3 November 2008; Accepted 16 April 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.06.008 Byline: Jihyun Lee (a), Jeong-Hoon Park (a), Myung-Jae Park (a), Chin-Wan Chung (a), Jun-Ki Min (b) Keywords: Distributed query processing; Semantic mapping; Query optimization; Distributed ontologies; Semantic Web Abstract: In this paper, we propose an intelligent distributed query processing method considering the characteristics of a distributed ontology environment. We suggest more general models of the distributed ontology query and the semantic mapping among distributed ontologies compared with the previous works. Our approach rewrites a distributed ontology query into multiple distributed ontology queries using the semantic mapping, and we can obtain the integrated answer through the execution of these queries. Furthermore, we propose a distributed ontology query processing algorithm with several query optimization techniques: pruning rules to remove unnecessary queries, a cost model considering site load balancing and caching, and a heuristic strategy for scheduling plans to be executed at a local site. Finally, experimental results show that our optimization techniques are effective to reduce the response time. Author Affiliation: (a) Division of Computer Science, Department of Electronic Engineering and Computer Science, Korea Advanced Institute of Science and Technology (KAIST), Daejon 305-701, Republic of Korea (b) School of Internet-Media Engineering, Korea University of Technology and Education, Byeongcheon-Myeon, Cheonan, Chungnam 330-708, Republic of Korea Article History: Received 30 October 2008; Revised 30 March 2009; Accepted 7 June 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.07.050 Byline: Min-Shiang Hwang (a), Song-Kong Chong (b), Te-Yu Chen (c) Keywords: ID-based scheme; Client puzzles; Password authentication; Resources exhaustion attack; Smart card Abstract: In this paper, we provide a defense mechanism to Kim-Lee-Yoo's ID-based password authentication scheme, which is vulnerable to impersonation attacks and resource exhaustion attacks. Mutual authentication and communication privacy are regarded as essential requirements in today's client/server-based architecture; therefore, a lightweight but secure mutual authentication method is introduced in the proposed scheme. Once the mutual authentication is successful, the session key will be established without any further computation. The proposed defense mechanism not only accomplishes the mutual authentication and the session key establishment, but also inherits the security advantages of Kim-Lee-Yoo's scheme, e.g. it is secure against password guessing attacks and message replay attacks. Author Affiliation: (a) Department of Management Information Systems, National Chung Hsing University, 250 Kuo Kuang Road, Taichung 402, Taiwan, ROC (b) Department of Computer Science and Information Engineering, National Cheng-Kung University, 1 University Road, Tainan 701, Taiwan, ROC (c) Department of Computer Science and Engineering, National Chung Hsing University, 250 Kuo Kuang Road, Taichung 402, Taiwan, ROC Article History: Received 21 July 2007; Revised 5 July 2009; Accepted 31 July 2009

Byline: Donghong Ji (1), Shiju Zhao (2), Guozheng Xiao (3) Keywords: Term extraction; Term weighting; Maximal marginal relevance; Document re-ranking; Information retrieval Abstract: In this paper, we address the problem of document re-ranking in information retrieval, which is usually conducted after initial retrieval to improve rankings of relevant documents. To deal with this problem, we propose a method which automatically constructs a term resource specific to the document collection and then applies the resource to document re-ranking. The term resource includes a list of terms extracted from the documents as well as their weighting and correlations computed after initial retrieval. The term weighting based on local and global distribution ensures the re-ranking not sensitive to different choices of pseudo relevance, while the term correlation helps avoid any bias to certain specific concept embedded in queries. Experiments with NTCIR3 data show that the approach can not only improve performance of initial retrieval, but also make significant contribution to standard query expansion. Author Affiliation: (1) Department of Computer Science, Center for Study of Language Information, Wuhan University, 430072, Wuhan, China (2) Department of Chinese Language and Literature, Wuhan University, 430072, Wuhan, China (3) Center for Study of Language Information, Wuhan University, 430072, Wuhan, China Article History: Registration Date: 03/10/2009 Online Date: 13/11/2009 Article note: First author is supported by NSF (60773011), NSF(90820005), and first two authors are supported by Wuhan University 985 Project (985yk004).

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cl.2008.08.002 Byline: Ana M. Roldan (a), Ernesto Pimentel (b), Antonio Brogi (c) Abstract: Nowadays, tuple spaces have turned out to be one of the most fundamental abstractions for coordinating communicating agents. Some models, as Linda, were presented as a set of inter-agent communication primitives which can virtually be added to any programming language. These models have the advantage of capturing both communication and synchronization in a natural and simple way. In this paper, we analyze the use of Linda to specify the interactive behavior of software components. We first introduce a process algebra for Linda and we define a notion of process compatibility that ensures the safe composition of components. This definition of compatibility takes into account the state of a global store (tuple space), which gives relevant information about the current execution of the system. Indeed, a Linda-based computation is characterized by the store's evolution, so that the set of tuples included into the store governs each computation step. In particular, we prove that compatibility implies successful computation (i.e. without deadlock). We also argue that Linda features some advantages with respect to similar proposals in the context of dynamic compatibility checking. In this context, the success of the composition of a pair of agents in presence of a suitable store can be useful to condition the acceptance of a given component into an open running system. In order to extend our approach to complex systems, where constructing a system involves more than two components, we propose the use of distributed tuple spaces as the glue to join components. Author Affiliation: (a) Department of Computer Science, University of Huelva, Spain (b) Department of Computer Science, University of Malaga, Spain (c) Department of Computer Science, University of Pisa, Italy Article History: Received 5 October 2006; Revised 21 July 2008; Accepted 27 August 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cl.2008.08.001 Byline: Zhi-jie Li (a)(b)(c), Chun-tian Cheng (b), Fei-xue Huang (d) Keywords: Resource allocation; Utility function; Computational grid; GridSim Abstract: Optimal resource allocation is a complex undertaking due to large-scale heterogeneity present in computational grid. Traditionally, the decision based on certain cost functions has been used in allocating grid resource as a standard method that does not take resource access cost into consideration. In this paper, the utility function is presented as a promising method for grid resource allocation. To tackle the issue of heterogeneous demand, the user's preference is represented by utility function, which is driven by a user-centric scheme rather than system-centric parameters adopted by cost functions. The goal of each grid user is to maximize its own utility under different constraints. In order to allocate a common resource to multiple bidding users, the optimal solution is achieved by searching the equilibrium point of resource price such that the total demand for a resource exactly equals the total amount available to generate a set of optimal user bids. The experiments run on a Java-based discrete-event grid simulation toolkit called GridSim are made to study characteristics of the utility-driven resource allocation strategy under different constraints. Results show that utility optimization under budget constraint outperforms deadline constraint in terms of time spent, whereas deadline constraint outperforms budget constraint in terms of cost spent. The conclusion indicates that the utility-driven method is a very potential candidate for the optimal resource allocation in computational grid. Author Affiliation: (a) Department of Computer Science and Engineering, Dalian University of Technology, Dalian 116024, Liaoning, PR China (b) Institute of Hydropower System and Hydroinformatics, Dalian University of Technology, Dalian 116024, Liaoning, PR China (c) Research Institute of Nonlinear Information Technology, Dalian Nationalities University, Dalian 116600, China (d) Department of Economics, Dalian University of Technology, Dalian 116024, Liaoning, PR China Article History: Received 10 August 2006; Revised 15 August 2008; Accepted 23 August 2008 Article Note: (footnote) [star] This work is supported by the National Natural Science Foundation of China under Grant no. 50479055.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.compeleceng.2008.09.005 Byline: Qiang Dong (a), Xiaofan Yang (a), Juan Zhao (b) Keywords: Interconnection network; Generalized honeycomb torus; Hamiltonian cycle; Fault-tolerance; Parallel computing Abstract: Generalized honeycomb torus (GHT) is recognized as an attractive alternative to existing torus interconnection networks in parallel computing systems. Assume that m and d are integers with m [greater than or equal to]2 and d [greater than or equal to]8. This paper addresses the fault-tolerant hamiltonicity of GHT(m, 2d, d) with fault set F ={(w, y), (x, y)}, where w < x, w + y is even and x + y is odd. We show that such a faulty GHT is hamiltonian by presenting a systematic method for constructing a fault-free hamiltonian cycle. This result reveals another appealing feature of GHTs. Author Affiliation: (a) College of Computer Science, Chongqing University, Chongqing 400044, China (b) Department of Foreign Language, Aba Teachers College, Aba 623000, China

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.compeleceng.2008.11.019 Byline: Ling Wang (a), Hui Song (a), Yingtao Jiang (b), Lihong Zhang (c) Keywords: Interconnect; Mesh; Routing; Network-on-chip; SoC Abstract: In this paper, we present a routing algorithm that combines the shortest path routing and adaptive routing schemes for NoCs. In specific, routing follows the shortest path to ensure low latency and low energy consumption. This routing scheme requires routing information be stored in a series of routing tables created at the routers along the routing path from the source to the destination. To reduce the exploration space and timing cost for selecting the routing path, a routing list and routing table for each node are created off-line. Routing table is updated on-line to reflect the dynamic change of the network status to avoid network congestion. To alleviate the high hardware implementation cost associated with the routing tables, a method to help reduce the size of the routing tables is also introduced. Compared to the existing routing algorithms, the experimental results have confirmed that the proposed algorithm has better performance in terms of routing latency and power consumption. Author Affiliation: (a) Department of Computer Science and Technology, Harbin Institute of Technology, #715, Harbin 150001, PR China (b) Department of Electrical and Computer Engineering, University of Nevada, Las Vegas, USA (c) Electrical and Computer Engineering, Faculty of Engineering and Applied Science, Memorial University of Newfoundland, Canada

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.10.001 Byline: Rong Qu (a), Edmund K. Burke (a), Barry McCollum (b) Keywords: Adaptive; Exam timetabling; Graph colouring; Graph colouring heuristics; Hybridisation; Hyper-heuristic Abstract: In this paper, we present a random iterative graph based hyper-heuristic to produce a collection of heuristic sequences to construct solutions of different quality. These heuristic sequences can be seen as dynamic hybridisations of different graph colouring heuristics that construct solutions step by step. Based on these sequences, we statistically analyse the way in which graph colouring heuristics are automatically hybridised. This, to our knowledge, represents a new direction in hyper-heuristic research. It is observed that spending the search effort on hybridising Largest Weighted Degree with Saturation Degree at the early stage of solution construction tends to generate high quality solutions. Based on these observations, an iterative hybrid approach is developed to adaptively hybridise these two graph colouring heuristics at different stages of solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme on developing computer methods to design and adapt heuristics automatically. Experimental results on benchmark exam timetabling and graph colouring problems demonstrate the effectiveness and generality of this adaptive hybrid approach compared with previous methods on automatically generating and adapting heuristics. Indeed, we also show that the approach is competitive with the state of the art human produced methods. Author Affiliation: (a) Automated Scheduling, Optimisation and Planning (ASAP) Group, School of Computer Science, University of Nottingham, Wollaton Road, Nottingham NG8 1BB, UK (b) School of Computer Science, Queens University, University Road, Belfast BT7 1NN, N. Ireland, UK Article History: Received 15 August 2006; Accepted 8 October 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.09.022 Byline: Wenyin Gong, Zhihua Cai Keywords: Multiobjective optimization; Differential evolution algorithm; Pareto-adaptive I[micro] -dominance; Orthogonal design method Abstract: Evolutionary multiobjective optimization has become a very popular topic in the last few years. Since the 1980s, various evolutionary approaches that are capable of searching for multiple solutions simultaneously in a single run have been developed to solve multiobjective optimization problems (MOPs). However, to find a uniformly distributed, near-complete, and near-optimal Pareto front in a small number of fitness function evaluations (NFFEs) is a challenging task for any multiobjective optimization evolutionary algorithm (MOEA). In this paper, we present an improved differential evolution algorithm to MOPs that combines several features of previous evolutionary algorithms in a unique manner. It is characterized by (a) employing the orthogonal design method with quantization technique to generate the initial population, (b) adopting an archive to store the nondominated solutions and employing the new Pareto-adaptive I[micro]-dominance method to update the archive at each generation, (c) storing the extreme points and inserting them into the final archive in order to remedy one of the limitations of I[micro]-dominance: the loss of the extreme points in the final archive, and (d) using a hybrid selection mechanism in which a random selection and an elitist selection are alternated in order to allow using the archive solution to guide the search towards the Pareto-optimal front. Experiments have been conducted on a number of unconstrained real-valued artificial functions of two and three objectives. The results prove the efficiency of our approach with respect to the quality of the approximation of the Pareto-optimal front and the considerable reduction of NFFEs in these test problems. By examining the selected performance metrics, our approach is found to be statistically competitive with five state-of-the-art MOEAs in terms of keeping the diversity of the individuals along the tradeoff surface, finding a well-approximated Pareto-optimal front and reducing the computational effort. Author Affiliation: School of Computer Science, China University of Geosciences, Wuhan 430074, PR China Article History: Received 17 October 2007; Accepted 22 September 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.09.015 Byline: Jie Zhu, Xiaoping Li, Qian Wang Keywords: No-wait; Job shop; Timetabling; Sequencing Abstract: In this paper, no-wait job shop problems with makespan minimization are considered. It is well known that these problems are strongly NP-hard. The problem is decomposed into the sequencing and the timetabling components. Shift timetabling is developed for the timetabling component. An effective method, CLLM (complete local search with limited memory), is presented by integrating with shift timetabling for the sequencing component. Experimental results show that CLLM outperforms all the existing effective algorithms for the considered problem with a little more computation time. Author Affiliation: School of Computer Science and Engineering, Southeast University, 210096 Nanjing, PR China Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, 210096 Nanjing, PR China Article History: Received 19 October 2007; Accepted 16 September 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cl.2008.04.002 Byline: Hai-Feng Guo (a), Gopal Gupta (b) Abstract: Due to their highly declarative nature and efficiency, tabled logic programming systems have been applied to solving many complex problems. Tabled logic programming is essential for extending traditional logic programming with tabled resolution. In this paper, we propose a new tabled resolution scheme, called dynamic reordering of alternatives (DRA) resolution, for definite logic programs. The scheme keeps track of the type of the subgoals during resolution; if the subgoal in the current resolvent is a variant of a former tabled subgoal, tabled answers are used to resolve the subgoal; otherwise, program clauses are used similar to SLD resolution. Program clauses leading to variant subgoals at runtime are dynamically reordered for further computation until the subgoals are completely evaluated. DRA resolution allows query evaluation to be performed in a depth-first, left-to-right traversal order similar to Prolog-typed SLD resolution, thus yielding a simple technique for incorporating tabled resolution in traditional logic programming systems. We show the correctness of DRA resolution. Author Affiliation: (a) Department of Computer Science, University of Nebraska at Omaha, Omaha, NE 68182-0500, USA (b) Department of Computer Science, University of Texas at Dallas, Richardson, TX 75083-0688, USA Article History: Received 10 October 2006; Accepted 5 April 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.04.043 Byline: Sang-Uk Jeon (a), Jang-Eui Hong (b), In-Gwon Song (a), Doo-Hwan Bae (a) Keywords: MPSoC; Embedded software; Platform independent model; Platform specific model; UML; Task allocation Abstract: In this paper, we describe a technique to design UML-based software models for MPSoC architecture, which focuses on the development of the platform specific model of embedded software. To develop the platform specific model, we define a process for the design of UML-based software model and suggest an algorithm with precise actions to map the model to MPSoC architecture. In order to support our design process, we implemented our approach in an integrated tool. Using the tool, we applied our design technique to a target system. We believe that our technique provides several benefits such as improving parallelism of tasks and fast-and-valid mapping of software models to hardware architecture. Author Affiliation: (a) Division of Computer Science, College of Information Science and Technology, KAIST, Republic of Korea (b) School of Electrical and Computer Engineering, Chungbuk National University, Cheongju, Republic of Korea Article History: Received 15 September 2007; Revised 20 April 2009; Accepted 22 April 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.05.002 Byline: Yang Xiao (a), Yanping Zhang (a), Miao Peng (a), Hui Chen (b), Xiaojiang Du (c), Bo Sun (d), Kui Wu (e) Keywords: Wireless sensor network; Randomized scheduling algorithm; Coverage; Intrusion object; Energy consumption; Two-dimensional; Three-dimensional Abstract: We are interested in wireless sensor networks which are used to detect intrusion objects such as enemy tanks, cars, submarines, etc. Since sensor nodes have a limited energy supply, sensor networks are configured to put some sensor nodes in sleep mode to save energy. This is a special case of a randomized scheduling algorithm. Ignored by many studies, an intrusion object's size and shape are important factors that greatly affect the performance of sensor networks. For example, an extremely large object in a small sensor field can easily be detected by even one sensor node, no matter where the sensor node is deployed. The larger an intrusion object is, the fewer sensor nodes that are required for detection. Furthermore, using fewer sensor nodes can save resources and reduce the waste of dead sensor nodes in the environment. Therefore, studying coverage based on intrusion object's size is important. In this paper, we study the performance of the randomized scheduling algorithm via both analysis and simulation in terms of intrusion coverage intensity. In particular, we study cases where intrusion objects occupy areas in a two-dimensional plane and where intrusion objects occupy areas in a three-dimensional space, respectively. We also study the deployment of sensor nodes when intrusion objects are of different sizes and shapes. First, sensor nodes are deployed in a two-dimensional plane and a three-dimensional space with uniform distributions. Then, they are deployed in a two-dimensional plane and a three-dimensional space in two-dimensional and three-dimensional Gaussian distributions, respectively. Therefore, our study not only demonstrates the impact of the size and shape of intrusion objects on the performance of sensor networks, but also provides a guideline on how to configure sensor networks to meet a certain detecting capability in more realistic situations. Author Affiliation: (a) Dept. of Computer Science, Univ. of Alabama, United States (b) Dept. of Mathematics and Computer Science, Virginia State Univ., United States (c) Dept. of Computer and Information Sciences, Temple Univ., United States (d) Dept. of Computer Science, Lamar Univ., United States (e) Dept. of Computer Science, Univ. of Victoria, Canada Article History: Received 18 June 2008; Revised 30 April 2009; Accepted 3 May 2009 Article Note: (miscellaneous) Responsible Editor: J. Lopez

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.04.001 Byline: Hung-Min Sun (a), Mu-En Wu (b), M. Jason Hinek (c), Cheng-Ta Yang (d), Vincent S. Tseng (d) Keywords: RSA; CRT; Encryption; Digital signatures; Lattice basis reduction; Cryptanalysis Abstract: In 1982, Quisquater and Couvreur proposed an RSA variant, called RSA-CRT, based on the Chinese Remainder Theorem to speed up RSA decryption. In 1990, Wiener suggested another RSA variant, called Rebalanced-RSA, which further speeds up RSA decryption by shifting decryption costs to encryption costs. However, this approach essentially maximizes the encryption time since the public exponent e is generally about the same order of magnitude as the RSA modulus. In this paper, we introduce two variants of Rebalanced-RSA in which the public exponent e is much smaller than the modulus, thus reducing the encryption costs, while still maintaining low decryption costs. For a 1024-bit RSA modulus, our first variant (Scheme A) offers encryption times that are at least 2.6 times faster than that in the original Rebalanced-RSA, while the second variant (Scheme B) offers encryption times at least 3 times faster. In both variants, the decrease in encryption costs is obtained at the expense of slightly increased decryption costs and increased key generation costs. Thus, the variants proposed here are best suited for applications which require low costs in encryption and decryption. Author Affiliation: (a) Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC (b) Institute of Information Science, Academia Sinica, Taipei, Taiwan, ROC (c) School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada (d) Department of Computer Science and Information Engineering, National Cheng Kung University, Taiwan, ROC Article History: Received 17 October 2008; Revised 1 March 2009; Accepted 4 April 2009 Article Note: (footnote) [star] This is an improved version of .

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.03.008 Byline: Ki Yong Lee (a), Hyojun Kim (b), Kyoung-Gu Woo (b), Yon Dohn Chung (c), Myoung Ho Kim (a) Keywords: Flash-based DBMS; MLC NAND flash memory; Transaction processing Abstract: Recently, Multi-Level Cell (MLC) NAND flash memory is becoming widely used as storage media for mobile devices such as mobile phones, MP3 players, PDAs and digital cameras. MLC NAND flash memory, however, has some restrictions that hard disk or Single-Level Cell (SLC) NAND flash memory do not have. Since most traditional database techniques assume hard disk, they may not provide the best attainable performance on MLC NAND flash memory. In this paper, we design and implement an MLC NAND flash-based DBMS for mobile devices, called AceDB Flashlight, which fully exploits the unique characteristics of MLC NAND flash memory. Our performance evaluations on an MLC NAND flash-based device show that the proposed DBMS significantly outperforms the existing ones. Author Affiliation: (a) Division of Computer Science, KAIST, 373-1 Guseong-Dong, Yuseong-Gu, Daejeon 305-701, Republic of Korea (b) Software Laboratories, Samsung Electronics, 416, Maetan-3Dong, Yeongtong-Gu, Suwon, Gyeonggi-Do 443-742, Republic of Korea (c) Department of Computer Science and Engineering, Korea University, Anam-Dong, Seongbuk-Gu, Seoul 136-701, Republic of Korea Article History: Received 27 August 2008; Revised 5 January 2009; Accepted 5 March 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.02.023 Byline: Suat Ozdemir (a), Yang Xiao (b) Keywords: Secure data aggregation; Survey; Wireless sensor networks Abstract: Wireless sensor networks often consists of a large number of low-cost sensor nodes that have strictly limited sensing, computation, and communication capabilities. Due to resource restricted sensor nodes, it is important to minimize the amount of data transmission so that the average sensor lifetime and the overall bandwidth utilization are improved. Data aggregation is the process of summarizing and combining sensor data in order to reduce the amount of data transmission in the network. As wireless sensor networks are usually deployed in remote and hostile environments to transmit sensitive information, sensor nodes are prone to node compromise attacks and security issues such as data confidentiality and integrity are extremely important. Hence, wireless sensor network protocols, e.g., data aggregation protocol, must be designed with security in mind. This paper investigates the relationship between security and data aggregation process in wireless sensor networks. A taxonomy of secure data aggregation protocols is given by surveying the current "state-of-the-art" work in this area. In addition, based on the existing research, the open research areas and future research directions in secure data aggregation concept are provided. Author Affiliation: (a) Computer Engineering Department, Gazi University, Maltepe, Ankara, TR-06570, Turkey (b) Department of Computer Science, The University of Alabama, Tuscaloosa, AL 35487-0290, United States Article History: Received 8 July 2008; Revised 29 November 2008; Accepted 22 February 2009 Article Note: (footnote) [star] Dr. Ozdemir's work is supported in parts by the Gazi University Scientific Research Project Fund No. 06/2007-44. Prof. Y. Xiao's work is supported in parts by the US National Science Foundation (NSF) under Grants Nos. CCF-0829827, CNS-0716211, and CNS-0737325.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.02.018 Byline: Moonjeong Chang (a), Hyunjeong Lee (b), Meejeong Lee (a) Keywords: Per-application mobility management; Application-specific handover decision; Vertical handover; Cross-layer approach Abstract: With the advance of various wireless access technologies, the demand for a mobile user equipped with multiple air interfaces simultaneously executing diverse applications emerged. In such network environments, per-application mobility management is a key to allow each application of an end user device to dynamically and fully take advantage of the most suitable access technology. In this paper, we devised a comprehensive architectural platform with cross-layer techniques to realize this disruptive technology, i.e., per-application mobility management. The proposed platform enables the triggering of vertical handover decisions based on the dynamic measurements from the entire protocol stack. For per-application, the handover decision as well as the mobility management and the transport/application protocol control adaptation for handover performance optimization are made with cross-layer techniques. Through the simulation results, it is shown that multi-layer handover triggering of the proposed platform enhances the QoS of the application services by making handover decisions when the QoS requirements of an application is not satisfied as well as when a mobile user moves out of the current access network in overlay network environments. It is also presented that per-application handover based on the proposed platform enhances the QoS of the application services compared to the handover approaches which make every on-going service flows handover together to the same access network. Author Affiliation: (a) Dept. of Computer Science and Engineering, Ewha Womans University, 11-1 Daehyun-dong, Seodaemun-gu, Seoul 120-750, Republic of Korea (b) Wireless Communication Lab, Intel, USA Article History: Received 21 January 2008; Revised 4 January 2009; Accepted 23 February 2009 Article Note: (miscellaneous) Responsible Editor: W. Wang

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.02.020 Byline: Sanghyun Yoo (a), Jin Hyun Son (b), Myoung Ho Kim (a) Keywords: Mobile ad hoc networks; Publish/subscribe system Abstract: Since nodes that compose mobile ad hoc networks (MANETs) does not have any prior knowledge about other nodes in many cases, the publish/subscribe communication paradigm that has the decoupling and asynchrony properties can be useful to share information between nodes. Existing publish/subscribe services for MANETs can be categorized into document flooding (DF), destination-based routing (DBR), and content-based routing (CBR). Although those approaches may work well when the size of network is small, all of them suffer from the performance decline as the size of the network increases. In this paper, we compare those approaches, and then propose a scalable publish/subscribe communication scheme in large MANETs by combining DF and CBR hierarchically. Our approach is to cluster all nodes in networks and to exploit CBR and DF for the intra- and inter-cluster communication, respectively. By using this approach, we can effectively utilize benefits of both approaches. Then, we present performance evaluation results which validate our idea with respect to system performance and scalability. Author Affiliation: (a) Division of Computer Science, KAIST, 335 Gwahangno, Yuseong-gu, Daejeon, Republic of Korea (b) Department of Computer Science and Engineering, Hanyang University, 1271 Sa3-Dong, Sangrok-gu, Ansan, Kyunggi-do 426-791, Republic of Korea Article History: Received 8 October 2008; Revised 29 December 2008; Accepted 3 February 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2009.01.012 Byline: Joo Hyuk Jeon (a), Ki Yong Lee (a), Jae Soo Yoo (b), Myoung Ho Kim (a) Keywords: In-network join; Event-detection; Sensor network Abstract: In sensor networks, the event-detection process can be considered as a join of two relations, i.e., a sensor table and a condition table, where a condition table is a set of tuples each of which contains condition information about a certain event. When join operations are used for event-detection, it is desirable, if possible, to perform 'in-network' joins in order to reduce the communication cost. In this paper, we propose an in-network join algorithm, called HIPaG. In HIPaG, a condition table is partitioned into several fragments. Those fragments are stored either in paths from the base station to sensor nodes, or in groups of nodes each of which are within the broadcast range among each other. By distributing a condition table in this way, a distributed join of a sensor table and a condition table can be effectively performed in the network. The experimental results show that our proposed HIPaG works much better than the existing method. Author Affiliation: (a) Division of Computer Science, KAIST, 373-1 Guseong-dong, Yuseong-gu, Daejeon, Republic of Korea (b) School of Electrical and Computer Engineering, Chungbuk National University, 361-763 Gaesin-dong, Heungduk-gu, Cheongju, Chungbuk, Republic of Korea Article History: Received 20 February 2008; Revised 8 December 2008; Accepted 9 January 2009

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.01.008 Byline: Demetrios Zeinalipour-Yazti (a), Zografoula Vagena (b), Vana Kalogeraki (c), Dimitrios Gunopulos (d), Vassilis J. Tsotras (e), Michail Vlachos (f), Nick Koudas (g), Divesh Srivastava (h) Keywords: Distributed Top-K query processing; P2P networks; Sensor networks Abstract: In this paper, we present an algorithm for finding the k highest-ranked (or Top-k) answers in a distributed network. A Top-K query returns the subset of most relevant answers, in place of all answers, for two reasons: (i) to minimize the cost metric that is associated with the retrieval of all answers; and (ii) to improve the recall and the precision of the answer-set, such that the user is not overwhelmed with irrelevant results. Our study focuses on multi-hop distributed networks in which the data is accessible by traversing a network of nodes. Such a setting captures very well the computation framework of emerging Sensor Networks, Peer-to-Peer Networks and Vehicular Networks. We present the Threshold Join Algorithm (TJA), an efficient algorithm that utilizes a non-uniform threshold on the queried attribute in order to minimize the transfer of data when a query is executed. Additionally, TJA resolves queries in the network rather than in a centralized fashion which further minimizes the consumption of bandwidth and delay. We performed an extensive experimental evaluation of our algorithm using a real testbed of 75 workstations along with a trace-driven experimental methodology. Our results indicate that TJA requires an order of magnitude less communication than the state-of-the-art, scales well with respect to the parameter k and the network topology. Author Affiliation: (a) University of Cyprus, Dept. of Computer Science, 75 Kallipoleos Str., P.O. Box 20537, CY-1678, Nicosia, Cyprus (b) Microsoft Research Cambridge, Cambridge, United Kingdom (c) AUEB, Athens, Greece and UC - Riverside, Riverside, CA, United States (d) University of Athens, Athens, Greece (e) UC - Riverside, Riverside, CA, United States (f) IBM Research Zurich, Rueschlikon, Switzerland (g) University of Toronto, Toronto, ON, Canada (h) AT&T Research Labs, Florham Park, NJ, United States Article History: Received 25 March 2008; Revised 25 October 2008; Accepted 12 January 2009 Article Note: (miscellaneous) Responsible Editor: A. Kshemkalyani

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2008.11.846 Byline: Diane Kelly Keywords: Scientific software; Characteristics of scientific software development; Long-term software evolution; Empirical study; Model of change Abstract: One of the characteristics of scientific application software is its long lifetime of active maintenance. There has been little software engineering research into the development characteristics of scientific software and into the factors that support its successful long evolution. The research described in this paper introduces a novel model to examine the nature of change that influenced an example of industrial scientific software over its lifetime. The research uses the model to provide an objective analysis of factors that contributed to long-term evolution of the software system. Conclusions suggest that the architectural design of the software and the characteristics of the software development group played a major role in the successful evolution of the software. The novel model of change and the research method developed for this study are independent of the type of software under study. Author Affiliation: Royal Military College of Canada, Department of Mathematics and Computer Science, Kingston, Ontario, Canada Article History: Received 2 June 2008; Revised 21 November 2008; Accepted 23 November 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.compeleceng.2008.06.001 Byline: Youtao Zhang (a), Jun Yang (b), Lan Gao (c) Keywords: Digital content protection; Secure processor; Group key management Abstract: Due to the explosion of Internet technology in the last decade, there is an increasing demand for secure and effective streaming media protection (SMP) in the new computing environment. Since end users usually have the full control of their machines, pure software based approaches such as user/password validation and group key based content encryption, are not sufficient to defend many attacks, in particular, malicious key sharing. On the other hand, existing hardware-based approaches tend to be too restrictive to adopt. The emerging secure processor designs provide a new direction for hardware assisted streaming media protection (H-SMP). The research in the computer architecture community has shown that secure processors can help to defend various types of attacks such as those with a hijacked and malicious OS. However existing designs focus on securing point-to-point data transfers and face both privacy and performance issues when supporting group-oriented applications, e.g. video on-demand. In this paper, we present privacy-aware secure processor designs for H-SMP against key sharing. We first categorize different protection policies, compare their advantages and disadvantages, and then discuss the novel hardware enhancements including instruction set extensions for supporting these policies. We elaborate the implementation details and present the security and performance analyses. Author Affiliation: (a) Computer Science Department, University of Pittsburgh, Pittsburgh, PA 15260, United States (b) Electrical and Computer Engineering, University of Pittsburgh, Pittsburgh, PA 15261, United States (c) VMware Inc., Palo Alto, CA 94304, United States

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.sysarc.2008.10.006 Byline: M. Sanchez-Elez (a), N. Bagherzadeh (b), R. Hermida (a) Keywords: Reconfigurable Computing; Memory Management; Energy Consumption; Multimedia and DSP applications Abstract: In this paper, we present an approach to the problem of low energy data scheduling for reconfigurable architectures targeting digital signal processing (DSP) and multimedia applications. The main goal is the reduction of the energy consumed by these applications through the integration of the proposed data management framework within a compilation tool specifically conceived for these architectures. Two levels of on-chip data storage are assumed to be available in the reconfigurable architecture. Then, the data manager tries to optimally exploit this storage hierarchy by saving data transfers among on-chip and external memories, so reducing the energy consumption. To do that, specific algorithms for finding the data shared among the different computation kernels of the application have been developed. Also, a data placement and replacement policy has been designed. We also show how an adequate data scheduling could decrease the number of operations required to implement the dynamic reconfiguration of the system. Author Affiliation: (a) Departmento Arquitectura de Computadores y Automatica, Facultad de Informatica, UCM, 28040 Madrid, Spain (b) Department of Electrical Engineering and Computer Science, University of California at Irvine, Irvine, CA 92697, USA Article History: Received 4 February 2008; Revised 20 October 2008; Accepted 29 October 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2008.09.013 Byline: Ai Chen, Dongwook Lee, Prasun Sinha Keywords: Wireless LAN; Association control; Algorithm/protocol design; Algorithm/protocol analysis Abstract: Support for efficient multicasting in WLANs can enable new services such as streaming of TV channels, radio channels, and visitor's information. With increasing deployments of large-scale WLANs, such services can be made available to a large number of users. However, any new multicast based services must minimally impact the existing unicast services which are currently the core services offered by most WLANs. In this paper, we leverage the flexibility of associating with different access-points (APs), which occurs often due to overlapping coverage of APs, to optimize the network's objective. Motivated by different revenue functions and network scenarios, three different optimization objectives are considered which are: maximizing the number of admitted users (MNU), balancing the load among APs (BLA), and minimizing the load of APs (MLA). We show that these problems are NP-hard and present centralized approximation algorithms and distributed approaches to solve them. These algorithms compute which AP a user should be associated with. Using simulations we evaluate their performance and compare them to a naive approach in which users associate to the AP with the best RSSI (Received Signal Strength Indicator). Author Affiliation: Department of Computer Science and Engineering, The Ohio State University, 395 Dreese Laboratories, 2015 Neil Avenue, Columbus, OH 43210-1277, USA Article History: Received 15 January 2008; Revised 15 September 2008; Accepted 16 September 2008 Article Note: (miscellaneous) Responsible Editor A. Capone

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.compeleceng.2008.05.003 Byline: Tzung-Her Chen (a), Wei-Bin Lee (b), Hsing-Bai Chen (b) Keywords: Mobile satellite communication system; Personal communication system; User authentication; Key establishment; Public-key management; Self-verification Abstract: In order to provide an opportunity to make personal communication as broad as possible, mobile satellite communication systems have recently drawn much attention. However, any communication system raises two major challenging issues: (1) how to determine whether actors are whom they claim to be; and (2) how to protect data against unauthorized disclosure. Although the secret-key cryptosystem (SKC) and the public-key cryptosystem (PKC) have been developed to provide well-defined security services to address these issues each has serous drawbacks while SKC-based authentication schemes have the common demerit that the server which maintains the secret-key table becomes an attractive target for numerous intrusions, PKC-based schemes suffer from the expensive complexity of the public-key infrastructure (PKI) and a high computation overhead. Therefore, in this paper, a self-verification authentication mechanism with lower computation and key management cost is introduced. Author Affiliation: (a) Department of Computer Science and Information Engineering, National Chiayi University, 300 University Road, Chia-Yi City 60004, Taiwan, ROC (b) Department of Information Engineering and Computer Science, Feng Chia University, No. 100 Wenhwa Road, Seatwen, Taichung 40724, Taiwan, ROC Article History: Received 30 March 2007; Accepted 29 May 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.sysarc.2008.07.004 Byline: Hyungkeun Song (a), Sukwon Choi (a), Hojung Cha (a), Rhan Ha (b) Keywords: Energy-aware embedded systems; Flash memory file system; JFFS2 Abstract: The JFFS2 file system for flash memory compresses files before actually writing them into flash memory. Because of this, multimedia files, for instance, which are already compressed in the application level go through an unnecessary and time-consuming compression stage and cause energy waste. Also, when reading such multimedia files, the default use of disk cache results in unnecessary main memory access, hence an energy waste, due to the low cache hit ratio. This paper presents two techniques to reduce the energy consumption of the JFFS2 flash file system for power-aware applications. One is to avoid data compression selectively when writing files, and the other is to bypass the page caching when reading sequential files. The modified file system is implemented on a PDA running Linux and the experiment results show that the proposed mechanism effectively reduces the overall energy consumption when accessing continuous and large files. Author Affiliation: (a) Department of Computer Science, Yonsei University, Seodaemun-gu, Shinchon-dong 134, Seoul 120-749, Republic of Korea (b) Department of Computer Engineering, Hongik University, Mapo-gu, Sangsoo-Dong 72-1, Seoul 121-791, Republic of Korea Article History: Received 30 June 2006; Revised 18 April 2008; Accepted 14 July 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2008.08.018 Byline: Wei Wei (a), Bing Wang (a), Chun Zhang (b), Jim Kurose (c), Don Towsley (c) Keywords: Access network classification; Packet pair; Network measurement Abstract: Ethernet, wireless LAN, ADSL, cable modem, and dialup are common access networks that have dramatically different characteristics. Fast and accurate classification of access networks can benefit a wide range of applications. In this paper, we propose a simple and efficient end-to-end scheme to classify access networks into three categories: Ethernet, wireless LAN and low-bandwidth connection. Our scheme is based on the intrinsic characteristics of the various access networks, and utilizes the median and entropy of packet-pair inter-arrival times. Extensive experiments show that our scheme obtains accurate classification results in a very short time (95% accuracy in 2s, with 10 packet pairs). Author Affiliation: (a) Computer Science and Engineering Department, University of Connecticut, Storrs, CT 06269, United States (b) IBM T.J. Watson Research Center, Hawthorne, NY 10532, United States (c) Computer Science Department, University of Massachusetts, Amherst, MA 01003, United States Article History: Received 29 April 2008; Revised 6 August 2008; Accepted 12 August 2008 Article Note: (miscellaneous) Responsible Editor: L.G. Xue

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2008.08.017 Byline: Vijay K. Verma (a), Ramesh C. Joshi (a), Bin Xie (b), Dharma P. Agrawal (b) Keywords: Bloated state; Cloning; Itinerary partitioning; Mobile agent; Network management; Simple network management protocol (SNMP) Abstract: As computer networks increase in size, it is critical to provide efficient and scalable network management. Integration of mobile agents (MAs) with simple network management protocol (SNMP) provides a decentralized network management architecture that overcomes the limitations of the legacy SNMP client/server structure. However, as an MA travels through its itinerary, acquiring the network state at each managed node, its size linearly increases node-by-node and it may be unexpectedly bloated. As a result, a bloated MA will have difficulty in migrating from one node to another. We show that the network response time grows exponentially as the MA size increases linearly. In this paper, we propose a new strategy called itinerary partitioning approach (IPA) that exploits cloning capability of MAs to effectively address this bloated state phenomenon. The analytical model shows the effectiveness of our proposed IPA in terms of network response time. We have implemented the IPA in a practical test-bed network and the results seem to be very encouraging. Author Affiliation: (a) Department of Electronics and Computer Science, Indian Institute of Technology (IIT) - Roorkee, Roorkee, India (b) OBR Center of Distributed and Mobile Computing, Department of Computer Science, University of Cincinnati, Cincinnati, OH 45221, United States Article History: Received 15 August 2006; Revised 9 April 2008; Accepted 4 August 2008

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.sysarc.2008.04.012 Byline: Hao Li (a), Jian Huang (b), Philip Sweany (a), Dijiang Huang (c) Keywords: Field programmable gate array; Elliptic curve cryptography; Tate pairing; Parallel processing; Galois field arithmetic Abstract: Elliptic curve cryptography (ECC) and Tate pairing are two new types of public-key cryptographic schemes that become popular in recent years. ECC offers a smaller key size compared to traditional methods without sacrificing security level. Tate pairing is a bilinear map commonly used in identity-based cryptographic schemes. Therefore, it is more attractive to implement these schemes by using hardware than by using software because of its computational expensiveness. In this paper, we propose field programmable gate array (FPGA) implementations of the elliptic curve point multiplication in Galois field GF(2.sup.283) and Tate pairing computation in GF(2.sup.283). Experimental results demonstrate that, compared with previously proposed approaches, our FPGA implementations of ECC and Tate pairing can speed up by 31.6 times and 152 times, respectively. Author Affiliation: (a) University of North Texas, Department of Computer Science and Engineering, P.O. Box 311366, Denton, TX 76203, USA (b) School of Electrical Engineering and Computer Science, University of Central Florida, 4000 Central Florida Blvd., Orlando, FL 32816, USA (c) Department of Computer Science and Engineering, Arizona State University Tempe, AZ 85287, USA Article History: Received 27 August 2007; Revised 16 April 2008; Accepted 17 April 2008 Article Note: (footnote) [star] Research is supported by Arizona State University Embedded System Consortium (CES) grant #AQS0005.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2007.03.004 Byline: Yunsong Guo (a), Yanzhi Li (b), Andrew Lim (c), Brian Rodrigues (d) Keywords: Production sourcing; Tariffs; Heuristics Abstract: In this paper, we study a multi-stage production sourcing problem where tariff concessions can be exploited at the firm level using free trade agreements between countries. To solve the problem, an algorithm which embeds a very large-scale neighborhood (VSLN) search into a simulated annealing framework is developed. A numerical study is conducted to verify the effectiveness of the solution approach. Author Affiliation: (a) Department of Computer Science, Cornell University, Ithaca, NY 14853, USA (b) Department of Management Sciences, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong (c) Department of IELM, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong (d) Lee Kong Chian School of Business, Singapore Management University, 50 Stamford Road, Singapore 178899, Singapore Article History: Received 14 September 2005; Accepted 21 March 2007

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2006.12.562 Byline: Chulyun Kim (a), Jong-Hwa Lim (b), Raymond T. Ng (c), Kyuseok Shim (a) Keywords: Data mining; Knowledge discovery; Sequential pattern mining Abstract: Discovering sequential patterns is an important problem for many applications. Existing algorithms find qualitative sequential patterns in the sense that only items are included in the patterns. However, for many applications, such as business and scientific applications, quantitative attributes are often recorded in the data, which are ignored by existing algorithms. Quantity information included in the mined sequential patterns can provide useful insight to the users. In this paper, we consider the problem of mining sequential patterns with quantities. We demonstrate that naive extensions to existing algorithms for sequential patterns are inefficient, as they may enumerate the search space blindly. To alleviate the situation, we propose hash filtering and quantity sampling techniques that significantly improve the performance of the naive extensions. Experimental results confirm that compared with the naive extensions, these schemes not only improve the execution time substantially but also show better scalability for sequential patterns with quantities. Author Affiliation: (a) School of Electrical Engineering and Computer Science, Seoul National University, Kwanak, P.O. Box 34, Seoul, Republic of Korea (b) Department of Computer Science, KAIST, Taejeon, Republic of Korea (c) Department of Computer Science, University of British Columbia, Vancouver, Canada Article History: Received 23 March 2006; Revised 3 December 2006; Accepted 7 December 2006 Article Note: (footnote) [star] This work was supported by the Ministry of Information and Communication, Korea, under the College Information Technology Research Center Support Program, grant number IITA-2006-C1090-0603-0031.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2007.01.006 Byline: Natalia Juristo (a), Ana M. Moreno (a), Maria-Isabel Sanchez-Segura (b) Keywords: Software usability; Software design Abstract: This paper analyses what implications usability has for software development, paying special attention to the impact of this quality attribute on design. In this context, the aim is twofold. On the one hand, we intend to empirically corroborate that software design and usability are really related. This would mean that this, like other quality attributes, would need to be dealt with no later than at design time to develop usable software at a reasonable cost. On the other hand, we present a possible quantification, calculated from a number of real applications, of the effect of incorporating certain usability features at design time. Author Affiliation: (a) School of Computing, Universidad Politecnica de Madrid, Campus de Montegancedo s/n, 28660 Boadilla del Monte, Madrid, Spain (b) Computer Science Department, Universidad Carlos III de Madrid, Avda. De la Universidad, 30, 28911 Leganes, Madrid, Spain Article History: Received 20 July 2006; Revised 3 January 2007; Accepted 5 January 2007 Article Note: (footnote) [star] This research was funded by the Spanish Ministry of Education - Project TIN 230005-00176.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.01.022 Byline: Rudolf Berghammer (a), Agnieszka Rusinowska (b)(c), Harrie de Swart (d) Keywords: Game theory; RelView; Relational algebra; Coalition formation; Feasible government; Dominance; Stable government Abstract: We present an application of relational algebra to coalition formation. This leads to specifications, which can be executed with the help of the RelView tool after a simple translation into the tool's programming language. As an example we consider a simplification of the situation in Poland after the 2001 elections. Author Affiliation: (a) Institute of Computer Science, University of Kiel, OlshausenstraAe 40, 24098 Kiel, Germany (b) Nijmegen School of Management, Radboud University Nijmegen, P.O. Box 9108, 6500 HK Nijmegen, The Netherlands (c) Department of Mathematical Economics, Warsaw School of Economics, Al. Niepodleglosci 162, 02-554 Warsaw, Poland (d) Department of Philosophy, Tilburg University, P.O. Box 90153, 5000 LE Tilburg, The Netherlands Article History: Received 29 June 2005; Accepted 13 January 2006 Article Note: (footnote) [star] Co-operation for this paper was supported by European COST Action 274 'Theory and Applications of Relational Structures as Knowledge Instruments' (TARSKI). We are grateful to two anonymous referees for some useful suggestions.