Indian Institute of Technology Kanpur
Kalyanpur, Kanpur 208 016, U.P., INDIA
Publications
Collapse All
 Working Papers
Surprise in Elections
Palash Dey, Pravesh K. Kothari, and Swaprava Nath
Technical Report.
Abstract and Full PaperElections involving a very large voter population often lead to outcomes that surprise many. This is particularly important for the elections in which results affect the economy of a sizable population. A better prediction of the true outcome helps reduce the surprise (or shock) and keeps the voters prepared. This paper starts from the basic observation that individuals in the underlying population build estimates of the distribution of preferences of the whole population based on their local neighborhoods. The outcome of the election leads to a surprise/shock if these local estimates contradict the outcome of the election for some fixed voting rule. To get a quantitative understanding, we propose a simple mathematical model of the setting where the individuals in the population and their connections (through geographical proximity, social networks etc.) are described by a random graph with connection probabilities that are biased based on the preferences of the individuals. Each individual also has some estimate of the bias in their connections.
[PDF]
We show that the election outcome leads to a surprise if the discrepancy between the esti mated bias and the true bias in the local connections exceeds a certain threshold, and confirm the phenomenon that surprising outcomes are associated only with closely contested elections. We compare standard voting rules based on their performance on surprise and show that they have different behavior for different parts of the population. It also hints at an impossibility that a single voting rule will be less surprising for all parts of a population. Finally, we experiment with the UKEU referendum (a.k.a. Brexit) dataset to see a realworld effect of estimation errors on surprise.

Separability and Decomposition in Mechanism Design with Transfers
Debasis Mishra, Swaprava Nath, and Souvik Roy
Technical Report.
Abstract and Full PaperIn private values quasilinear environment, we consider problems where allocation decisions along multiple components have to be made. Every agent has additively separable valuation over the components. We show that every neutral and dominant strategy implementable allocation rule in this problem is a neutral component affine maximizer, which assigns nonnegative weight vectors to agents in each component and chooses an alternative in each component by maximizing the weighted sum of valuations in that component. A corollary of our result is that every neutral and dominant strategy implementable allocation rule can be almost decomposed (modulo tiebreaking) into dominant strategy implementable allocation rules along each component.
[PDF]

Subset Selection Via Implicit Utilitarian Voting
Ioannis Caragiannis, Swaprava Nath, Ariel Procaccia, and Nisarg Shah
Journal of Artificial Intelligence Research (JAIR), 2016, forthcoming.
Abstract and Full PaperHow should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A wellestablished approach  which we refer to as implicit utilitarian voting  assumes that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regretbased rules are more compelling than distortionbased rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regretbased rule. Our methods underlie the design and implementation of an upcoming social choice website.
[PDF]

Dynamic Mechanism Design with Interdependent Valuations
Swaprava Nath, Onno Zoeter, Y. Narahari, and Chris Dance
Review of Economic Design (ROED), 19(3), 2015, pp 211228.
Abstract and Full PaperWe consider an infinite horizon dynamic mechanism design problem with interdependent valuations. In this setting the types of the agents are assumed to be evolving according to a first order Markov process and the types are independent across agents in every round and across rounds. However, the valuations of the agents are functions of the types of all the agents, which makes the problem fall into an interdependent value model. Designing mechanisms in this setting is nontrivial in view of an impossibility result which says that for interdependent valuations, any efficient and expost incentive compatible mechanism must be a constant mechanism, even if the mechanism is static. Mezzetti circumvents this problem by splitting the decisions of allocation and payment into two stages. However, Mezzetti's result is limited to static setting and moreover in the second stage of that mechanism, agents are weakly indifferent about reporting their valuations truthfully. This paper provides a first attempt at designing a dynamic mechanism which is strict expost incentive compatible and efficient in interdependent value setting with Markovian type evolution. In a restricted domain, which appears often in realworld scenarios, we show that our mechanism is expost individually rational as well.
[PDF] [Journal Link]

Affine Maximizers in Domains with Selfish Valuations
Swaprava Nath and Arunava Sen
ACM Transactions on Economics and Computation (ACMTEAC), 3(4), 2015, article 26, pp 26:119.
Abstract and Full PaperWe consider the domain of selfish and continuous preferences over a "rich" allocation space and show that onto, strategyproof and nonbossy social choice functions are affine maximizers. Roberts (1979) proves this result for a finite set of alternatives and an unrestricted valuation space. In this paper, we show that in a subdomain of the unrestricted valuations with the additional assumption of nonbossiness, using the richness of the allocations, the strategyproof social choice functions can be shown to be affine maximizers. This work serves as an example that an affine maximizer result needs certain amount of richness split across valuations and allocations.
[PDF] [Journal Link]

