A general framework for distance-based consensus in ordinal ranking models

The problem of aggregating a set of ordinal rankings of n alternatives has given rise to a number of consensus models. Among the most common of these models are those due to Borda and Kendall, which amount to using average ranks, and the ℓ¹ and ℓ² distance models. A common criticism of these approaches is their use of ordinal rank position numbers directly as the values of being ranked at those levels. This paper presents a general framework for associating value or worth with ordinal ranks, and develops models for deriving a consensus based on this framework. It is shown that the ℓ^p distance models using this framework are equivalent to the conventional ordinal models for any p ⩾ 1. This observation can be seen as a form of validation of the practice of using ordinal data in a manner for which it was presumably not designed. In particular, it establishes the robustness of the simple Borda, Kendall and median ranking models.     

Ordinal ranking and preference strength

This paper extends the Kemeny and Snell model of ordinal ranking to include a preference strength component. This is accomplished by expanding the ranking space to allow for the incorporation of dummy objects in the object listing. A set of axioms is presented, which a distance function on this expanded space should adhere to. Under this set of conditions, the distance function is characterized and shown to be unique. It is also shown that the Kemeny and Snell model is naturally embedded in this general model.     

Robust multi-criteria ranking with additive value models and holistic pair-wise preference statements

We consider a problem of ranking alternatives based on their deterministic performance evaluations on multiple criteria. We apply additive value theory and assume the Decision Maker’s (DM) preferences to be representable with general additive monotone value functions. The DM provides indirect preference information in form of pair-wise comparisons of reference alternatives, and we use this to derive the set of compatible value functions. Then, this set is analyzed to describe (1) the possible and necessary preference relations, (2) probabilities of the possible relations, (3) ranges of ranks the alternatives may obtain, and (4) the distributions of these ranks. Our work combines previous results from Robust Ordinal Regression, Extreme Ranking Analysis and Stochastic Multicriteria Acceptability Analysis under a unified decision support framework. We show how the four different results complement each other, discuss extensions of the main proposal, and demonstrate practical use of the approach by considering a problem of ranking 20 European countries in terms of 4 criteria reflecting the quality of their universities.     

Bounded-hops power assignment in ad hoc wireless networks

Motivated by topology control in ad hoc wireless networks, Power Assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity). The input consists of a directed complete weighted digraph G=(V,c) (that is, ). The power of a vertex u in a directed spanning subgraph H is given by , and corresponds to the energy consumption required for node u to transmit to all nodes v with uv∈E(H). The power of H is given by . Power Assignment seeks to minimize p(H) while H satisfies the given connectivity constraint.Min-Power Bounded-Hops Broadcast is a power assignment problem which has as additional input a positive integer d and a r∈V. The output H must be a r-rooted outgoing arborescence of depth at most d. We give an (O(logn),O(logn)) bicriteria approximation algorithm for Min-Power Bounded-Hops Broadcast: that is, our output has depth at most O(dlogn) and power at most O(logn) times the optimum solution.For the Euclidean case, when c(u,v)=c(v,u)=∥u,v∥^κ (here ∥u,v∥ is the Euclidean distance and κ is a constant between 2 and 5), the output of our algorithm can be modified to give a O((logn)^κ) approximation ratio. Previous results for Min-Power Bounded-Hops Broadcast are only exact algorithms based on dynamic programming for the case when the nodes lie on the line and c(u,v)=c(v,u)=∥u,v∥^κ.Our bicriteria results extend to Min-Power Bounded-Hops Strong Connectivity, where H must have a path of at most d edges in between any two nodes. Previous work for Min-Power Bounded-Hops Strong Connectivity consists only of constant or better approximation for special cases of the Euclidean case.     

Location tracking in mobile ad hoc networks using particle filters

