Alpern S.,University of Warwick |
Lidbetter T.,Management Science Group
Mathematics of Operations Research | Year: 2014
A point lies on a network according to some unknown probability distribution. Starting at a specified root of the network, a Searcher moves to find this point at speeds that depend on his location and direction. He seeks the randomized search algorithm that minimizes the expected search time. This is equivalent to modeling the problem as a zero-sum hide-and-seek game whose value is called the search value of the network. We make a new and direct derivation of an explicit formula for the search value of a tree, proving that it is equal to half the sum of the minimum tour time of the tree and a quantity called its incline. The incline of a tree is an average over the leaf nodes of the difference between the time taken to travel from the root to a leaf node and the time taken to travel from a leaf node to the root. This difference can be interpreted as height of a leaf node, assuming uphill is slower than downhill. We then apply this formula to obtain numerous results for general networks. We also introduce a new general method of comparing the search value of networks that differ in a single arc. Some simple networks have very complicated optimal strategies that require mixing of a continuum of pure strategies. Many of our results generalize analogous ones obtained for constant velocity (in both directions) by S. Gal, but not all of those results can be extended. © 2014 INFORMS.
Kolios P.,Kings College London |
Friderikos V.,Kings College London |
Papadaki K.,Management Science Group
IEEE Vehicular Technology Magazine | Year: 2011
One of the key components of emerging and next-generation wireless networks is the integration of fixed and/or mobile relays to, inter alia, increase capacity, lessen edge-cell starvation, and permit an energy-efficient operation of the network. If mobile nodes are allowed to perform mechanical relaying, i.e., store and carry the information before forwarding it to another relay node or base station BS, a plethora of different, novel resource-utilization schemes can be explored to increase network performance. We detail in this article a set of techniques based on mechanical relaying for wireless networks and describe the benefits that stem from the use of such relaying schemes in terms of energy consumption and resource utilization in the network. © 2006 IEEE.
Kolios P.,University of Cyprus |
Pitsillides A.,University of Cyprus |
Mokryn O.,The Academic College of Tel-Aviv-Yaffo |
Papadaki K.,Management Science Group
2014 IEEE International Conference on Communications, ICC 2014 | Year: 2014
This work is concerned with the problem of efficient and intelligent message forwarding in wireless networks. This problem arises in many diverse scenarios within ad-hoc networks and especially networks formed during and in the aftermath of a disaster in which infrastructure-based communication systems have been damaged or completely destroyed. Within this setting, mobile devices need to support critical message exchanges in order to offer user reassurance and aid first responders' search-and-rescue operations. Notably, the dissemination of alert messages has to be done in a way that achieves sufficient dissemination while ensuring network longevity. Under the proposed explore and exploit (EnE) framework, this paper derives innovative networking heuristics that capitalizes on locally-calculated metrics (including the Local Connectivity (LC) centrality metric) to make message forwarding/replication decisions. The proposed heuristics exhibit excellent features with regards to the aforementioned performance objectives and are shown to greatly outperform current popular alternative solutions. © 2014 IEEE.
Montibeller G.,Management Science Group |
Yoshizaki H.,University of Sao Paulo
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2011
Locating logistic facilities, such as plants and distribution centres, in an optimal way, is a crucial decision for manufacturers, particularly those that are operating in large developing countries which are experiencing a process of fast economic change. Traditionally, such decisions have been supported by optimising network models, which search for the configuration with the minimum total cost. In practice, other intangible factors, which add or reduce value to a potential configuration, are also important in the location choice. We suggest in this paper an alternative way to analyse such problems, which combines the value from the topology of a network (such as total cost or resilience) with the value of its discrete nodes (such as specific benefits of a particular location). In this framework, the focus is on optimising the overall logistic value of the network. We conclude the paper by discussing how evolutionary multi-objective methods could be used for such analyses. © 2011 Springer-Verlag.
Papadaki K.,Management Science Group |
Friderikos V.,Kings College London
Performance Evaluation | Year: 2012
In this paper a rate control scheme for downlink packet transmission in CDMA networks is proposed based on both the queue lengths and the channel states of mobile users. We are interested in optimal rate allocation policies for throughput maximisation over time and thus we formulate the problem as a discrete stochastic dynamic program. This dynamic program is exponentially complex in the number of users, which renders it impractical and therefore we use an approximate dynamic programming (DP) algorithm to obtain sub-optimal rate allocation policies in real time. The numerical results reveal that the proposed algorithm significantly outperforms a number of different baseline greedy heuristics. © 2012 Elsevier B.V. All rights reserved.