A Strict Expost Incentive Compatible Mechanism for Interdependent Valuations
Swaprava Nath and Onno Zoeter
Economics Letters, 121(2), 2013, pp 321325.
Abstract and Full PaperThe impossibility result by Jehiel and Moldovanu says that in a setting with interdependent valuations, any efficient and expost incentive compatible mechanism must be a constant mechanism. Mezzetti circumvents this problem by designing a two stage mechanism where the decision of allocation and payment are split over the two stages. This mechanism is elegant, however keeps a major weakness. In the second stage, agents are weakly indifferent about reporting their valuations truthfully: an agent's payment is independent of her reported valuation and truthtelling for this stage is by assumption. We propose a modified mechanism which makes truthful reporting in the second stage a strict equilibrium.
[PDF] [Journal Link]

Theory and Algorithms for HopCountBased Localization with Random Geometric Graph Models of Dense Sensor Networks
Swaprava Nath, Venkatesan N. E., Anurag Kumar, and P. Vijay Kumar
ACM Transactions on Sensor Networks (ACMTOSN), 8(4), 2012, pp 35:138.
Abstract and Full PaperWireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes in a region of Euclidean space. Following deployment, the nodes selforganize into a mesh topology with a key aspect being selflocalization. Having obtained a mesh topology in a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this work, we analyze this approximation through two complementary analyses. We assume that the mesh topology is a random geometric graph on the nodes; and that some nodes are designated as anchors with known locations. First, we obtain high probability bounds on the Euclidean distances of all nodes that are h hops away from a fixed anchor node. In the second analysis, we provide a heuristic argument that leads to a direct approximation for the density function of the Euclidean distance between two nodes that are separated by a hop distance h. This approximation is shown, through simulation, to very closely match the true density function.
[PDF] [Journal Link]
Localization algorithms that draw upon the above analyses are then proposed and shown to perform better than some of the wellknown algorithms present in the literature. Beliefpropagation based messagepassing is then used to further enhance the performance of the proposed localization algorithms. To our knowledge, this is the first usage of messagepassing for hopcountbased selflocalization.

A GameTheoretic Formalism of Human Partial Adaptation: Models and Experiments
Stefanos Nikolaidis, Swaprava Nath, Ariel Procaccia, and Siddhartha Srinivasa
Human Robot Interaction (HRI), March 69, 2017, Vienna, Austria, forthcoming.
Abstract and Full PaperIn humanrobot collaborative tasks, humans often start with an inaccurate model of the robot capabilities. They then make inferences on what the robot can and cannot do through interaction, and update their strategy accordingly. This paper presents a gametheoretic formalism for human partial adaptation to the robot, which captures the evolution of the human strategy over time, as the human partner observes the outcome of the robot and their actions. The model allows the robot to reason in a probabilistic sense over how the human actions will change based on its own actions, and compute a policy that optimizes the tradeoff between conveying information to the human and maximizing the team payoff. We formally prove that under certain observability assumptions on the human state, the policy computation can be done very efficiently. Human subject experiment indicate that the proposed formalism can significantly improve humanrobot team performance, compared to policies that assume complete adaptation of the human to the robot.
[PDF]

Preference Elicitation For Participatory Budgeting
Gerdus Benade, Swaprava Nath, Ariel Procaccia, and Nisarg Shah
Association for Advancement of Artificial Intelligence (AAAI), February 4  9, 2017, San Francisco, California, USA, forthcoming.
Abstract and Full PaperParticipatory budgeting enables the allocation of public funds by collecting and aggregating individual preferences; it has already had a sizable realworld impact. But making the most of this new paradigm requires a rethinking of some of the basics of computational social choice, including the very way in which individuals express their preferences. We analytically compare four preference elicitation methods  knapsack votes, rankings by value or value for money, and threshold approval votes  through the lens of implicit utilitarian voting, and find that threshold approval votes are qualitatively superior. This conclusion is supported by experiments using data from real participatory budgeting elections
[PDF]

