Både heltal programmeringsmodeller och heuristiska algoritmer har föreslagits för att hitta minimal energi sändning och multicast träd i trådlösa ad hoc-nätverk. Bland heuristiska algoritmer är algoritmen för inkrementell sändning/multisändning (BIP/MIP) mest känd. Den teoretiska prestandan för BIP/MIP har kvantifierats i flera studier. För att bedöma den empiriska prestandan hos BIP/MIP och andra heuristiska algoritmer är det nödvändigt att beräkna ett optimalt träd eller en mycket bra lägre gräns för det optimala. I detta dokument presenterar vi ett heltal programmering samt förbättrade heuristiska algoritmer. Vårt heltal programmering strategi består av ett nytt heltal modell och ett avkopplingssystem. Till skillnad från tidigare föreslagna modeller leder den kontinuerliga avslappningen av vår modell till en mycket skarp nedre gräns för det optimala. Vårt avkopplingsprogram möjliggör prestandautvärdering av heuristik utan att behöva beräkna optimala träd. Våra bidrag till heuristiska algoritmer består av den effektförbättrande algoritmen på varandra följande effektjustering (SPA) och förbättrad tids komplexitet hos några tidigare föreslagna algoritmer. Vi rapporterar omfattande numeriska experiment. Algoritm SPA hittar bättre lösningar jämfört med en mängd andra algoritmer. Dessutom visar heltal programmering strategi att träd som hittats av algoritm SPA är optimala eller nästan optimala.
Baserat på ett heltal programmering strategi föreslås i REF, de fastställer den nedre gränsen för den optimala för MEB / MEM problem.
Minimum-energy broadcast and multicast in wireless networks: An integer programming approach and improved heuristic algorithms
{'venue': 'Ad Hoc Networks', 'journal': 'Ad Hoc Networks', 'mag_field_of_study': ['Computer Science']}