In Mobile Ad Hoc Networks (MANETs), nodes depend on each other for routing and forwarding packets. However, to save power and other resources, nodes belonging to independent authorities may behave selfishly, and may not be willing to help other nodes. Such selfish behavior poses a real threat to the proper functioning of MANETs. One way to foster node cooperation is to introduce punishment for selfish nodes. Based on neighbor-monitoring techniques, a fully distributed solution to detect, punish, and re-admit selfish nodes, is proposed here. This solution provides nodes the same opportunity to serve/and be served by others. A light-weight solution regarding battery status is also proposed here. This solution requires neighbor monitoring only when necessary, thereby saving nodes battery power. Another effective way to solve the selfish-node problem is to reward nodes for their service according to their cost. To force nodes to show their true cost, truthful protocols are needed. A low overhead truthful routing protocol to find optimal routes is proposed in this thesis. The most prominent feature of this protocol is the reduction of overhead from existing solutions O(n3) to O(n2). A light-weight scalable truthful routing protocol (LSTOP) is further proposed, which finds near-least-cost paths in dense networks. LSTOP reduces overhead to O(n) on average, and O(n2) in worst case scenarios. Multiple path routing protocols are an effective alternative to single path routing protocols. A generic mechanism that can turn any table-driven multipath routing protocol into a truthful one, is outlined here. A truthful multipath routing protocol (TMRP), based on well-known AOMDV protocol, is presented as an example. TMRP incurs an only 2n message overhead for a route discovery, and can also achieve load balancing without compromising truthfulness. To cope with the selfish-node problem in the area of position-based routing, a truthful geographic forwarding (TGF) algorithm is presented. TGF utilizes three auction-based forwarding schemes to stimulate node cooperation. The truthfulness of these schemes is proven, and their performance is evaluated through statistical analysis and simulation studies.

Desertification, the deterioration of productive and fertile lands into barren and desolate deserts, usually occurs as a result of deforestation, drought, or improper planting and agriculture. This thesis investigates ways to provide reliefs such as water and shelter in a continuously desertifying landscape (Taklamakan desert, Xinjiang, China) for locals, pilgrims, travelers and expedition caravans. To create diverse experiences in the desert, both temporary and permanent structures are considered in this project to minimize further land degradation. Movements of historical trade routes, oasis towns, and modern population fluctuation are examined to determine strategies and locations for intervention. The progressions of architectural, environmental and cultural decay are revealed in three selected sites: the Kapakaskan Village, the Jafar Sadiq Shrine, and the ancient ruined city of Niya. The design and the primary area of study seek to explain and incorporate passive or low energy building systems, form, cultural community, and technological innovations.

With increasing demand for social network based activities, it is very important to understand not only the structural properties of social networks but also how social networks form, to better exploit their promise and potential. We believe the existing methods and tools for social network analysis have a major inadequacy: they do not capture the behavior (such as rationality and intelligence) of individuals nor do they model the strategic interactions that occur among these individuals. Game theory is a natural tool to overcome this inadequacy since it provides rigorous mathematical models of strategic interaction among autonomous, intelligent, and rational agents. This thesis brings out how a game theoretic approach helps analyze social networks better. In particular, we study three contemporary and pertinent problems in social networks using a game theoretic approach: determining influential individuals for viral marketing, community detection, and social network formation. The first problem deals with determining influential nodes in social networks for diffusion of information. We present an efficient heuristic algorithm (SPIN) to this problem based on cooperative game theoretic techniques. The running time of SPIN is independent of the number of influential nodes to be determined. Moreover, unlike the popular benchmark algorithms, the proposed method works well with both submodular and non-submodular objective functions for diffusion of information. In the second problem, we design a novel game theoretic approach to partition a given undirected, unweighted graph into dense subgraphs (or communities). The approach is based on determining a Nash stable partition which is a pure strategy Nash equilibrium of an appropriately defined strategic form game. In the proposed graph partitioning game, the nodes of the graph are the players and the strategy of a node is to decide to which community it ought to belong. The utility of each node is defined to depend entirely on the node’s local neighborhood. A Nash stable partition (NSP) of this game is a partition consisting of communities such that no node has incentive to defect from its community to any other community. Given any graph, we prove that an NSP always exists and we also derive a lower bound on the fraction of intra-community edges in any NSP. Our approach leads to an efficient heuristic algorithm to detect communities in social networks with the additional feature of automatically determining the number of communities. The focus of the third problem is to understand the patterns behind the evolution of social networks that helps in predicting the likely topologies of social networks. The topology of social networks plays a crucial role in determining the outcomes in several social and economic situations such as trading networks, recommendation networks. We approach the problem of topology prediction in networks by defining a game theoretic model, which we call value function -allocation rule model, that considers four determinants of network formation. This model uses techniques from both cooperative game theory and non-cooperative game theory. We characterize the topologies of networks that are in equilibrium and/or socially efficient. Finally, we study the tradeoffs between equilibrium networks and efficient networks.