Efficiency and Budget Balance
Swaprava Nath and Tuomas Sandholm
Web and Internet Economics (WINE), December 11  14, 2016, Montreal, Canada, forthcoming.
Abstract and Full PaperWe study efficiency and budget balance in mechanism design in the quasilinear domain. Green and Laffont [1979] proved that one cannot generically achieve both. We consider strategyproof budgetbalanced mechanisms that are approximately efficient. For deterministic mechanisms, we show that a strategyproof and budgetbalanced mechanism must have a sink agent whose valuation function is ignored in selecting an alternative, and she is given the payments made by the other agents. We assume the valuations of the agents are drawn from a bounded open interval. This result strengthens Green and Laffont’s impossibility result by showing that even in a restricted domain of valuations, there does not exist a mechanism that is strategyproof, budget balanced, and takes every agent’s valuation into consideration  a corollary of which is that it cannot be efficient. Using this result, we find a tight lower bound on the inefficiencies of strategyproof, budgetbalanced mechanisms in this domain. The bound shows that the inefficiency asymptotically disappears when the number of agents is large  a result close in spirit to Green and Laffont [1979, Theorem 9.4]. However, our results provide worstcase bounds and the best possible rate of convergence.
[PDF] [code]
Next, we consider minimizing any convex combination of inefficiency and budget imbalance. We show that no deterministic mechanism can do asymptotically better than minimizing inefficiency alone.
Finally, we investigate randomized mechanisms and provide improved lower bounds on expected inefficiency. We give a tight lower bound for an interesting class of strategyproof, budgetbalanced, randomized mechanisms. We also use an optimizationbased approach in the spirit of automated mechanism design to provide a lower bound on the minimum achievable inefficiency of any randomized mechanism.

Subset Selection Via Implicit Utilitarian Voting
Ioannis Caragiannis, Swaprava Nath, Ariel Procaccia, and Nisarg Shah
International Joint Conference on Artificial Intelligence (IJCAI), July 915, 2016, New York, USA.
Abstract and Full PaperHow should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A wellestablished approach  which we refer to as implicit utilitarian voting  assumes that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regretbased rules are more compelling than distortionbased rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regretbased rule. Our methods underlie the design and implementation of an upcoming social choice website.
[PDF]

Productive Output in Hierarchical Crowdsourcing
Swaprava Nath and Balakrishnan Narayanaswamy
Autonomous Agents and MultiAgent Systems (AAMAS), May 59, 2014, Paris, France, pp 469476.
Abstract and Full PaperOrganically grown crowdsourcing networks, which includes production firms and social network based crowdsourcing applications, tend to have a hierarchical structure. Considering the entire crowdsourcing system as a consolidated organization, a primary goal of a designer is to maximize the net productive output of this hierarchy using reward sharing as an incentive tool. Every individual in a hierarchy has a limited amount of effort that they can split between production and communication. Productive effort yields an agent a direct payoff, while the communication effort of an agent improves the productivity of other agents in her subtree. To understand how the net output of the crowdsourcing network is influenced by these components, we develop a game theoretic model that helps explain how the individuals trade off these two components depending on their position in the hierarchy and their shares of reward. We provide a detailed analysis of the Nash equilibrium efforts and a design recipe of the reward sharing scheme that maximizes the net productive output. Our results show that even under strategic behavior of the agents, it is sometimes possible to achieve the optimal output and also provide bounds on the achievability when this is not the case.
[PDF]

A Mechanism to Optimally Balance Cost and Quality of Labeling Tasks Outsourced to Strategic Agents
Satyanath Bhat, Swaprava Nath, Onno Zoeter, Sujit Gujar, Y. Narahari, and Chris Dance
Autonomous Agents and MultiAgent Systems (AAMAS), May 59, 2014, Paris, France, pp 917924.
Abstract and Full PaperWe consider a class of crowdsourcing problems where the owner of a task benefits from the high quality opinions provided by experts. Executing the task at an assured quality level in a cost effective manner in such situations becomes a mechanism design problem when the individual qualities are private information of the experts. The considered class of task execution problems falls into the category of interdependent values, where one cannot simultaneously achieve truthfulness and efficiency in the unrestricted setting due to an impossibility result (Jehiel and Moldovanu, 2001). We propose a mechanism QUEST, that leverages the structure of our special class of problems and guarantees allocative efficiency, expost incentive compatibility, expost individual rationality, and strict budget balance, which even the mechanism given by Mezzetti (2004) cannot achieve in this setting. The expost individual rationality comes under a tight sufficiency condition, and we show that the above four properties are not simultaneously satisfiable if the sufficient condition is violated. To the best of our knowledge, this is the first attempt in developing a quality assuring crowdsourcing mechanism in an interdependent value setting with quality levels held private by strategic agents.
[PDF]

