اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدImproved Bounds on Information Dissemination by Manhattan Random Waypoint Model
145
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
With the popularity of portable wireless devices it is important to model and predict how information or contagions spread by natural human mobility -- for understanding the spreading of deadly infectious diseases and for improving delay tolerant communication schemes. Formally, we model this problem by considering $M$ moving agents, where each agent initially carries a emph{distinct} bit of information. When two agents are at the same location or in close proximity to one another, they share all their information with each other. We would like to know the time it takes until all bits of information reach all agents, called the textit{flood time}, and how it depends on the way agents move, the size and shape of the network and the number of agents moving in the network. We provide rigorous analysis for the MRWP model (which takes paths with minimum number of turns), a convenient model used previously to analyze mobile agents, and find that with high probability the flood time is bounded by $Obig(Nlog Mlceil(N/M) log(NM)rceilbig)$, where $M$ agents move on an $Ntimes N$ grid. In addition to extensive simulations, we use a data set of taxi trajectories to show that our method can successfully predict flood times in both experimental settings and the real world.
قيم البحث
اقرأ أيضاً
We study by extensive numerical simulations the dynamics of a hard-core tracer particle (TP) in presence of two competing types of disorder - frozen convection flows on a square random Manhattan lattice and a crowded dynamical environment formed by a
lattice gas of mobile hard-core particles. The latter perform lattice random walks, constrained by a single-occupancy condition of each lattice site, and are either insensitive to random flows (model A) or choose the jump directions as dictated by the local directionality of bonds of the random Manhattan lattice (model B). We focus on the TP disorder-averaged mean-squared displacement, (which shows a super-diffusive behaviour $sim t^{4/3}$, $t$ being time, in all the cases studied here), on higher moments of the TP displacement, and on the probability distribution of the TP position $X$ along the $x$-axis. Our analysis evidences that in absence of the lattice gas particles the latter has a Gaussian central part $sim exp(- u^2)$, where $u = X/t^{2/3}$, and exhibits slower-than-Gaussian tails $sim exp(-|u|^{4/3})$ for sufficiently large $t$ and $u$. Numerical data convincingly demonstrate that in presence of a crowded environment the central Gaussian part and non-Gaussian tails of the distribution persist for both models.
In the randomly-oriented Manhattan lattice, every line in $mathbb{Z}^d$ is assigned a uniform random direction. We consider the directed graph whose vertex set is $mathbb{Z}^d$ and whose edges connect nearest neighbours, but only in the direction fix
ed by the line orientations. Random walk on this directed graph chooses uniformly from the $d$ legal neighbours at each step. We prove that this walk is superdiffusive in two and three dimensions. The model is diffusive in four and more dimensions.
The problem of Multi-Agent Path Finding (MAPF) calls for finding a set of conflict-free paths for a fleet of agents operating in a given environment. Arguably, the state-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS
). In this work we revisit the complexity analysis of CBS to provide tighter bounds on the algorithms run-time in the worst-case. Our analysis paves the way to better pinpoint the parameters that govern (in the worst case) the algorithms computational complexity. Our analysis is based on two complementary approaches: In the first approach we bound the run-time using the size of a Multi-valued Decision Diagram (MDD) -- a layered graph which compactly contains all possible single-agent paths between two given vertices for a specific path length. In the second approach we express the running time by a novel recurrence relation which bounds the algorithms complexity. We use generating functions-based analysis in order to tightly bound the recurrence. Using these technique we provide several new upper-bounds on CBSs complexity. The results allow us to improve the existing bound on the running time of CBS for many cases. For example, on a set of common benchmarks we improve the upper-bound by a factor of at least $2^{10^{7}}$.
Can artificial agents benefit from human conventions? Human societies manage to successfully self-organize and resolve the tragedy of the commons in common-pool resources, in spite of the bleak prediction of non-cooperative game theory. On top of tha
t, real-world problems are inherently large-scale and of low observability. One key concept that facilitates human coordination in such settings is the use of conventions. Inspired by human behavior, we investigate the learning dynamics and emergence of temporal conventions, focusing on common-pool resources. Extra emphasis was given in designing a realistic evaluation setting: (a) environment dynamics are modeled on real-world fisheries, (b) we assume decentralized learning, where agents can observe only their own history, and (c) we run large-scale simulations (up to 64 agents). Uncoupled policies and low observability make cooperation hard to achieve; as the number of agents grow, the probability of taking a correct gradient direction decreases exponentially. By introducing an arbitrary common signal (e.g., date, time, or any periodic set of numbers) as a means to couple the learning process, we show that temporal conventions can emerge and agents reach sustainable harvesting strategies. The introduction of the signal consistently improves the social welfare (by 258% on average, up to 3306%), the range of environmental parameters where sustainability can be achieved (by 46% on average, up to 300%), and the convergence speed in low abundance settings (by 13% on average, up to 53%).
Mobile Adhoc Network is a kind of wireless ad hoc network where nodes are connected wirelessly and the network is self configuring. MANET may work in a standalone manner or may be a part of another network. In this paper we have compared Random Walk
Mobility Model and Random Waypoint Mobility Model over two reactive routing protocols Dynamic Source Routing (DSR) and Adhoc On-Demand Distance Vector Routing (AODV) protocol and one Proactive routing protocol Distance Sequenced Distance Vector Routing (DSDV) Our analysis showed that DSR, AODV & DSDV under Random Walk and Random Way Point Mobility models have similar results for similar inputs however as the pause time increases so does the difference in performance rises. They show that their motion, direction, angle of direction, speed is same under both mobility models. We have made their analysis on packet delivery ratio, throughput and routing overhead. We have tested them with different criteria like different number of nodes, speed and different maximum number of connections.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