Mobile ad hoc networks (MANETs) are dynamic networks formed on-the-fly as mobile nodes move in and out of each others' transmission ranges. In general, the mobile ad hoc networking model makes no assumption that nodes know their own locations. However, recent research shows that location-awareness can be beneficial to fundamental tasks such as routing and energy-conservation. On the other hand, the cost and limited energy resources associated with common, low-cost mobile nodes prohibits them from carrying relatively expensive and power-hungry location-sensing devices such as GPS. This paper proposes a mechanism that allows non-GPS-equipped nodes in the network to derive their approximated locations from a limited number of GPS-equipped nodes. In our method, all nodes periodically broadcast their estimated location, in terms of a compressed particle filter distribution. Non-GPS nodes estimate the distance to their neighbors by measuring the received signal strength of incoming messages. A particle filter is then used to estimate the approximated location, along with a measure of confidence, from the sequence of distance estimates. Simulation studies show that our solution is capable of producing good estimates equal or better than the existing localization methods such as APS-Euclidean for the more difficult scenario when the network connectivity is low.     

Maximum flow problem in wireless ad hoc networks with directional antennas

Directional antenna offers a variety of benefits for wireless networks, one of which is the increased spatial reuse ratio. This feature gives rise to the improved throughput in resource limited wireless ad hoc networks. In this paper, we formulate the maximum flow problem as an optimization problem in wireless ad hoc networks with switched beam directional antennas constrained by interference. We demonstrate how to solve this optimization problem. It turns out that the proposed method works for both single beam antenna and multi-beam antenna, with minor variation of the constraints.     

A biobjective optimization model for routing in mobile ad hoc networks

In this paper, the problem of finding optimal paths in mobile ad hoc networks is addressed. More specifically, a novel bicriteria optimization model, which allows the energy consumption and the link stability of mobile nodes to be taken into account simultaneously, is presented. In order to evaluate the validity of the proposed model, a greedy approach is devised. Some preliminary computational experiments have been carried out, in a simulation environment. The numerical results are very encouraging, showing the correctness of the proposed model. Indeed, the selection of a shorter route leads to a more stable route, but to a greater energy consumption. On the other hand, if longer routes are selected the route fragility is increased, but the average energy consumption is reduced.     

Improving time-efficiency in blocking expanding ring search for mobile ad hoc networks

We propose a new strategy for reducing the amount of latency and energy consumption in Blocking Expanding Ring Search (BERS) and enhanced Blocking Expanding Ring Search (BERS*) for mobile ad hoc networks (MANETs). BERS and BERS* are respectively energy and energy–time efficient route discovery protocols for MANETs as compared to conventional Expanding Ring Search (ERS). In this study, we identify unnecessary waiting time caused by a STOP/END instruction in BERS/BERS* and explore the potential of further improvement of their time efficiency. This leads to tBERS and tBERS*, the improved BERS and BERS* respectively. In tBERS/tBERS*, a route node may also issue the STOP/END instruction to terminate flooding. We implement this idea in algorithms, conduct analysis, and achieve further latency reduction in both tBERS and tBERS* as well as the energy saving in tBERS*.     

Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks

A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. One of the key communication operations is to broadcast a message from a source node. This paper studies the minimum latency broadcast scheduling problem in wireless ad hoc networks under collision-free transmission model. The previously best known algorithm for this NP-hard problem produces a broadcast schedule whose latency is at least 648（rmax/rmin）^2 times that of the optimal schedule, where rmax and rmin are the maximum and minimum transmission ranges of nodes in a network, respectively. We significantly improve this result by proposing a new scheduling algorithm whose approximation performance ratio is at most （1 ＋ 2rmax/rmin）^2＋32, Moreover, under the proposed scheduling each node just needs to forward a message at most once.     

Two new algorithms for the Min-Power Broadcast problem in static ad hoc networks

In this paper we address the Min-Power Broadcast problem in wireless ad hoc networks. Given a network with an identified source node w, the Min-Power Broadcast (MPB) problem is to assign transmission range to each node such that communication from w to other nodes is possible and the total energy consumption is minimized.

