?url_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rft.relation=http%3A%2F%2Fmiis.maths.ox.ac.uk%2Fmiis%2F662%2F&rft.title=Optimization+of+Lifetime+in+Sensor+Networks&rft.creator=Bansal%2C+N.&rft.creator=Bourne%2C+D.&rft.creator=Firat%2C+M.&rft.creator=de+Graaf%2C+M.&rft.creator=Kapodistria%2C+S.&rft.creator=Kumar%2C+K.&rft.creator=Meerman%2C+C.&rft.creator=Mitici%2C+M.&rft.creator=Nardi%2C+F.+R.&rft.creator=de+Rijk%2C+B.&rft.creator=Sarswat%2C+S.&rft.creator=Scardia%2C+L.&rft.subject=Technology%2FDevices&rft.subject=Information+and+communication+technology&rft.description=We+consider+the+problem+proposed+by+Thales+Nederland+at+the+SWI+2012+meeting.+Thales+Nederland+is+the+Dutch+branch+of+the+international+Thales+Group.+The+company+specializes+in+designing+and+producing+professional+electronics+for+defence+and+security+applications%2C+such+as+radar+and+communication+systems.+Moreover%2C+Thales+Nederland+acts+as+a+local+point+of+contact+for+the+complete+portfolio+of+the+Thales+Group.+During+the+SWI+2012+meeting%2C+on+behalf+of+Thales+Nederland%2C+Dr.+Maurits+de+Graaf+posed+several+questions+regarding+the+maximization+of+the+lifetime+of+a+wireless+sensor+network.+We+addressed+these+questions+during+the+workshop+and+our+most+significant+results+are+summarized+as+follows%3A+We+have+proven+that+this+lifetime+maximization+problem%2C+even+under+the+most+simple+constraints%2C+is+NP-complete%2C+so+it+is+not+possible+to+find+an+algorithm+that+gives+the+optimal+solution+within+polynomial+time.+Furthermore%2C+we+have+constructed+a+counterexample+to+illustrate+that+the+heuristic+currently+used+by+Thales+can+be+asymptotically+at+least+log+n+times+worse+than+the+optimal+solution.+Moreover%2C+we+have+developed+a+new+heuristic+and+have+illustrated+with+several+numerical+examples+that+it+performs+better+than+the+heuristic+currently+used+by+Thales.+Finally%2C+we+have+formulated+the+problem+as+a+linear+programming+problem+and+used+this+to+quantify+how+far+the+heuristic+used+by+Thales+is+from+being+optimal.&rft.date=2012&rft.type=Study+Group+Report&rft.type=NonPeerReviewed&rft.format=application%2Fpdf&rft.language=en&rft.identifier=http%3A%2F%2Fmiis.maths.ox.ac.uk%2Fmiis%2F662%2F1%2Fp3.pdf&rft.identifier=++Bansal%2C+N.+and+Bourne%2C+D.+and+Firat%2C+M.+and+de+Graaf%2C+M.+and+Kapodistria%2C+S.+and+Kumar%2C+K.+and+Meerman%2C+C.+and+Mitici%2C+M.+and+Nardi%2C+F.+R.+and+de+Rijk%2C+B.+and+Sarswat%2C+S.+and+Scardia%2C+L.++(2012)+Optimization+of+Lifetime+in+Sensor+Networks.++%5BStudy+Group+Report%5D+++++