On Profit Sharing and Hierarchies in Organizations
Swaprava Nath, Balakrishnan Narayanaswamy, Kundan Kandhway, Bhushan Kotnis, and David C. Parkes
Asian Meeting of the Econometric Society (AMES), December 2022, 2012, New Delhi, India, paper 119, pp 119.
Abstract and Full PaperWe study the effect of hierarchies on the performance of an organization that exhibits both profit sharing and information sharing. We adopt a serverqueue model of effort and intraorganizational competition and quantify the performance of an organization in terms of the overall efficiency and risk in meeting target production levels. On the one hand, we show that profit sharing leads to free riding at the Nash equilibrium and reduces overall effort. Introducing a form of information asymmetry, we then quantitatively establish the tradeoff between free riding and the positive effects of information sharing in hierarchies. We formulate an optimal hierarchy design problem that captures both effects, and provide a simple algorithm that gives near optimal designs. We provide an analysis of the productive value of optimized hierarchies, considering their ability to attain target production levels with low risk.
[PDF]

Mechanism Design for Time Critical and Cost Critical Task Execution via Crowdsourcing
Swaprava Nath, Pankaj Dayama, Dinesh Garg, Y. Narahari, and James Zou
Web and Internet Economics (WINE), December 9  12, 2012, Liverpool, UK, pp 212226.
Abstract and Full PaperIn recent times, crowdsourcing over social networks has emerged as an active tool for complex task execution. In this paper, we address the problem faced by a planner to incentivize agents in the network to execute a task and also help in recruiting other agents for this purpose. We study this mechanism design problem under two natural resource optimization settings: (1) cost critical tasks, where the planner's goal is to minimize the total cost, and (2) time critical tasks, where the goal is to minimize the total time elapsed before the task is executed. We define a set of fairness properties that should be ideally satisfied by a crowdsourcing mechanism. We prove that no mechanism can satisfy all these properties simultaneously. We relax some of these properties and define their approximate counterparts. Under appropriate approximate fairness criteria, we obtain a nontrivial family of payment mechanisms. Moreover, we provide precise characterizations of cost critical and time critical mechanisms.
[PDF] [slides]

Threats and Tradeoffs in Resource Critical Crowdsourcing Tasks over Networks (student abstract)
Swaprava Nath, Pankaj Dayama, Dinesh Garg, Y. Narahari, and James Zou
Conference of the Association for Advancement Artificial Intelligence (AAAI), July 2226, 2012, Toronto, Canada, pp 24472448.
[PDF]

Dynamic Mechanism Design for Markets with Strategic Resources
Swaprava Nath, Onno Zoeter, Y. Narahari, and Chris Dance
Conference on Uncertainty in Artificial Intelligence (UAI), July 1417, 2011, Barcelona, Spain, pp 539546.
Abstract and Full PaperThe assignment of tasks to multiple resources becomes an interesting game theoretic problem, when both the task owner and the resources are strategic. In the classical, nonstrategic setting, where the states of the tasks and resources are observable by the controller, this problem is that of finding an optimal policy for a Markov decision process (MDP). When the states are held by strategic agents, the problem of an efficient task allocation extends beyond that of solving an MDP and becomes that of designing a mechanism. Motivated by this fact, we propose a general mechanism which decides on an allocation rule for the tasks and resources and a payment rule to incentivize agents' participation and truthful reports.
[PDF] [slides]
In contrast to related dynamic strategic control problems studied in recent literature, the problem studied here has interdependent values: the benefit of an allocation to the task owner is not simply a function of the characteristics of the task itself and the allocation, but also of the state of the resources. We introduce a dynamic extension of Mezzetti's two phase mechanism for interdependent valuations. In this changed setting, the proposed dynamic mechanism is efficient, within period expost incentive compatible, and within period expost individually rational. It has, perhaps surprisingly, a computation time that is of the same order as of the nonstrategic equivalent.
We demonstrate the effectiveness of the approach with simulations, and observe that certain socially desirable properties may not be simultaneously satisfiable.

