### Ubiquitous home: real-life testbed for home context-aware service

- Research Article in 1st International Conference on Integrated Internet Ad hoc and Sensor Networks
- Authors:
- Tatsuya Yamazaki
- Abstract:
The National Institute of Information and Communications Technology of Japan completed a real-life testbed, called the "ubiquitous home", for home context-aware service experiments in 2004. From the viewpoint of sensor ubiquity, the Ubiquitous Home is superior to other similar testbeds. At the Ubiq…

more »The National Institute of Information and Communications Technology of Japan completed a real-life testbed, called the "ubiquitous home", for home context-aware service experiments in 2004. From the viewpoint of sensor ubiquity, the Ubiquitous Home is superior to other similar testbeds. At the Ubiquitous Home, experimenters can collect real-life data as if living in their own house, not in a laboratory. This paper introduces an overview and detailed sensor arrangement of the Ubiquitous Home. Two cases from several progressing experiments are also presented. The first case is on connecting networked appliances; the second concerns the combination of wearable devices and the Ubiquitous Home sensors to record user behavior.

### Wireless nomadic transfer over mobile ad hoc networks

- Research Article in 1st International Conference on Integrated Internet Ad hoc and Sensor Networks
- Authors:
- Stefano Annese, Andrea Ghittino
- Abstract:
Mobile ad hoc networking allows the development of several infrastructure free applications. One of the arguments we focused on is the possibility of deploying a set of services in areas lacking of low-cost and wide band connectivity to Internet, as rural or mountain communities. The main idea is t…

more »Mobile ad hoc networking allows the development of several infrastructure free applications. One of the arguments we focused on is the possibility of deploying a set of services in areas lacking of low-cost and wide band connectivity to Internet, as rural or mountain communities. The main idea is that it is possible to transfer data by mobile vehicles such as bus, letter carriers and other similar means, by equipping them with an ad hoc kit able to discover clients capable to receive news, e-mail or, generally, to act as a server for other kind of services. In this context we used AODV protocol to interconnect the hosts involved in the test-bed and SLP to develop some applications to offer e-mail and news pushing services over discontinuous connectivity.

### GILDA: the grid INFN virtual laboratory for dissemination activities

- Research Article in 1st International Conference on Integrated Internet Ad hoc and Sensor Networks
- Authors:
- G. Andronico, V. Ardizzone, R. Barbera, R. Catania, A. Carrieri, A. Falzone, E. Giorgio, G. La Rocca, S. Monforte, M. Pappalardo, G. Passaro, G. Platania
- Abstract:
The elements of the GILDA dissemination grid developed within the context of Italian INFN Grid Project and the European EGEE Project are presented and described.

more »The elements of the GILDA dissemination grid developed within the context of Italian INFN Grid Project and the European EGEE Project are presented and described.

### An optimization framework for radio resource management based utility vs. price tradeoff in WCDMA systems

- Research Article in 3rd International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks
- Authors:
- L. Badia,, C. Saturni, L. Brunetta, M. Zorzi
- Abstract:
In this paper we investigate radio resource management strategies for multimedia networks driven by economic aspects such as users' utility and service pricing. To this end, we discuss a framework in which the impact of both QoS and pricing is accounted for in the users' acceptance rate of the serv…

more »In this paper we investigate radio resource management strategies for multimedia networks driven by economic aspects such as users' utility and service pricing. To this end, we discuss a framework in which the impact of both QoS and pricing is accounted for in the users' acceptance rate of the service. The model is general enough to be adapted to different situations and optimization goals. Thus, we discuss possible objectives for the network management under the constraints of meeting quality of service requirements, by satisfying at the same time technical conditions of feasibility. We employ utility functions, in order to account for the additional characteristic represented by the traffic elasticity, and consider the effect of price to have a realistic characterization of economic quantities. The resulting optimization problem is then discussed and analyzed, to derive general insight and identify possibilities for enhancement.

### A simulation tool to evaluate radio resource management algorithms for enhanced UMTS

- Research Article in 3rd International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks
- Authors:
- V. Vassiliou, J. Antoniou, G. Hadjipollas, A. Pitsillides
- Abstract:
This paper presents a new system level simulator that has been developed to evaluate radio resource management (RRM) techniques in UMTS (Universal Mobile Telecommunication Systems) and enhanced-UMTS networks. The simulator includes new implementations for the user equipment, node B, radio network c…