As the problem is NP-Hard we first propose a simulated annealing algorithm for the MPB problem. Utilizing a special node selection mechanism in its neighborhood structure the algorithm is designed in a way enabling an efficient power consumption evaluation and search for neighboring solutions. We then combine the algorithm with a decomposition approach to enhance its performance. This is achieved by decomposing the master problem and performing metropolis chain of the simulated annealing only on the much smaller subproblems resulting from decomposition. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed algorithms.     

Topology control in the mobile ad hoc networks in order to intensify energy conservation

Although studied for years, due to their dynamic nature, research in the field of mobile ad hoc networks (MANETs) has remained a vast area of interest. Since once distributed, there will be less to no plausibility of recharge, energy conservation has become one of the pressing concerns regarding this particular type of network. In fact, one of the main obligations of designers is to make efficient use of these scarce resources. There has been tremendous work done in different layers of protocol stack in order to intensify energy conservation. To date, numerous topology control algorithms have been proposed, however, only a few have used meta-heuristics such as genetic algorithms, neural networks and/or learning automata to overcome this issue. On the other hand, since nodes are mobile and thus in a different spatial position, as time varies, we can expect that by regulating time intervals between topology controls, one may prolong the network’s lifetime. The main initiative of this paper is to intensify energy conservation in a mobile ad hoc network by using weighted and learning automata based algorithms. The learning automata, regulates time intervals between which the topology controls are done. The represented learning automata based algorithm uses its learning ability to find appropriate time-intervals so that the nodes would regulate the energy needed in order to exchange the information to their neighbors, accordingly. Moreover, at first we have represented two weighted based algorithms which extend two prominent protocols, namely K-Neigh and LMST. Then these algorithms are combined with a learning based algorithm which regulates time intervals between which the topology controls are done. In comparison with approaches that are based on periodic topology controls, proposed approach shows enhanced results. On the other hand, considering the learning ability of the learning automata based algorithms, composition of the aforementioned algorithms has been proven to be enhanced, in the respect of energy consumed per data transmitted, over those compared with.     

Aggregation and consensus for preference relations based on fuzzy partial orders

We propose a framework for eliciting and aggregating pairwise preference relations based on the assumption of an underlying fuzzy partial order. We also propose some linear programming optimization methods for ensuring consistency either as part of the aggregation phase or as a pre- or post-processing task. We contend that this framework of pairwise-preference relations, based on the Kemeny distance, can be less sensitive to extreme or biased opinions and is also less complex to elicit from experts. We provide some examples and outline their relevant properties and associated concepts.     

Some simple optimization techniques for self-organized public key management in mobile ad hoc networks

We consider some graph theoretical problems arising from security requirements in some communication networks. Basically one has to associate to each node of a directed graph G=(V,E) a partial subgraph of G. A solution consists hence of a collection of |V| subgraphs, subject to some packing constraints or connectivity requirements. We first describe the usual graph theoretical model and we review a known construction procedure for which we point out some basic properties. We then study in more details the case of complete graphs and show the existence of a solution with a guaranteed quality. Next, we study the performance of the construction procedure and we propose an additional construction. We attempt to characterize the cases in which either construction is preferable. In the last section, a tabu search approach is proposed and tested on a sample of numerical examples.     

A fast local search method for minimum energy broadcast in wireless ad hoc networks

Local search methods are often used to reduce the power consumption of broadcast routing in wireless networks. For a classic method, sweep, the best available time complexity result is O(|V|⁴). We present an O(|V|²)-time method, which exhaustively removes unnecessary transmissions yielding a solution comparable to that of sweep.     

Multicriteria approaches for ranking of efficient units in DEA models

Data envelopment analysis models usually split decision making units into two basic groups, efficient and inefficient. Efficiency score of inefficient units allows their ranking but efficient units cannot be ranked directly because of their maximum efficiency. That is why there are formulated several models for ranking of efficient units. The paper presents two original models for ranking of efficient units in data envelopment analysis—they are based on multiple criteria decision making techniques—goal programming and analytic hierarchy process. The first model uses goal programming methodology and minimizes either the sum of undesirable deviations or maximal undesirable deviation from the efficient frontier. The second approach is analytic hierarchy process model for ranking of efficient units. The two presented models are compared with several super-efficiency models and other approaches for ranking decision making units in DEA models including definitions based on distances from optimistic and pessimistic envelopes and cross efficiency evaluation models. The results of the analysis by all presented models are illustrated on a real data set—evaluation of 194 bank branches of one of the Czech commercial banks.     