Dynamic Learningbased Mechanism Design for Dependent Valued Exchange Economies (PhD proposal)
Swaprava Nath
International World Wide Web Conference (WWW), March 28  April 1, 2011, Hyderabad, India, pp 397402.
Abstract and Full PaperLearning private information from multiple strategic agents poses challenge in many Internet applications. Sponsored search auctions, crowdsourcing, Amazon’s mechanical turk, various online review forums are examples where we are interested in learning true values of the advertisers or true opinion of the reviewers. The common thread in these decision problems is that the optimal outcome depends on the private information of all the agents, while the decision of the outcome can be chosen only through reported information which may be manipulated by the strategic agents. The other important trait of these applications is their dynamic nature. The advertisers in an online auction or the users of mechanical turk arrive and depart, and when present, interact with the system repeatedly, giving the opportunity to learn their types. Dynamic mechanisms, which learn from the past interactions and make present decisions depending on the expected future evolution of the game, has been shown to improve performance over repeated versions of static mechanisms. In this paper, we will survey the past and current stateoftheart dynamic mechanisms and analyze a new setting where the agents consist of buyers and sellers, known as exchange economies, and agents having value interdependency, which are relevant in applications illustrated through examples. We show that known results of dynamic mechanisms with independent value settings cannot guarantee certain desirable properties in this new significantly different setting. In the future work, we propose to analyze similar settings with dynamic types and population.
[PDF]

Performance Evaluation of DistanceHop Proportionality on Geometric Graph Models of Dense Sensor Network
Swaprava Nath and Anurag Kumar
International Conference on Performance EVALUation MEthodologies and TOOLS (VALUETOOLS), October 2123, 2008, Athens, Greece, pp 4247:110.
Abstract and Full PaperWireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes on a region in Euclidean space, e.g., the unit square. After deployment, the nodes selforganise into a mesh topology. In a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this paper, we analyse the performance of this approximation. We show that nodes with a certain hop distance from a fixed anchor node lie within a certain annulus with probability approaching unity as the number of nodes n → ∞.
[PDF] [slides]
We take a uniform, i.i.d. deployment of n nodes on a unit square, and consider the geometric graph on these nodes with radius r(n) = c√1n n/n. We show that, for a given hop distance h of a node from a fixed anchor on the unit square, the Euclidean distance lies within [(1ε)(h1)r(n), hr(n)], for ε > 0, with probability approaching unity as n → ∞. This result shows that it is more likely to expect a node, with hop distance h from the anchor, to lie within this annulus centred at the anchor location, and of width roughly r(n), which decreases as n increases. We show that if the radius r of the geometric graph is fixed, the convergence of the probability is exponentially fast. Similar results hold for a randomised lattice deployment. We provide simulation results that illustrate the theory, and serve to show how large n needs to be for the asymptotics to be useful.

Linear Antenna Array with Suppressed Sidelobe and Sideband Levels using Time Modulation
Swaprava Nath and Subrata Mitra
International Conference On Computers And Devices For Communication (CODEC), December 2006, Kolkata, India.
Abstract and Full PaperIn this paper, the goal is to achieve an ultra low sidelobe level (SLL) and sideband levels (SBL) of a time modulated linear antenna array. The approach followed here is not to give fixed level of excitation to the elements of an array, but to change it dynamically with time. The excitation levels of the different array elements over time are varied to get the low sidelobe and sideband levels. The mathematics of getting the SLL and SBL furnished in detail and simulation is done using the mathematical results. The excitation pattern over time is optimized using Genetic Algorithm (GA). Since, the amplitudes of the excitations of the elements are varied within a finite limit, results show it gives better sidelobe and sideband suppression compared to previous time modulated arrays with uniform amplitude excitations.
[PDF]