more »This paper presents a new system level simulator that has been developed to evaluate radio resource management (RRM) techniques in UMTS (Universal Mobile Telecommunication Systems) and enhanced-UMTS networks. The simulator includes new implementations for the user equipment, node B, radio network controller nodes and can evaluate parameters associated with UMTS or enhanced-UMTS performance, related to the introduction of RRM functions. The RRM functions implemented deal with admission control, packet scheduling, handover control, load control, and power control. The evaluation of RRM mechanisms is supported by the provision of appropriate radio propagation, traffic generation, and mobility models.

### Minimizing delay in loss-tolerant MAC layer multicast

- Research Article in 3rd International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks
- Authors:
- P. Chaporkar , S. Sarkar
- Abstract:
Many real-time applications require one to many (multicast) communication. Real time applications can gracefully accommodate some loss but require low delay. We minimize the delay in real-time MAC layer multicast by exploiting the broadcast nature of wireless medium and limited loss tolerance of th…

more »Many real-time applications require one to many (multicast) communication. Real time applications can gracefully accommodate some loss but require low delay. We minimize the delay in real-time MAC layer multicast by exploiting the broadcast nature of wireless medium and limited loss tolerance of the applications. We show that multiple transmissions of a packet at the MAC layer significantly reduces the delay than that when only one transmission is allowed. But each additional transmission consumes additional power and increases network load. Therefore, our goal is to design a policy that judiciously uses the limited transmission opportunities so as to deliver each packet in minimum possible time to the required number of group members. We show that the problem is an instance of the stochastic shortest path problem, and using this formulation obtain a computationally simple, closed form transmission strategy in important special cases. Numerical computations show that only a small number of transmissions, if used judiciously, are sufficient to minimize the delay subject to loss constraint.

### A new hybrid scheduling framework for asymmetric wireless environments with request repetition

- Authors:
- N. Saxena, C.M. Pinotti, S.K. Das, K. Basu
- Abstract:
The ever-increasing popularity of Web services, growing demand for wireless multimedia and introduction of new, feature-enhanced, hand-held devices has already given birth to a new set of data-centric applications. Providing such applications with enhanced data processing capability calls for an ef…

more »The ever-increasing popularity of Web services, growing demand for wireless multimedia and introduction of new, feature-enhanced, hand-held devices has already given birth to a new set of data-centric applications. Providing such applications with enhanced data processing capability calls for an efficient scheduling and transmission technique. The goal of most scheduling strategy lies in reducing the average waiting time. However, in most practical systems the variation of waiting time often results in client's impatience, thus provoking the clients to send repeated requests for the particular data item(s). In this paper we have developed a new hybrid scheduling framework for heterogeneous, asymmetric environments, by exploring the advantages of broadcasting very popular (push) data and dissemination of less popular (pull) data. The data access probabilities and the cut-off point used to segregate push and pull sets are dynamically computed. Packet fair scheduling (PFS) and stretch-optimal scheduling principle is deployed to obtain the push and pull schedule respectively. The framework explicitly takes care of the repeated requests originating from the impatient clients and minimizes the overall expected access time by obtaining an optimal cut-off point. Extensive performance analysis and simulation experiments are performed to show the efficiency of the system in reducing the overall expected access time (delay).

### Tighter bounds for the minimum energy broadcasting problem

- Authors:
- A. Navarra
- Abstract:
In this paper we present a new upper bound on the approximation ratio of the minimum spanning tree heuristic for the basic problem on ad-hoc networks given by the minimum-energy broadcast routing (MEBR) problem. We introduce a new analysis allowing to establish a 6.33-approximation ratio in the 2-d…

more »In this paper we present a new upper bound on the approximation ratio of the minimum spanning tree heuristic for the basic problem on ad-hoc networks given by the minimum-energy broadcast routing (MEBR) problem. We introduce a new analysis allowing to establish a 6.33-approximation ratio in the 2-dimensional case, thus decreasing the previously known 7.6 upper bound (M. Flammini et al., 2004).

### Iterated local optimization for minimum energy broadcast

- Authors:
- Intae Kang, R. Poovendran
- Abstract:
In our prior work, we presented a highly effective local search based heuristic algorithm called the largest expanding sweep search (LESS) to solve the minimum energy broadcast (MEB) problem over wireless ad hoc or sensor networks. In this paper, the performance is further strengthened by using ite…