A probabilistic framework for the design of instance-based supervised ranking algorithms in an ordinal setting

In this article, we present a probabilistic framework which serves as the base from which instance-based algorithms for solving the supervised ranking problem may be derived. This framework constitutes a simple and novel approach to the supervised ranking problem, and we give a number of typical examples of how this derivation can be achieved. In this general framework, we pursue a cumulative and stochastic approach, relying heavily upon the concept of stochastic dominance. We show how the median can be used to extract, in a consistent way, a single (classification) label from a returned cumulative probability distribution function. We emphasize that all operations used are mathematically sound, i.e. they only make use of ordinal properties. Mostly, when confronted with the problem of learning a ranking, the training data is not monotone in itself, and some cleansing operation is performed on it to remove these ‘inconsistent’ examples. Our framework, however, deals with these occurrences of ‘reversed preference’ in a non-invasive way. On the contrary, it even allows to incorporate information gained from the occurrence of these reversed preferences. This is exactly what happens in the second realization of the main theorem.     

网页排序中的随机模型及算法

随着互联网规模的日益增长, 搜索引擎已经成为互联网上有效的信息获取工具. 而在众多搜索引擎的背后, 是信息检索技术, 也即网页排序算法在起作用. 网页排序包括重要性排序和相关性排序. 通过我们研究发现, 尽管这两类排序所依据的准则不同, 但是都可以通过建立适当的随机过程模型来研究. 对于网页重要性排序, 我们通过分析用户浏览网页的行为建立了Markov 骨架过程的框架. 基于该框架我们分析了三种不同的随机过程模型对用户行为模拟的合理程度, 并设计了名为BrowseRank 的一组新算法, 该算法可以根据用户上网行为来计算网页的重要性. 在网页相关性排序中, 我们主要针对排序结果联合问题建立了一个基于Markov 链的监督学习框架. 通过将传统方法的监督化, 使原来难于解决的问题变的易于学习, 将原来的NP- 难问题转化为一个半正定规划问题, 提高了效率.     

Location-aided routing with uncertainty in mobile ad hoc networks: A stochastic semidefinite programming approach

We study location-aided routing under mobility in wireless ad hoc networks. Due to node mobility, the network topology changes continuously, and clearly there exists an intricate tradeoff between the message passing overhead and the latency in the route discovery process. Aiming to obtain a clear understanding of this tradeoff, we use stochastic semidefinite programming (SSDP), a newly developed optimization model, to deal with the location uncertainty associated with node mobility. In particular, we model both the speed and the direction of node movement by random variables and construct random ellipses accordingly to better capture the location uncertainty and the heterogeneity across different nodes. Based on SSDP, we propose a stochastic location-aided routing (SLAR) strategy to optimize the tradeoff between the message passing overhead and the latency. Our results reveal that in general SLAR can significantly reduce the overall overhead than existing deterministic algorithms, simply because the location uncertainty in the routing problem is better captured by the SSDP model.     

Model-based two-way clustering of second-level units in ordinal multilevel latent Markov models

In this paper, an ordinal multilevel latent Markov model based on separate random effects is proposed. In detail, two distinct second-level discrete effects are considered in the model, one affecting the initial probability vector and the other affecting the transition probability matrix of the first-level ordinal latent Markov process. To model these separate effects, we consider a bi-dimensional mixture specification that allows to avoid unverifiable assumptions on the random effect distribution and to derive a two-way clustering of second-level units. Starting from a general model where the two random effects are dependent, we also obtain the independence model as a special case. The proposal is applied to data on the physical health status of a sample of elderly residents grouped into nursing homes. A simulation study assessing the performance of the proposal is also included.