Improving Productive Output in InfluencerInfluencee Networks
Swaprava Nath and Balakrishnan Narayanaswamy
Technical Report.
Abstract and Full PaperIn social or organizational networks, it is often observed that different individuals put different levels of production effort depending on their position in the network. One possible reason is reward sharing, which incentivizes particular agents to spend effort in sharing information with others and increasing their productivity. We model the effort level in a network as a strategic decision made by an agent on how much effort to expend on the complementary tasks of information sharing and production. We conduct a gametheoretic analysis of incentive and information sharing in both hierarchical and general influencerinfluencee networks. Our particular interest is in understanding how different reward structures in a network influence this decision. We establish the existence of a unique purestrategy Nash equilibrium in regard to the choice made by each agent, and study the effect of the quality and cost of communication, and the reward sharing on the effort levels at this equilibrium. Our results show that a larger reward share from an influencee incentivizes the influencer to spend more effort, in equilibrium, on communication, capturing a freeriding behavior of well placed agents. We also address the reverse question of designing an optimal reward sharing scheme that achieves the effort profile which maximizes the system output. In this direction, for a number of stylized networks, we study the Price of Anarchy for this output, and the interplay between information and incentive sharing on mitigating the loss in output due to agent selfinterest.
[PDF]

Mechanism Design for Strategic Crowdsourcing
Swaprava Nath
PhD Thesis, Indian Institute of Science, Bangalore
December 2013.
Advisor: Y. Narahari
Abstract and Full ThesisThis thesis looks into the economics of crowdsourcing using game theoretic modeling. The art of aggregating information and expertise from a diverse population has been in practice since a long time. The Internet and the revolution in communication and computational technologies have made this task easier and given birth to a new era of online resource aggregation, which is now popularly referred to as crowdsourcing. Two important features of this aggregation technique are: (a) crowdsourcing is always human driven, hence the participants are rational and intelligent, and they have a payoff function that they aim to maximize, and (b) the participants are connected over a social network which helps to reach out to a large set of individuals. To understand the behavior and the outcome of such a strategic crowd, we need to understand the economics of a crowdsourcing network. In this thesis, we have considered the following three major facets of the strategic crowdsourcing problem.
[PDF] [Slides] [Presentation Video]
(i) Elicitation of the true qualities of the crowd workers: As the crowd is often unstructured and unknown to the designer, it is important to ensure if the crowdsourced job is indeed performed at the highest quality, and this requires elicitation of the true qualities which are typically the participants' private information.
(ii) Resource critical task execution ensuring the authenticity of both the information and the identity of the participants: Due to the diverse geographical, cultural, socioeconomic reasons, crowdsourcing entails certain manipulations that are unusual in the classical theory. The design has to be robust enough to handle fake identities or incorrect information provided by the crowd while performing crowdsourcing contests.
(iii) Improving the productive output of the crowdsourcing network: As the designer's goal is to maximize a certain measurable output of the crowdsourcing system, an interesting question is how one can design the incentive scheme and/or the network so that the system performs at an optimal level taking into account the strategic nature of the individuals. In the thesis, we design novel mechanisms to solve the problems above using game theoretic modeling. Our investigation helps in understanding certain limits of achievability, and provides design protocols in order to make crowdsourcing more reliable, effective, and productive. 
Self Organisation in Random Geometric Graph models
of Wireless Sensor Networks
Swaprava Nath
Masters Thesis, Indian Institute of Science, Bangalore
June 2008.
Advisor: Anurag Kumar
Abstract and Full ThesisWe consider the problem of selforganisation in dense wireless sensor networks. Wireless sensor networks can be viewed in terms of deployment of a large number of nodes in an Euclidean space. After deployment, the nodes are required to build a topology to communicate among themselves and also to a base station. In this process they should meet some performance criteria, e.g. coverage of the area to be monitored, connectivity of all the nodes in the network, the capacity of the wireless network, etc. Also, once an event is detected in the network, we need to localise the occurrence of the event with the information reaching the base station in an energy efficient way with minimum delay. These performance objectives are the issues addressed in selforganisation of wireless sensor networks (WSN).
[PDF] [Slides]
In this report, we first introduce the problem of selforganisation in general and then present a survey of the existing literature in this area. Later we formalise a very commonly used approximation of proportionality between the hopdistance (the minimum number of hops) and Euclidean distance for three different scenarios in dense networks. Our proofs bank on a certain geometric construction and union bound, and provide a sufficient condition. We provide simulation results that illustrate the theoretical result, and serve to show how large the number of nodes needs to be before the asymptotics are useful. We propose a localisation algorithm that uses this theory for a fixed anchor and a random node. We also introduce another algorithm for localisation that uses the empirical distribution of Euclidean distance given the hopdistance, which performs better than the previous one. Finally, we discuss few more issues related to the nonidealities in real sensor networks that require more understanding of the stochastic geometry of these networks and theoretical formalisation.
My small contribution towards a nicer IISc Thesis Format.