more »In our prior work, we presented a highly effective local search based heuristic algorithm called the largest expanding sweep search (LESS) to solve the minimum energy broadcast (MEB) problem over wireless ad hoc or sensor networks. In this paper, the performance is further strengthened by using iterated local optimization (ILO) techniques at the cost of additional computational complexity. To the best of our knowledge, this implementation constitutes currently the best performing algorithm among the known heuristics for MEB. We support this claim through extensive simulation study, comparing with globally optimal solutions obtained by an integer programming (IP) solver. For small network size up to 20 nodes, which is imposed by practical limitation of the IP solver, the ILO based algorithm produces globally optimal solutions with very high frequency (70%), and average performance is within 1.12% of the optimal solution.

### Modeling and analysis of opportunistic routing in low traffic scenarios

- Authors:
- R.C. Shah, S. Wietholter, A. Wolisz
- Abstract:
Opportunistic routing protocols have been proposed as efficient methods to exploit the high node densities in sensor networks to mitigate the effect of varying channel conditions and non-availability of nodes that power down periodically. They work by integrating the network and data link layers so…

more »Opportunistic routing protocols have been proposed as efficient methods to exploit the high node densities in sensor networks to mitigate the effect of varying channel conditions and non-availability of nodes that power down periodically. They work by integrating the network and data link layers so that they can take a joint decision as to the next hop forwarding node based on its availability and suitability as a forwarder. This cross-layer integration makes it harder to optimize the protocol due to the dependencies among the different components of the protocol stack. In this paper, we provide a framework to model opportunistic routing that breaks up the functionality into three separate components and simplifies analysis. The framework is used to model two variants of opportunistic routing and is shown to match well with simulation results. In addition, using the model for performance analysis yields important guidelines for the future design of such protocols.

### A practical approach to QoS routing for wireless networks

- Authors:
- T. Tung, Zhanfeng Jia, J. Walrand
- Abstract:
We study QoS routing in wireless networks. We impose a structure on the network to combat the far-reaching effects of interference. We observe that there is little difference between routes through shared interference domains; instead the choices exist between routes through different domains. Base…

more »We study QoS routing in wireless networks. We impose a structure on the network to combat the far-reaching effects of interference. We observe that there is little difference between routes through shared interference domains; instead the choices exist between routes through different domains. Based on this observation, we suggest partitioning the network into non-overlapping clusters where each cluster represents an interference domain. Routing algorithms operate over the cluster-level topology and use shortest paths within the clusters. Clustering decouples the constraints allowing for estimates of the available capacity within a cluster via local measurements. We present a routing algorithm that chooses amongst cluster-level paths to accommodate a flow with certain QoS requirements. An admission control policy checks the feasibility of the suggested route and refines our estimates of available capacity.

### Energy saving dynamic source routing for ad hoc wireless networks

- Authors:
- M. Tarique, K.E. Tepe, M. Naserian
- Abstract:
In this paper, energy saving dynamic source routing (ESDSR) protocol is introduced to maximize the life-span of a mobile ad hoc network (MANET). Many theoretical studies show that energy consumption in MANET can be significantly reduced using energy-aware routing protocols compared to fixed-power m…

more »In this paper, energy saving dynamic source routing (ESDSR) protocol is introduced to maximize the life-span of a mobile ad hoc network (MANET). Many theoretical studies show that energy consumption in MANET can be significantly reduced using energy-aware routing protocols compared to fixed-power minimum-hop routing protocols. Two approaches are broadly suggested for energy-aware routing protocols - transmission power control approach and load sharing approach. ESDSR integrates the advantages of those two approaches. In ESDSR, the routing decision is based on a load balancing approach. Once a routing decision is made, link by link transmit power adjustment per packet is done based on a transmit power control approach. We modified dynamic source routing (DSR) protocol to make it energy aware by a network simulator (network simulator-2 of University of California). The simulation results show that the proposed ESDSR can save energy up to 40% per packet and it can send 20 % more packets to destinations by spending the same battery power in compare to DSR.

### k-server optimal task scheduling problem with convex cost function

- Authors:
- Mingjie Lin, Yaling Ma
- Abstract:
We consider a class of k-server optimal task scheduling problems partitioning and scheduling N tasks with various real-time constrains and work loads on k servers with convex task processing cost function so as to minimize the total task processing cost while still guaranteeing satisfaction of all …

