We introduce the Regular Language-Constrained Team Orienteering Problem with Time Windows (RLC-TOPTW) as a generalization of the Team Orienteering Problem with Time Windows (TOPTW). The problem is pertinent to application domains which entail categorization of graph/network nodes and constraints associated with the categories of the nodes in the solution path. RLC-TOPTW captures any type of constraints as long as they can be described by regular expressions, and its solution provides a feasible path that satisfies the constraints. As RLC-TOPTW is NP-hard we present two efficient heuristic approaches: The first heuristic is based on the solution approach for solving the Regular Language-Constrained Orienteering Problem with Time Windows (RLC-OPTW) given in[1] while the second is a genetic algorithm approach. The proposed algorithms have been assessed using publicly available datasets.

This paper addresses the problem of operator-based vehicle repositioning in free-floating electric car-sharing systems (FFCSs). New algorithmic techniques are developed which derive cost-effective relocation tours by primarily minimizing relocation drivers' walking time. Car repositioning takes place overnight and aims at complete rebalancing of the system i.e., at achieving an optimal, based on user demand, cars distribution among nonoverlapping cells of the FFCS's operating area. The battery level of the electric cars is also taken into account when deciding if and where each car will be relocated. If k is the number of employees handling car relocations from oversupplied to undersupplied regions, when k = 1 i.e., there exists a single employee carrying out a relocation tour comprising alternating phases of a car relocation followed by walking to the next to be relocated car, we define and solve the Minimum Walking Car Repositioning Problem (MWCRP) whose main objective is to minimize the walking distance in the relocation tour as the walking part of such a tour is tiresome and takes more time than the driving one. We also define and solve the k-MWCRP when k > 1 to handle the case that a team of more than one drivers is employed to take on the relocation plan. It is worth mentioning that these are the first vehicle relocation techniques lowering the relocation cost by mostly minimizing the walking cost. Performance results confirm the effectiveness of the proposed algorithms.

Mobile Context-Aware Recommender Systems (CARS) have recently emerged aiming at generating recommendations relevant to the specific environmental and situational usage context. This article reports on the design and implementation of a collaborative filtering-based mobile CARS, developed as part of an e-platform that supports location-based search for retail products and services sold by nearby physical retailer shops. In addition to the current user location, our RS considers a multitude of contextual factors like time, season, demographic data, consumer behavior, and location history of the user in order to derive more meaningful product recommendations. The RS has been tested on real operational environments as well as on lab evaluation trials demonstrating higher accuracy and relevance of recommendations against two baseline approaches.

Providing efficient, sustainable and personalized mobility services in urban environments that combine a spectrum of transport modes (e.g., public transport, electric vehicles, vehicle sharing, low energy and/or emission routes) constitutes a great challenge. In this work, we present MOVESMART, a holistic approach (and integrated platform) for the provision of renewable personal mobility services, leveraging crowd-sourcing data, tools for collecting real-time information by multimodal travelers, and traffic prediction mechanisms. MOVESMART guarantees real-time responses to renewable (on-demand) mobility queries for efficient multi-modal route planning that are time-dependent as well as sensitive to aperiodic incidents and traffic prediction forecasts. This paper focuses on the cloudbased (backend) services of the MOVESMART platform.

Mobility of people and goods in urban environments raises several quality and sustainability concerns. While ICTs have established the ground for developing intelligent transport services, their effective use for supporting cleaner urban mobility still represents a major research challenge. The eCOMPASS research project addressed this challenge through introducing new mobility concepts and establishing a methodological framework for route planning optimization, delivering a comprehensive set of innovative tools and services for end-users to enable eco-awareness in urban transport. eCOMPASS innovative tools are based on new algorithmic technology concerning tools and methods for vehicle routing (cars and vehicle fleets) and multimodal human mobility for city dwellers and tourists. eCOMPASS involved a generic architecture that considered all types and scenarios of human and goods mobility in urban environments minimizing their environmental impact. In this work, we report on the main scientific innovations and end-products of eCOMPASS for vehicle routing, including car route planning and vehicle fleets.

