اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMinimizing Total Interference in Asymmetric Sensor Networks
55
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The problem of computing a connected network with minimum interference is a fundamental problem in wireless sensor networks. Several models of interference have been studied in the literature. The most common model is the receiver-centric, in which the interference of a node $p$ is defined as the number of other nodes whose transmission range covers $p$. In this paper, we study the problem of assigning a transmission range to each sensor, such that the resulting network is strongly connected and the total interference of the network is minimized. For the one-dimensional case, we show how to solve the problem optimally in $O(n^3)$ time. For the two-dimensional case, we show that the problem is NP-complete and give a polynomial-time 2-approximation algorithm for the problem.
قيم البحث
اقرأ أيضاً
We consider the following interference model for wireless sensor and ad hoc networks: the receiver interference of a node is the number of transmission ranges it lies in. We model transmission ranges as disks. For this case we show that choosing tran
smission radii which minimize the maximum interference while maintaining a connected symmetric communication graph is NP-complete.
This invited paper presents some novel ideas on how to enhance the performance of consensus algorithms in distributed wireless sensor networks, when communication costs are considered. Of particular interest are consensus algorithms that exploit the
broadcast property of the wireless channel to boost the performance in terms of convergence speeds. To this end, we propose a novel clustering based consensus algorithm that exploits interference for computation, while reducing the energy consumption in the network. The resulting optimization problem is a semidefinite program, which can be solved offline prior to system startup.
We consider asymmetric convex intersection testing (ACIT). Let $P subset mathbb{R}^d$ be a set of $n$ points and $mathcal{H}$ a set of $n$ halfspaces in $d$ dimensions. We denote by $text{ch}(P)$ the polytope obtained by taking the convex hull of $
P$, and by $text{fh}(mathcal{H})$ the polytope obtained by taking the intersection of the halfspaces in $mathcal{H}$. Our goal is to decide whether the intersection of $mathcal{H}$ and the convex hull of $P$ are disjoint. Even though ACIT is a natural variant of classic LP-type problems that have been studied at length in the literature, and despite its applications in the analysis of high-dimensional data sets, it appears that the problem has not been studied before. We discuss how known approaches can be used to attack the ACIT problem, and we provide a very simple strategy that leads to a deterministic algorithm, linear on $n$ and $m$, whose running time depends reasonably on the dimension $d$.
The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between inciden
t edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove that, up to a finite number of well specified exceptions of constant size, the number of edges of a graph with $n$ vertices and a total angular resolution greater than $60^{circ}$ is bounded by $2n-6$. This bound is tight. In addition, we show that deciding whether a graph has total angular resolution at least $60^{circ}$ is NP-hard.
Total Generalized Variation (TGV) has recently been proven certainly successful in image processing for preserving sharp features as well as smooth transition variations. However, none of the existing works aims at numerically calculating TGV over tr
iangular meshes. In this paper, we develop a novel numerical framework to discretize the second-order TGV over triangular meshes. Further, we propose a TGV-based variational model to restore the face normal field for mesh denoising. The TGV regularization in the proposed model is represented by a combination of a first- and second-order term, which can be automatically balanced. This TGV regularization is able to locate sharp features and preserve them via the first-order term, while recognize smoothly curved regions and recover them via the second-order term. To solve the optimization problem, we introduce an efficient iterative algorithm based on variable-splitting and augmented Lagrangian method. Extensive results and comparisons on synthetic and real scanning data validate that the proposed method outperforms the state-of-the-art methods visually and numerically.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