more »We consider a class of k-server optimal task scheduling problems partitioning and scheduling N tasks with various real-time constrains and work loads on k servers with convex task processing cost function so as to minimize the total task processing cost while still guaranteeing satisfaction of all time constraints. This class has broad expressing power for practical scheduling problems in several areas such as real-time multimedia wireless transmission , CPU energy conservation, and warehouse order processing management, et. al. Our formulation is quite general such that most previous works can be readily reduced to a special case of the presented k-server optimal task scheduling problem. We show that, when k = 1, optimal solution can be obtained in computational complexity of O(N) and the corresponding optimal scheduling problem is equivalent to finding the shortest 2D Euclidean distance between two vertices inside a well-defined 2D polygon. However, when k 2, the optimal scheduling problem can be demonstrated to be NP-hard by reducing it to a well-known NP-complete bin-packing problem. Therefore, we conclude no polynomial time algorithm exists for a general k-server optimal task scheduling problem. We then construct approximation algorithms to solve the presented k-server problem in a practical way and illustrate its performance by simulation results and analysis.

### Computing optimal or near-optimal trees for minimum-energy in wireless networks

- Authors:
- Di Yuan
- Abstract:
We study minimum-energy broadcast routing in all-wireless networks. Up to now, a number of heuristics have been proposed for this NP-hard problem. Among them, the broadcast incremental power (BIP) algorithm, presented by Wieselthier et al., is most known. The contribution of our work consists of a …

more »We study minimum-energy broadcast routing in all-wireless networks. Up to now, a number of heuristics have been proposed for this NP-hard problem. Among them, the broadcast incremental power (BIP) algorithm, presented by Wieselthier et al., is most known. The contribution of our work consists of a refinement of the BIP algorithm and a novel integer programming formulation. The refined version of BIP is a natural extension of the original algorithm. The integer programming formulation allows us to compute optimal broadcast trees for networks of small size. For large-sized networks, the formulation admits the computation of a sharp lower bound to the optimal tree. We are thus able to efficiently assess the numerical performance of any heuristic algorithm for the problem. In our computational study, we compare the performance of our refined BlP algorithm to that of its original version, and examine the numerical performance of the two algorithms in terms of optimality using our integer programming model.

### NEURAL: a self-organizing routing algorithm for ad hoc networks

- Authors:
- E. Vicente, V.E. Mujica, D. Sisalem, R. Popescu-Zeletin
- Abstract:
This paper evaluates a self-organizing routing protocol for ad hoc network, called the neuron routing algorithm (NEURAL). NEURAL has been designed taking into account the learning and self-organizing abilities of the brain. More precisely, it was inspired by the synapses process between neurons, wh…

more »This paper evaluates a self-organizing routing protocol for ad hoc network, called the neuron routing algorithm (NEURAL). NEURAL has been designed taking into account the learning and self-organizing abilities of the brain. More precisely, it was inspired by the synapses process between neurons, when a signal is propagated. Basically, the most significant characteristic of NEURAL is the uniform distribution of the information around the node's location based on the current changes in its neighborhood. Using a 2-hop acknowledgment mechanism, local information is monitored in order to be used for route selection method, classification procedures and learning algorithms.

### Towards an understanding of EASE and its properties

- Authors:
- S. Ioannidis, P. Marbach
- Abstract:
We propose a model under which several inherent properties of the exponential age search routing protocol can be derived. By making simplifications on this model, we are able to address the issue of the optimality of a parameter of the protocol and to improve the existing upper bound on its perform…

more »We propose a model under which several inherent properties of the exponential age search routing protocol can be derived. By making simplifications on this model, we are able to address the issue of the optimality of a parameter of the protocol and to improve the existing upper bound on its performance.

### Mobility prediction's influence on QoS in wireless networks: a study on a call admission algorithm