The environmental impact of the steadily increasing demand for mobility of people and goods, especially in urban environments, raises public concern and presents challenges that need to be addressed in the interest of long-term sustainability. Along this line, the inherently eco-friendly human mobility which involves the use of urban public transit networks must be encouraged and eased. This necessitates the development of context-aware services that hide the complexity of public transit networks while considering all available transportation modalities (e.g. bus, metro, tram, walking and cycling) in order to provide sophisticated route planning tailored to both residents and visitors of urban areas. The EU-funded eCOMPASS research project has addressed this challenge through establishing a methodological framework for route planning optimization. A core objective of the project has been to employ novel algorithm engineering approaches for delivering a comprehensive set of tools and services (accessible from web/mobile application interfaces) for mobile end users to enable eco-awareness in urban multi-modal transfers. eCOMPASS delivered web and mobile services providing multimodal public transportation route planning, considering contextual information as well as various restrictions and/or user constraints. Herein, we report the motivation, main scientific innovations and present the end-products of eCOMPASS with respect to multimodal human mobility.

A special case of the Time-Dependent Shortest Path Problem (TDSPP) is the itinerary planning problem where the objective is to find the shortest path between a source and a destination node which passes through a fixed sequence of intermediate nodes. In this paper, we deviate from the common approach for solving this problem, that is, finding first the shortest paths between successive nodes in the above sequence and then synthesizing the final solution from the solutions of these sub-problems. We propose a more direct approach and solve the problem by a label-setting approach which is able to early prune a lot of partial paths that cannot be part of the optimal solution. In addition, we study a different version of the main problem where it is only required that the solution path should pass through a set of specific nodes irrespectively of the particular order in which these nodes are included in the path. As a case study, we have applied the proposed techniques for solving the itinerary planning of a ship with respect to two conflicting criteria, in the area of the Aegean Sea, Greece. Moreover, the algorithm handles the case that the ship speed is not constant throughout the whole voyage. Specifically, it can be set at a different level each time the ship departs from an intermediate port in order to obtain low cost solutions for the itinerary planning. The experimental results confirm the high performance of the proposed algorithms.

Several mobile guides for unknown destinations provide assistance to tourists (through personalized tour recommendations) in making feasible plans and visiting the most interesting POIs within their available time. However, existing tourist tour planners only regard available attractions as sites lacking physical dimensions (i.e. POIs are treated as points). Although this is adequate for scheduling visits at POIs with single entry/exit points, it fails to capture practical properties of typical tourist visiting styles in urban destinations (e.g. tourists typically enjoy walking on pedestrian zones, market areas and scenic neighborhoods). Herein, we introduce Scenic Athens, a context-aware mobile city guide for Athens (Greece) which delivers personalized tour planning services to tourists deriving near-optimal sequencing of POIs along recommended tours. Scenic Athens takes into account a multitude of travel restrictions and POI properties, also incorporating scenic (walking) routes (in addition to point POIs), thereby supporting more experiential exploration of tourist destinations. A user evaluation study validated the recommendation value, usability and perceived utility of the proposed application.

The investigation of mobile agent (MA) middleware as a technology for implementing efficient data fusion schemes on wireless sensor networks (WSN) has been a subject of intense research in the past few years. Nevertheless, the itineraries followed by travelling MAs largely determine the overall performance of the data fusion applications. Along this line, this article introduces a novel algorithmic approach for efficient itinerary planning of MA objects engaged in data fusion tasks. Our algorithm adopts an iterated local search (ILS) approach in deriving the hop sequence of multiple travelling MAs over the deployed source nodes. Simulation results demonstrate the performance gain of our method against existing multiple MA itinerary planning methods.

A critical issue dealt with in Wireless Sensor and Actor Networks (WSANs) is the real time response of actors to events occurring in the network area. The fast notification of actors from Sensor Nodes (SNs) about the events as well as the effective coordination of actors for prompt event handling is most important in these networks. In this paper, we introduce a distributed protocol for effective event handling in a WSAN. Existing approaches mainly favoring actors near the current event for handling it, may lead to highly ineffective solutions for certain worst-case scenarios. Through a randomized approach, our solution also selects distant actors for handling events, and guarantees fast average responsiveness to events and a balanced energy distribution among actors. In addition, it features efficient distributed algorithms for sensor to actor and actor to actor coordination which are of independent interest.

