Mechanism Design In Grid And Sensor Networks

Distributed system can be regarded as a network which connects many agents. The agents in the traditional distributed system are assumed to be obedient, which means they will act according to the certain algorithm. When many computers connect with each other to form a distributed system, different components in the system might be rational and selfish. And this kind of system can be regarded as strategic, in other words, the components in the system have their own incentive and the strategic agents will react according to their own benefits. The incentive problem becomes very import when the rational and selfish agents only care about their own benefits.In this paper, we will focus on the incentive problems in Gird and sensor network, and design corresponding mechanism to assure the normal running of the system considering the selfish assumption.First of all, we did some research on the dynamic allocation problem in Grid. Most existing allocation algorithm is static, such as Minwork and so on. However, the static allocation algorithm suffers on the efficiency, scalability and practicality. In order to resolve these kinds of problems, we design a dynamic allocation mechanism. It assumes that all the tasks are generated randomly according to certain probability model, and we want all the tasks can be finished in the shortest time. A dynamic allocation mechanism is given by utilizing second price sealed auction, and the mechanism is proved to be efficient, scalable and Strategyproof.We also propose the mechanism problem in sensor network after researching the Sensor Web project of Microsoft. This project plans to connect all the sensor networks in the whole country or even the whole world. What's more, they also supply the API of the platform in order to make people upload their sensor resources freely. But we also found some serious problems, for example, the sensor resources in the platform do not increase obviously in a long time. This is to say that few people would like to upload there sensors for free. And we believe it is the consequence of lacking incentive. So we design an incentive mechanism to make people have incentive to upload their sensors. We divide the systems to two sides, one is the resource supplier and the other is the resource consumer. And we give a cost model to the supplier and value mode to the consumer. Then we consider three different application scenarios: one is the single supplier and multiple consumers, one is multiple suppliers and single consumer, the last one is multiple suppliers and multiple consumers. The corresponding mechanisms are also designed, and some of them are proved to be Strategyproof, which make sure that every side can give there real bid and make a rational decision.