Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Author: search.filters.author.Makowski, Armand M.

Search Results

Now showing 1 - 10 of 88
  • Thumbnail Image
    Item
    On the gradual deployment of random pairwise key distribution schemes
    (2010-07-31) Yagan, Osman; Makowski, Armand M.
    In the context of wireless sensor networks, the pairwise key distribution scheme of Chan et al. has several advantages over other key distribution schemes including the original scheme of Eschenauer and Gligor. However, this offline pairwise key distribution mechanism requires that the network size be set in advance, and involves all sensor nodes simultaneously. Here, we address this issue by describing an implementation of the pairwise scheme that supports the gradual deployment of sensor nodes in several consecutive phases. We discuss the key ring size needed to maintain the secure connectivity throughout all the deployment phases. In particular we show that the number of keys at each sensor node can be taken to be O(log n) in order to achieve secure connectivity (with high probability).
  • Thumbnail Image
    Item
    On random graphs associated with a pairwise key distribution scheme for wireless sensor networks (Extended version)
    (2010-07) Yagan, Osman; Makowski, Armand M.
    The pairwise key distribution scheme of Chan et al. was proposed as an alternative to the key distribution scheme of Eschenauer and Gligor (EG) to enable network security in wireless sensor networks. In this paper we consider the random graph induced by this pairwise scheme under the assumption of full visibility. We first establish a zero-one law for graph connectivity. Then, we discuss the number of keys needed in the memory of each sensor in order to achieve secure connectivity (with high probability). For a network of n sensors the required number of keys is shown to be on the order of log n, a key ring size comparable to that of the EG scheme (in realistic scenarios).
  • Thumbnail Image
    Item
    On random graphs associated with a pairwise key distribution scheme
    (2010-01-01) Yagan, Osman; Makowski, Armand M.
    The pairwise key distribution scheme of Chan et al. was proposed as an alternative to the key distribution scheme of Eschenauer and Gligor to enable network security in wireless sensor networks. We consider the random graph induced by this pairwise scheme under the assumption of full visibility, and show the existence of a zero-one law for graph connectivity.
  • Thumbnail Image
    Item
    On the existence of triangles in random key graphs
    (2009-07-04) Yagan, Osman; Makowski, Armand M.
    The random key graph, also known as the uniform random intersection graph, is a random graph induced by the random key predistribution scheme of Eschenauer and Gligor under the assumption of full visibility. We show the existence of a zero-one law for the appearance of triangles in random key graphs by applying the method of first and second moments to the number of triangles in the graph.
  • Thumbnail Image
    Item
    Connectivity in one-dimensional geometric random graphs: Poisson approximations, zero-one laws and phase transitions
    (2008-10-24) Han, Guang; Makowski, Armand M.; Makowski, Armand M.
    Consider n points (or nodes) distributed uniformly and independently on the unit interval [0,1]. Two nodes are said to be adjacent if their distance is less than some given threshold value.For the underlying random graph we derive zero-one laws for the property of graph connectivity and give the asymptotics of the transition widths for the associated phase transition. These results all flow from a single convergence statement for the probability of graph connectivity under a particular class of scalings. Given the importance of this result, we give two separate proofs; one approach relies on results concerning maximal spacings, while the other one exploits a Poisson convergence result for the number of breakpoint users.
  • Thumbnail Image
    Item
    On the random graph induced by a randomized predistribution scheme under full visibility (Extended version)
    (2008) Yagan, Osman; Makowski, Armand M.
    We consider the random graph induced by the random key predistribution scheme of Eschenauer and Gligor under the assumption of full visibility. We show the existence of a zero-one law for the absence of isolated nodes, and complement it by a Poisson convergence for the number of isolated nodes. Leveraging earlier resu lts and analogies with Erd\H{o}s-Renyi graphs, we explore similar results for the property of graph connectivity. Implications for secure connectivity are discussed.
  • Thumbnail Image
    Item
    A strong zero-one law for connectivity in one-dimensional geometric random graphs with non-vanishing densities
    (2007) Han, Guang; Makowski, Armand M.; Makowski, Armand M.; ISR
    We consider the geometric random graph where n points are distributed independently on the unit interval [0,1] according to some probability distribution function F. Two nodes communicate with each other if their distance is less than some transmission range. When F admits a continuous density f which is strictly positive on [0,1], we show that the property of graph connectivity exhibits a strong critical threshold and we identify it. This is achieved by generalizing a limit result on maximal spacings due to Levy for the uniform distribution.
  • Thumbnail Image
    Item
    On the critical communication range under node placement with vanishing densities
    (2007) Han, Guang; Makowski, Armand M.; Makowski, Armand M.; ISR
    We consider the random network where n points are placed independently on the unit interval [0, 1] according to some probability distribution function F. Two nodes communicate with each other if their distance is less than some transmission range. When F admits a continuous density f with f = inf (f(x), x  [0, 1]) > 0, it is known that the property of graph connectivity for the underlying random graph admits a strong critical threshold. Through a counterexample, we show that only a weak critical threshold exists when f = 0 and we identify it. Implications for the critical transmission range are discussed.
  • Thumbnail Image
    Item
    On zero-one laws for connectivity in one-dimensional geometric random graphs
    (2006) Han, Guang; Makowski, Armand M.; Makowski; ISR; CSHCN
    We consider the geometric random graph where n points are distributed uniformly and independently on the unit interval [0,1]. Using the method of first and second moments, we provide a simple proof of the "zero-one" law for the property of graph connectivity under the asymptotic regime created by having n become large and the transmission range scaled appropriately with n.
  • Thumbnail Image
    Item
    Very sharp transitions in one-dimensional MANETs
    (2005) Han, Guang; Makowski, Armand M.; Makowski, Armand M.; ISR; CSHCN
    We investigate how quickly phase transitions can occur in one-dimensional geometric random graph models of MANETs. In the case of graph connectivity, we show that the transition width behaves like 1/n (when the number n of users is large), a significant improvement over general asymptotic bounds given recently by Goel et al. for monotone graph properties. We also discuss a similar result for the property that there exists no isolated user in the network. The asymptotic results are validated by numerical computations. Finally we outline how the approach sed here could be applied in higher dimensions and or other graph properties.