Tourists become increasingly dependent on mobile city guides to locate tourist services and retrieve information about nearby points of interest (POIs) when visiting unknown destinations. Although several city guides support the provision of personalized tour recommendations to assist tourists visiting the most interesting attractions, existing tour planners only consider walking tours. Herein, we introduce eCOMPASS, a context-aware mobile application which also considers the option of using public transit for moving around. Far beyond than just providing navigational aid, eCOMPASS incorporates multimodality (i.e. time dependency) within its routing logic aiming at deriving near-optimal sequencing of POIs along recommended tours so as to best utilize time available for sightseeing and minimize waiting time at transit stops. Further advancing the state of the art, eCOMPASS allows users to define arbitrary start/end locations (e.g. the current location of a mobile user) rather than choosing among a fixed set of locations. This paper describes the routing algorithm which comprises the core functionality of eCOMPASS and discusses the implementation details of the mobile application using the metropolitan area of Berlin (Germany) as case study.

A large class of Wireless Sensor Networks (WSN) applications involve a set of isolated urban areas (e.g., urban parks or building blocks) covered by sensor nodes (SNs) monitoring environmental parameters. Mobile sinks (MSs) mounted upon urban vehicles with fixed trajectories (e.g., buses) provide the ideal infrastructure to effectively retrieve sensory data from such isolated WSN fields. Existing approaches involve either single-hop transfer of data from SNs that lie within the MS's range or heavy involvement of network periphery nodes in data retrieval, processing, buffering, and delivering tasks. These nodes run the risk of rapid energy exhaustion resulting in loss of network connectivity and decreased network lifetime. Our proposed protocol aims at minimizing the overall network overhead and energy expenditure associated with the multihop data retrieval process while also ensuring balanced energy consumption among SNs and prolonged network lifetime. This is achieved through building cluster structures consisted of member nodes that route their measured data to their assigned cluster head (CH). CHs perform data filtering upon raw data exploiting potential spatial-temporal data redundancy and forward the filtered information to appropriate end nodes with sufficient residual energy, located in proximity to the MS's trajectory. Simulation results confirm the effectiveness of our approach against as well as its performance gain over alternative methods.

This paper deals with the problem of deriving personalized recommendations for daily sightseeing itineraries for tourists visiting any destination. Our approach considers selected places of interest that a traveler would potentially wish to visit and derives a near-optimal itinerary for each day of visit; the places of potential interest are selected based on stated or implied user preferences. Our method enables the planning of customized daily personalized tourist itineraries considering user preferences, time available for visiting sights in daily basis, opening days of sights and average visiting times for these sights. Herein, we propose a heuristic solution to this problem and discuss its implementation aspects.

Damianos Gavalas, Grammati Pantziou, Charalampos Konstantopoulos; Mobility in Wireless Sensor Networks, The Computer Journal, Volume 54, Issue 12, 1 November 20

This short paper deals with the problem of deriving personalized recommendations for daily sightseeing itineraries for tourists visiting any destination. Our approach considers selected places of interest that a traveller would potentially wish to visit and derives a near-optimal itinerary for each day of visit; the places of potential interest are selected based on stated or implied user preferences. Herein, we propose a heuristic solution to this problem and discuss its implementation aspects.

A key feature of wireless sensor networks (WSNs) is the collaborative processing, where the correlation existing over the local data of sensor nodes (SNs) is exploited so that the total data volume can be reduced (data aggregation). The use of Mobile Agents (MAs), i.e., software entities able of migrating among nodes and resuming execution naturally, fits in this scenario; the local data of an SN can be combined with the data collected by an MA from other SNs in a way that depends on the specific program code of the MA. In this paper, we consider the problem of calculating near-optimal routes for MAs that incrementally aggregate the data as they visit the nodes in a distributed sensor network. Our algorithm follows a greedy-like approach always selecting the next node to be included in an itinerary in such a way that the cost of the so far formed itineraries is kept minimum at each step. Simulation results confirm the high effectiveness of the proposed algorithm as well as its performance gain over alternative approaches. Also, with the use of proper data structures, the computational complexity of the algorithm is kept low as it is formally proved in the paper.

