Smart home systems Part 13

Tham khảo tài liệu 'smart home systems part 13', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Memory management in smart home gateway 171 Case 1 si 1 Ể S . Then S cSi achieves A i w max M T S ScSi T S w . Case 2 si 1 e S . Let S S si 1 . Since the elements of S are incomparable and the dependence graph is a forest we have T S n T si 1 0 and therefore I T S I I T S - T Si 1 I and M T S M T Sr - M T Si 1 . By the definition of L si 1 we know that for L si 1 1 j i Sj is a descendant of Si 1 . T sj nT si 1 0 implying that S must be a subset of Sk where k L si 1 . Thus S cSk is a subset that achieves A i L si 1 max M T S ScSk T S w- T si 1 which when combined with Si 1 gives M T S M T S M T si 1 A i L si 1 M T si 1 . Equation 2 then follows by taking the maximum achievable memory over cases 1 and 2. Now we state the optimal algorithm. Optimal G S Ml The current set of service instances S the dependence forest G and the memory requirement Mt. Output A new dependence forest G describing the dependence among the bundles remaining after deleting a set of bundles whose total memory is at least Mt. 1. For each node s e S compute the accumulative size and memory c s T s and m s M T s 2. Call Traverse-forest G to get the post-order traversal s1 . sn of G and the set of indices L s s e V G . 3. Initialize A i 0 0 for all i 1 . n A 0 w 0 for all w 1 . n A 1 1 m s1 and A 1 w - for all w 2 . n. Build a dynamic programming table 4. For i 1 to n 5. For w 1 to n if c si 1 w if A i w m si 1 A L s 1 w - c si 1 A i 1 w A i w B i 1 w 0 else A i 1 w m si 1 A L si 1 w - c si 1 B i 1 w 0 else A i 1 w A i w B i 1 w 0. now compute optimal solution 6. S 0 i n k min w e n A i w Mt . 7. while i 0 if B i k 1 S SG si t L si k k c s . else I I 1. 8. For each s e S delete T s . 172 Smart Home Systems Thus we get an O n1 2 time O nh space algorithm for solving problem 1. 5. Performance evaluations We carried extensive studies to evaluate the proposed algorithms. First we compared the performance of the different algorithms in terms of the number of removed services to verify our new .