- Authors:
- J.-M. Francois, G. Leduc
- Abstract:
Several mechanisms increase the QoS level of mobile networks thanks to an underlying mobility prediction method (i.e. a means to predict a mobile's next access router). This paper aims at studying how the accuracy of the prediction method can influence the network QoS in the particular context of c…

more »Several mechanisms increase the QoS level of mobile networks thanks to an underlying mobility prediction method (i.e. a means to predict a mobile's next access router). This paper aims at studying how the accuracy of the prediction method can influence the network QoS in the particular context of call admission control. It shows that (a) the mobiles behaviour must be adapted according to the prediction scheme accuracy in order to achieve good performance and (b) the admission algorithm can be modified to increase its fairness and to give mobiles an incentive to do such an adaptation.

### Optimal controlled flooding search in a large wireless network

- Authors:
- N.B. Chang, Mingyan Liu
- Abstract:
In this paper we consider the problem of searching for a node or an object (i.e., piece of data, file, etc.) in a large wireless network. We consider the class of controlled flooding search strategies where query/search packets are broadcast and propagated in the network until a preset TTL (time-to…

more »In this paper we consider the problem of searching for a node or an object (i.e., piece of data, file, etc.) in a large wireless network. We consider the class of controlled flooding search strategies where query/search packets are broadcast and propagated in the network until a preset TTL (time-to-live) value carried in the packet expires. Every unsuccessful search attempt results in an increased TTL value (i.e., larger search area) and the same process is repeated. We derive search strategies that minimize the search cost in the worst-case, via a performance measure in the form of the competitive ratio between the average search cost of a strategy and that of an omniscient observer. This ratio is shown in prior work to be lower bounded by 4 among all deterministic search strategies. In this paper we show that by using randomized strategies this ratio is lower bounded by e. We derive an optimal strategy that achieves this lower bound, and discuss its performance under other performance criteria.

### Securing route optimisation in NEMO

- Authors:
- M. Calderon, C.J. Bernardos, M. Bagnulo, I. Soto
- Abstract:
The network mobility (NEMO) basic support protocol enables mobile networks to change their point of attachment to the Internet, while preserving established sessions of the nodes within the mobile network. When only a nonnested mobile network is considered, the so-called triangle routing is the mai…

more »The network mobility (NEMO) basic support protocol enables mobile networks to change their point of attachment to the Internet, while preserving established sessions of the nodes within the mobile network. When only a nonnested mobile network is considered, the so-called triangle routing is the main problem that should be faced. In mobile IPv6, the route optimisation mechanism solves this problem, and the return routability mechanism aims to limit the security concerns originated because of the route optimisation. Nowadays return routability is considered a weak solution (i.e., based on strong assumptions). In this article we explore different approaches to route optimisation in NEMO and we devise how to adapt some of the terminal mobility solutions to a NEMO environment, where, as we propose, a delegation of signalling rights from the mobile network node to the mobile router is necessary.

### Analysis of a distributed algorithm to determine multiple routes with path diversity in ad hoc networks

- Authors:
- S. Mueller, D. Ghosal
- Abstract:
With multipath routing in mobile ad hoc networks (MANETs), a source can establish multiple routes to a destination for routing data. In MANETs, multipath routing can be used to provide route resilience, smaller end-to-end delay, and better load balancing. However, when the multiple paths are close …

more »With multipath routing in mobile ad hoc networks (MANETs), a source can establish multiple routes to a destination for routing data. In MANETs, multipath routing can be used to provide route resilience, smaller end-to-end delay, and better load balancing. However, when the multiple paths are close together, transmissions of different paths may interfere with each other, causing degradation in performance. Besides interference, the physical diversity of paths also improves fault tolerance. We present a purely distributed multipath protocol based on the AODV-multipath (AODVM) protocol called AODVM with path diversity (AODVM/PD) that finds multiple paths with a desired degree of correlation between paths specified as an input parameter to the algorithm. We demonstrate through detailed simulation analysis that multiple paths with low degree of correlation determined by AODVM/PD provides both smaller end-to-end delay than AODVM in networks with low mobility and better route resilience in the presence of correlated node failures.

### Finite state Markov model for effective bandwidth calculation in wireless packet networks

- Authors:
- S.R. Kundu, K. Basu, S.K. Das
- Abstract:
In this paper we study the causal behavior of Rayleigh fading wireless channel and a single queue system buffer using the finite state Markov chain (FSMC) and the finite buffer fluid flow model. In the process, we propose a state partitioning scheme for capturing the wireless channel realities base…

more »In this paper we study the causal behavior of Rayleigh fading wireless channel and a single queue system buffer using the finite state Markov chain (FSMC) and the finite buffer fluid flow model. In the process, we propose a state partitioning scheme for capturing the wireless channel realities based on the combined effect of level crossing rate (LCR), average fade duration (AFD) and the average value of the signal SNR observed at the output of the matched filter or correlation demodulator. Relevant system parameters captured using such a scheme is linked with the fluid flow traffic model to create a modulated Markov process (MMP) that is used to calculate the packet loss rate and effective bandwidth of the system.

### Power control for multicell CDMA wireless networks: a team optimization approach

- Authors:
- T. Alpcan, Xingzhe Fan , T. Basar, M. Arcak, J.T. Wen
- Abstract:
We study power control in multicell CDMA wireless networks as a team optimization problem where each mobile attains its individual fixed target SIR level by transmitting with minimum possible power level. We derive conditions under which the power control problem admits a unique feasible solution. …

more »We study power control in multicell CDMA wireless networks as a team optimization problem where each mobile attains its individual fixed target SIR level by transmitting with minimum possible power level. We derive conditions under which the power control problem admits a unique feasible solution. Using a Lagrangian relaxation approach similar to F. Kelly et al. (1998) we obtain two decentralized dynamic power control algorithms: primal and dual power update, and establish their global stability utilizing both classical Lyapunov theory and the passivity framework [J.T. Wen and M. Arcak, February 2004]. We show that the robustness results of passivity studies [(X. Fan et al., July 2004), (X. Fan et al., 2004)] as well as most of the stability and robustness analyses of F. Kelly et al. (1998) in the literature are applicable to the power control problem considered. In addition, some of the basic principles of call admission control are investigated from the perspective of the model adopted in this paper. We illustrate the proposed power control schemes through simulations.

### A simulated annealing algorithm for energy-efficient sensor network design

- Authors:
- F.Y.S. Lin, P.L. Chiu
- Abstract:
In this paper, we develop an algorithm to deploy an energy efficient sensor network such that it provides surveillance and target-positioning services. We consider to place K independent sets of sensors on a sensor field. These sets monitor the field in turn and work together when intrusion events …

more »In this paper, we develop an algorithm to deploy an energy efficient sensor network such that it provides surveillance and target-positioning services. We consider to place K independent sets of sensors on a sensor field. These sets monitor the field in turn and work together when intrusion events occur. The lifetime of the sensor network is therefore prolonged up to K times. The problem is therefore a variant of the set K-cover problem, which is NP-complete. We formulate such sensor deployment problem, as a 0/1 integer programming problem. A simulated annealing based heuristic then is proposed for solving the optimization problem. The experimental results show that the proposed algorithm indicates a significant improvement in the sensor lifetime compared to the intuitive approach. Furthermore, the proposed algorithm is highly effective and efficient in terms of the overall deployment cost.

### Interference power sum with log-normal components in ad-hoc and sensor networks

- Authors:
- R. Hekmat, P. Van Mieghem
- Abstract:
The log-normal shadowing radio model has frequently been used to model radio propagation conditions. There exist accurate calculation methods for estimation of interference power sum statistics in fixed-topology wireless networks based on this radio model. Here we publish essential additions to the…

more »The log-normal shadowing radio model has frequently been used to model radio propagation conditions. There exist accurate calculation methods for estimation of interference power sum statistics in fixed-topology wireless networks based on this radio model. Here we publish essential additions to these estimation methods to expand their use to sensor networks and ad-hoc networks with changing topology. To our best knowledge this has not been done before. Taking into account radio propagation conditions, density of nodes, size of the network, traffic load per node and MAC protocol characteristics, we present a calculation method for the estimation of interference power sum statistics in wireless ad-hoc and sensor networks. The accuracy of the calculation method is verified by simulations. We highlight the influence of MAC protocols on interference and show that an increase in network size or in node density does not necessarily lead into higher interference values. Our results can be deployed to estimate the network capacity.

### On range matrices and wireless networks in d dimensions

- Authors:
- M. Desai, D. Manjunath
- Abstract:
Suppose that V = {v1, v2, ...vn} is a set of nodes randomly (uniformly) distributed in the d dimensional cube [0, x0]d, and W = {w(i, j) > 0 : 1 ≤ i, j ≤ n} is a set of numbers chosen so that w(i, j) = w(j, i) = w(j, i). Construct a graph Gn,d,W whose vertex set is V, and whose edge set consists of…

more »Suppose that V = {v1, v2, ...vn} is a set of nodes randomly (uniformly) distributed in the d dimensional cube [0, x0]d, and W = {w(i, j) > 0 : 1 ≤ i, j ≤ n} is a set of numbers chosen so that w(i, j) = w(j, i) = w(j, i). Construct a graph Gn,d,W whose vertex set is V, and whose edge set consists of all pairs {ui, uj} with || ui - uj || ≤ w(i, j). In the wireless network context, the set V is a set of labeled nodes in the network and W represents the maximum distances between the node pairs for them to be connected. We essentially address the following question: "if G is a graph with vertex set V, what is the probability that G appears as a subgraph in Gn,d,W?" Our main contribution is a closed form expression for this probability under the l∞ norm for any dimension d and a suitably defined probability density function. As a corollary to the above answer, we also answer the question, "what is the probability that Qn,d,W is connected?".