Mobile agents (MAs) have been initially developed to replace the client/server model which shows many disadvantages in WSN environments (e.g. very high bandwidth and energy utilization). Herein, we present CBID (Clone-Based Itinerary Design), a novel algorithm that calculates near-optimal routes for MAs that incrementally fuse the data as they visit the nodes while enabling a fast update of designed itineraries which is especially important for highly dynamic topologies. The order of visited nodes highly affects the quality and the overall cost of data fusion. The key MAs characteristic exploited by CBID to reduce energy consumption and response time is their cloning capability. Parallel dispatched MAs sequentially visit sensor nodes arranged in tree structures and upon visiting a node with two or more child nodes, the MAs (master MAs) clone of themselves with each clone (slave MA) visiting a tree branch. When all slave MAs return to that node, report their data to the master MA and are self-destroyed. This results in highly reduced energy consumption and response time since many MAs work in parallel. Simulation results prove the high effectiveness of CBID in data fusion tasks compared to other alternative algorithms.

In this article, we consider the problem of calculating an appropriate number of near-optimal (subject to a certain routing objective) routes for mobile agents (MAs) that incrementally fuse the data as they visit the nodes in a distributed sensor network. We propose an improved heuristic algorithm which computes an approximate solution to the problem by suggesting an appropriate number of MAs and constructing near-optimal itineraries for each of them. The performance gain of our algorithm over alternative approaches both in terms of cost and task completion latency is demonstrated by a quantitative evaluation and also in simulated environments through a Java-based tool.

Wireless sensor networks (WSNs) are used in many applications which often include the monitoring and recording of sensitive information. Hence, their critical importance raises many security concerns. In the context of WSNs, jamming is the type of attack which interferes with the radio frequencies used by network nodes. In the event that an attacker uses a rather powerful jamming source, disruptions of WSNs proper function are likely to occur. As a result, the use of countermeasures against jamming in WSN environments is of immense importance. The main contribution of this article is the discussion of various defence methods against jamming that would allow a WSN to survive and work properly in a hostile jamming environment. Our focus is on frequency hopping spread spectrum (FHSS) and direct sequence spread spectrum (DSSS), two of the most effective countermeasures against jamming. We suggest the use of a specific FHSS technique in 5 GHz band with 55 frequency channels wherein the channel sequence is generated using a secret word, known only to the sink and the sensor nodes, as a seed. Each channel uses DSSS modulation with 16 bit Pseudo Noise (PN) code, which derives from the same secret word used for FHSS channel generation.

Organization, scalability and routing have been identified as key problems hindering viability and commercial success of mobile ad hoc networks. Clustering of mobile nodes among separate domains has been proposed as an efficient approach to address those issues. In this work, we introduce an efficient distributed clustering algorithm that uses both location and energy metrics for cluster formation. Our proposed solution mainly addresses cluster stability, manageability and energy efficiency issues. Also, unlike existing active clustering methods, our algorithm relieves the network from the unnecessary burden of control messages broadcasting, especially for relatively static network topologies. This is achieved through adapting broadcast period according to mobile nodes mobility pattern. The efficiency, scalability and competence of our algorithm against alternative approaches have been demonstrated through simulation results.

One of the most important features in image analysis and understanding is shape. Mathematical morphology is the image processing branch that deals with shape analysis. The definition of all morphological transformations is based on two primitive operations, i.e. dilation and erosion. Since many applications require the solution of morphological problems in real time, researching time efficient algorithms for these two operations is crucial. In this paper efficient parallel algorithms for the binary dilation and erosion are presented and evaluated for an advanced associative processor. Simulation results indicate that the achieved speedup is linear.

Motion estimation is widely used in video coding schemes in order to reduce the inherent temporal redundancy among the frames of a video stream. In particular, low and very low bit rate video coding schemes need sophisticated motion models which usually require a large number of arithmetic operations. In this paper we present a parallel algorithm for the most practical of these models. Specifically we implement the affine motion model on a hypercube-based multiprocessor. This model covers the most usual kinds of motion and requires only a modest number of arithmetic operations. Also, the hypercube network can efficiently handle the non-regular data flow resulting from the parallel implementation of this model. In addition, we assume that our multiprocessor is fine grained, in contrast to most programmable architectures used in video coding, where processors usually have large local memory. Apart from its practicality, the constraint of limited local memory makes the algorithm design more challenging and thus more theoretically interesting. Finally, with regard to other proposals in the literature, our scheme is more general: whereas our scheme covers all kinds of motion supported by the affine motion model, the rest of the proposals deal only with a subset of these kinds. Copyright © 2000 John Wiley & Sons, Ltd.