焼きなまし法を用いたTDMAスケジューリング技術

全文

(1)Vol.2013-SLDM-160 No.13 Vol.2013-EMB-28 No.13 2013/3/13. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ম͖ͳ·͠๏Λ༻͍ͨ TDMA εέδϡʔϦϯάٕज़ ਿ‫ ݪ‬ਅ1,a). ‫ؠ‬Ӭ ໌ਓ2. ֓ཁɿंࡌ޲͚ΞϓϦέʔγϣϯʹ୅ද͞ΕΔ࢈‫༻ۀ‬ΞϓϦέʔγϣϯΛ۩‫ݱ‬Խ͢ΔͨΊʹ͸ɼσουϥ Πϯ࣌ࠁ·ͰʹϊʔυؒͰ௨৴ϝοηʔδΛૹ৴͢ΔωοτϫʔΫγεςϜΛ҆Ձʹ࣮‫͢ݱ‬Δඞཁ͕͋Δɽ ຊߘͰ͸ɼ௨৴όεͷಈ࡞प೾਺Λ࡟‫͢ݮ‬Δ͜ͱ͕ɼϫΠϠϋʔωεͷ௿ίετԽʹߩ‫͢ݙ‬Δ͜ͱΛߟྀ ͠ɼϋʔυϦΞϧλΠϜ੍໿Լʹ͓͍ͯ௨৴όεͷಈ࡞प೾਺Λ࠷খԽ͢Δ TDMA εέδϡʔϦϯάٕज़ ΛఏҊ͢Δɽ۩ମతʹ͸ɼϑϨʔϜͷϖΠϩʔυ௕ɼ‫ͼٴ‬ɼεϩοτϚϧνϓϨΫγϯάΛ‫ؚ‬Ήૹ৴εέ δϡʔϧΛ࠷దԽ͠ɼFlexRay όεͷಈ࡞प೾਺Λ࠷খԽ͢Δɽ·ͣɼର৅ͱ͢Δઃ‫ܭ‬໰୊Λ਺ཧ໰୊ͱ ͯ͠ఆࣜԽ͢Δɽ͞Βʹɼઃ‫ܭ‬໰୊ͷղΛ‫ٻ‬ΊΔম͖ͳ·͠๏ʹ‫ͮ͘ج‬ղ๏Λ༩͑Δɽ‫ʹݧ࣮ػࢉܭ‬ΑΓɼ ఏҊख๏͸‫ط‬ଘख๏ͱൺ΂ɼ62.3ʙ63.2%ͷಈ࡞प೾਺Λ࡟‫͖Ͱݮ‬Δ͜ͱΛ֬ೝͨ͠ɽ ΩʔϫʔυɿTDMA ๏, ੡଄ίετ, ಈ࡞प೾਺, εϩοτϚϧνϓϨΫγϯά. Simulated Annealing-Based TDMA Scheduling Technique Abstract: A cost-effective communication mechanism that is capable of sending out a communication message from node to node by their deadline is required for realizing industrial applications such as automotive ones. Reduction of the operating frequency of a communication bus generally contributes to lowering the cost of wire harness. This paper presents a design paradigm in which we optimize the length of a payload segment of a frame and slot multiplexing under hard real-time constraints so that we can minimize the operating frequency of the communication bus. We formulate the above design problem as a mathematical problem. We also apply simulated annealing (SA) to solving the design problem. Our experimental results show that our technique achieved 62.3–63.2% less operating frequency comparing than that of a conventional one. Keywords: TDMA (time division multiple access) scheme, fabrication cost, operating frequency, slot multiplexing. 1. ͸͡Ίʹ ࣗಈं࢈‫͍͓ͯʹۀ‬͸ɼ‫ࡁܦ‬ੑɼ҆શੑɼ‫ͼٴ‬շదੑΛ ઈ͑ͣ௥‫͠ٻ‬ɼࣗಈं੡඼Λվྑ͠ଓ͚͍ͯΔɽࣗಈंͷ ਐԽ͸ΤϨΫτϩχΫεͷਐԽʹෛ͏ͱ͜Ζ͕େ͖͍ɽं ࡌΤϨΫτϩχΫε͸࣍ੈ୅ࣗಈंͷ։ൃʹ͓͍ͯΑΓॏ ཁͳ໾ׂΛՌͨ͢ͱߟ͑ΒΕΔɽ ंࡌΤϨΫτϩχΫε͸ߴՁͳిࢠσόΠεͱ഑ઢ͔Β ߏ੒͞ΕΔͨΊʹɼ঎‫ۀ‬త‫͔఺؍‬Β͸ɼγεςϜΛ҆Ձʹ ૊Έ্͛Δઃ‫ܭ‬ύϥμΠϜ͕‫ٻ‬ΊΒΕΔɽ‫ݱ‬ঢ়Ͱ͸ɼߴ‫ڃ‬ ंʹ͸ 100 ‫ݸ‬Λӽ͢ ECU(electronic control unit) ͕౥ࡌ͞ ΕɼECU ͸େ‫ن‬໛ͳωοτϫʔΫΛհͯ͠‫ʹ͍ޓ‬௨৴Λ ߦ͍ͬͯΔɽࣗಈंͷ࣮‫ʹݱ‬͸ɼߴ౓Ͱ͔ͭେ‫ن‬໛ͳ෼ࢄ γεςϜ͕ඞཁͰ͋Γɼ௿ίετͳ෼ࢄγεςϜΛઃ‫͢ܭ‬ Δٕज़ඞཁෆՄܽͰ͋Δɽ CAN (controller area network) ͸ɼ૬‫઀ޓ‬ଓ͞Εͨ‫ؒثػ‬ 1. 2. a). ‫۝‬भେֶγεςϜ LSI ‫ڀݚ‬ηϯλʔ System LSI Research Center, Kyushu University, 744 Motooka, Nishi-ku, Fukuoka, Fukuoka 819–0395, Japan ‫۝‬भେֶେֶӃ౷߹৽ྖҬֶ෎ΦʔτϞʔςΟϒαΠΤϯεઐ߈ Department of Automotive Science, Graduate School of Integrated Frontier Sciences, Kyushu University, 744 Motooka, Nishi-ku, Fukuoka, Fukuoka 819–0395, Japan [email protected]. ⓒ 2013 Information Processing Society of Japan. ͷσʔλసૹʹ༻͍ΒΕΔ௨৴ωοτϫʔΫͷඪ४Ͱ͋ ΓɼंࡌωοτϫʔΫʹ༻͍ΒΕ͍ͯΔ [2]ɽCAN ʹ͓͍ ͯ͸ɼϑϨʔϜͷ༏ઌ౓ʹ‫͍ͯͮج‬௨৴όεͷ࢖༻ॱং͕ ఆ·ΔͨΊʹɼ্Ґͷ༏ઌ౓Λ࣋ͭϑϨʔϜ͕ඇܾఆతʹ ૹ৴͞ΕΔ৔߹ɼԼҐͷ༏ઌ౓Λ࣋ͭϑϨʔϜͷ௨৴ϨΠ ςϯγ͸ඇܾఆతʹఆ·Δɽ௨৴ϨΠςϯγ͕ඇܾఆత ʹఆ·ΔͷͰ͋Ε͹ɼϦΞϧλΠϜੑΛอূ͢Δ͜ͱ͸ ೉͍͠ɽx-by-wire γεςϜͷΑ͏ͳϋʔυϦΞϧλΠϜ ੑ͕ཁ‫͞ٻ‬ΕΔγεςϜʹ CAN Λద༻͢Δࣄ͸ࠔ೉Ͱ͋ Δ [3]ɽFlexRay ͸ TDMA (time division multiple access) ๏ ʹ‫͍͠৽͍ͨͮج‬ωοτϫʔΫඪ४Ͱ͋Γɼωοτϫʔ ΫଳҬ෯Λ࢖༻͢Δ্Ͱɼ௨৴ϨΠςϯγʹ͓͚Δܾఆ ੑͱॊೈੑΛ݉Ͷඋ͍͑ͯΔ [4]ɽFlexRay ͷ௨৴‫ߏػ‬͸ Static TDMA ๏Ͱ௨৴ϨΠςϯγʹ͓͚ΔܾఆੑΛఏ‫͠ڙ‬ɼ Flexible TDMA ๏Ͱ௨৴ଳҬ෯ʹ͓͚ΔॊೈੑΛ༩͑Δɽ FlexRay ͷ௨৴‫ߏػ‬ͷઃ‫ܭ‬ύϥμΠϜʹ͍ͭͯ‫͢ڀݚ‬Δ ࣄ͸٤‫ۓ‬ͷ՝୊Ͱ͋Δɽզʑ͸͜Ε·Ͱʹɼ௨৴όεͷಈ ࡞प೾਺Λ࡟‫͢ݮ‬Ε͹ɼϫΠϠϋʔωεͷௐୡίετΛ࡟ ‫͖Ͱݮ‬Δ఺ʹண໨͠ɼϑϨʔϜͷϖΠϩʔυηάϝϯτͷ େ͖͞Λ࠷దԽ͠ɼ௨৴όεͷಈ࡞प೾਺Λ࠷খԽ͢Δઃ ‫ํܭ‬๏࿦ΛఏҊͨ͠ [10, 11]ɽ͞Βʹɼసૹ͞ΕΔσʔλͷ ‫ޡ‬Γ཰Λߟྀͨ͠ TDMA εέδϡʔϦϯάٕज़ΛఏҊ͠. 1.

(2) Vol.2013-SLDM-160 No.13 Vol.2013-EMB-28 No.13 2013/3/13. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report t communication cycle level. static segment. arbitration grid level. static slot. dynamic segment. symbol window. static minislot minislot slot action action point point. network idle time. action point. macrotick level macrotick microtick level. microtick. ਤ1. ௨৴αΠΫϧ಺ͷ࣌ؒ֊૚ɽ. ͨ [5]ɽ͜ΕΒͷ‫Ͱڀݚ‬͸ɼεϩοτϚϧνϓϨΫγϯάɼ ͢ͳΘͪɼෳ਺ͷ௨৴αΠΫϧʹ࿱Γɼෳ਺ͷ௨৴৴߸Λ ಉҰͷεϩοτʹׂΓ౰ͯΔٕ๏ɼΛߟྀ͓ͯ͠Βͣɼޮ Ռతʹಈ࡞प೾਺Λ࡟‫͢ݮ‬Δ͜ͱ͕Ͱ͖ͳ͍ɽຊߘͰ͸ɼ εϩοτϚϧνϓϨΫγϯάΛߟྀ͠ɼFlexRay όεͷಈ ࡞प೾਺Λ࠷খԽ͠ɼFlexRay ͷ௨৴‫ߏػ‬Λ੡଄͢ΔͨΊ ʹඞཁͳίετΛ࡟‫͢ݮ‬Δઃ‫ํܭ‬๏࿦ΛఏҊ͢Δɽ۩ମత ʹ͸ɼϑϨʔϜͷϖΠϩʔυ௕ɼ‫ͼٴ‬ɼεϩοτϚϧνϓ ϨΫγϯάΛ‫ؚ‬Ήૹ৴εέδϡʔϧΛ࠷దԽ͠ɼ௨৴όε ͷಈ࡞प೾਺Λ࠷খԽ͢Δઃ‫ٕܭ‬ज़ΛఏҊ͢Δɽόεͷಈ ࡞प೾਺Λ࡟‫͢ݮ‬Δ͜ͱʹΑͬͯɼΑΓ௿଎Ͱ҆Ձͳ഑ઢ Λ࢖༻Ͱ͖ɼFlexRay ωοτϫʔΫγεςϜΛ੡଄͢Δί ετΛ࡟‫͖Ͱݮ‬Δɽ ຊߘͷ࢒Γ͸࣍ͷΑ͏ʹߏ੒͞ΕΔɽ2 અͰ͸ɼFlexRay ωοτϫʔΫϓϩτίϧʹ͍ͭͯ؆୯ʹड़΂Δɽ3 અͰ͸ɼ ຊߘͰऔΓѻ͏ઃ‫ܭ‬໰୊ΛఆࣜԽ͠ɼઃ‫ܭ‬໰୊ͷղ๏ͱ͠ ͯম͖ͳ·͠๏Λద༻͢Δɽ4 અͰ͸ɼ࣮‫݁ݧ‬ՌʹΑΓఏ Ҋख๏ͷ༗ޮੑʹ͍ͭͯٞ࿦͢Δɽ5 અͰ݁࿦Λड़΂Δɽ. 2. FlexRay ຊઅͰ͸ FlexRay ඪ४ʹ͍ͭͯ؆୯ʹௐࠪ͢ΔɽFlexRay ʹؔ͢Δৄࡉ͸࢓༷ॻΛࢀর͞Ε͍ͨ [4]ɽ. 2.1 ௨৴αΠΫϧ ௨৴αΠΫϧ͸ɼFlexRay γεςϜͷϝσΟΞΞΫηε ๏Λߏ੒͢ΔͨΊʹप‫ظ‬తʹ‫܁‬Γฦ͞ΕΔ௨৴ߏ଄ͷҰͭ ͷΠϯελϯεͰ͋Δɽ௨৴αΠΫϧ͸࣌ؒ֊૚ʹΑͬͯ ఆٛ͞ΕΔɽ࣌ؒ֊૚͸࢛ͭͷ࣌ؒ֊૚Ϩϕϧ͔Βߏ੒͞ ΕΔɽ͢ͳΘͪɼϚΠΫϩςΟοΫϨϕϧɼϚΫϩςΟο ΫϨϕϧɼΞʔϏτϨʔγϣϯάϦουϨϕϧɼ‫ͼٴ‬௨৴ αΠΫϧϨϕϧͷ࢛ͭͰ͋ΔɽҰͭͷ௨৴αΠΫϧʹண໨ ͨ࣌ؒ͠֊૚Λਤ 1 ʹࣔ͢ɽ ௨৴αΠΫϧϨϕϧͰ͸ɼ௨৴αΠΫϧ͕‫܁‬Γฦ࣮͠ߦ ͞ΕΔɽҰͭͷ௨৴αΠΫϧʹ͸ɼ੩తηάϝϯτɼಈతη άϝϯτɼγϯϘϧ΢Οϯυ΢ɼ‫ͼٴ‬ωοτϫʔΫΞΠυϧ ͕࣌ؒ‫·ؚ‬ΕΔɽຊߘͰ͸ಛʹ੩తηάϝϯτʹ஫໨͢Δɽ ੩తηάϝϯτ಺Ͱ͸ɼૹ৴Λௐఀ͢ΔͨΊʹ TDMA(time division multiple scheme) ๏͕༻͍ΒΕΔɽTDMA ๏͸‫ڞ‬ ༗͞ΕΔ௨৴࿏ͷͨΊͷ௨৴࿏ΞΫηε๏Ͱ͋ΔɽTDMA ๏Ͱ͸ɼνϟωϧΛ࣌ؒతʹ෼ׂ͠ɼλΠϜεϩοτ͕ઃ ͚ΒΕΔɽ֤ʑͷλΠϜεϩοτ͸ɼ͋Β͔͡Ί‫ڐ‬Մ͞Ε ͨ௨৴ϝοηʔδͷΈ͕࢖༻Ͱ͖Δɽಈతηάϝϯτ಺ Ͱ͸ɼૹ৴Λௐఀ͢ΔͨΊʹ FTDMA(flexible time division multiple access) ๏͕༻͍ΒΕΔɽγϯϘϧ΢Οϯυ΢͸ ⓒ 2013 Information Processing Society of Japan. ωοτϫʔΫʹγϯϘϧΛૹΔͨΊʹ༻͍ΒΕΔ௨৴‫ؒظ‬ Ͱ͋ΔɽωοτϫʔΫΞΠυϧ࣌ؒ͸ɼ௨৴͕ߦΘΕͳ͍ ‫͋Ͱؒظ‬Γɼ௨৴αΠΫϧΛ‫݁͢׬‬Δ΋ͷͰ͋Δɽ ࣍ͷԼҐͷϨϕϧͰ͋ΔΞʔϏτϨʔγϣϯάϦουϨ ϕϧ͸ΞʔϏτϨʔγϣϯάϦουΛ‫ؚ‬Ήɽ੩తηάϝϯ τͰ͸ɼΞʔϏτϨʔγϣϯάϦου͸੩తεϩοτͱ‫ݺ‬ ͹ΕΔ࿈ଓ͢Δִ࣌ؒؒͰߏ੒͞ΕΔɽಈతηάϝϯτͰ ͸ɼΞʔϏτϨʔγϣϯάϦου͸ϛχεϩοτͱ‫ݺ‬͹Ε Δ࿈ଓ͢Δִ࣌ؒؒͰߏ੒͞ΕΔɽ ΞʔϏτϨʔγϣϯάϦουϨϕϧ͸ϚΫϩςΟοΫϨ ϕϧͷ্ʹҐஔ͠ɼϚΫϩςΟοΫʹΑͬͯఆٛ͞ΕΔɽ ϚΫϩςΟοΫ͸άϩʔόϧ࣌ؒΛද͢࠷খ୯ҐͰ͋Δɽ ਤ 1 ʹࣔ͞ΕΔϚΫϩςΟοΫͷ‫ڥ‬ք͸ΞΫγϣϯϙΠϯ τͱ‫ݺ‬͹ΕΔɽΞΫγϣϯϙΠϯτ͸ૹ৴‫ ͕ث‬FlexRay ϑ ϨʔϜͷૹ৴Λ։࢝͢Δ࣌ࠁͰ͋Δɽ ࣌ؒ֊૚ʹ͓͍ͯ࠷΋௿͍Ϩϕϧ͸ϚΠΫϩςΟοΫͰ ͋ΔɽҰͭͷϚΠΫϩςΟοΫ͸࣌ؒʹ͓͚ΔҰִؒΛࣔ ͠ɼϊʔυʹ‫ॴہ‬తͳ֓೦Ͱ͋Δɽ. 2.2 ϝσΟΞΞΫηε੍‫ޚ‬ FlexRay ͷϓϩτίϧʹ͓͍ͯ͸ɼϝσΟΞΞΫηε੍ ‫ޚ‬͸‫܁‬Γସ͑͞ΕΔ௨৴αΠΫϧʹ‫͍͍ͯͮج‬Δɽ௨৴α ΠΫϧ಺ʹ͓͍ͯ͸ɼFlexRay ͸ೋͭͷϝσΟΞΞΫηε ๏Λఏ‫͢ڙ‬Δɽ͢ͳΘͪɼSTDMA(static time division multiple access) ๏ɼ‫ ͼٴ‬FTDMA (flexible time division multiple access) ๏Ͱ͋Δɽલऀͷํ๏͸੩తηάϝϯτͰ༻͍Β Εɼ‫ऀޙ‬ͷํ๏͸ಈతηάϝϯτͰ༻͍ΒΕΔɽύέοτ ͷΑ͏ʹૹ৴ͷ୯ҐͰ͋Δ௨৴ϑϨʔϜ͸੩తηάϝϯτ ‫ͼٴ‬ಈతηάϝϯτͷ྆ऀͰૹΒΕΔɽຊߘͰ͸؆୯ʹ੩ తηάϝϯτͷͨΊͷ TDMA ๏ʹ͍ͭͯ؆୯ʹௐࠪ͢Δɽ શͯͷϑϨʔϜ͸֤ʑͷϑϨʔϜ ID Λ͍࣋ͬͯΔɽϑ ϨʔϜ ID ͸ϢχʔΫʹ੩తεϩοτʹରԠ෇͚ΒΕ͓ͯ ΓɼϑϨʔϜ ID ʹΑͬͯૹ৴εϩοτ͕ܾఆ͞ΕΔɽϑ ϨʔϜ ID ΛϊʔυʹϢχʔΫʹׂΓ౰ͯΔ͜ͱͰௐఀ͸ ࣮‫͞ݱ‬ΕΔɽ৽͍͠੩తεϩοτʹͳΔͱɼεϩοτΧ΢ ϯλ͸ͦͷ஋ΛҰͭ૿Ճ͢ΔɽϑϨʔϜͷϑϨʔϜ ID ͕ εϩοτΧ΢ϯλͱҰகͨ͠ͱ͖ʹɼ౰֘ϑϨʔϜ͸ૹΒ ΕΔɽεϩοτΧ΢ϯλͷॳ‫ظ‬஋͸ 1 Ͱ͋Δɽ੩తηάϝ ϯτͷऴΘΓʹεϩοτΧ΢ϯλ͸ 1 ʹ࠶ॳ‫ظ‬Խ͞ΕΔɽ શͯͷ੩తηάϝϯτ͸ಉ͡਺ͷϚΫϩςΟοΫ͔Βߏ ੒͞ΕΔɽҰͭͷ੩తηάϝϯτͷϚΫϩςΟοΫ਺͸େ Ҭతʹఆ਺Ͱ͋Δɽਤ 2 ʹ੩తηάϝϯτͷλΠϛϯάͷ ৄࡉΛࣔ͢ɽ channel active. channel idle channel delimiter idle. frame ID 1. channel active. channel idle channel delimiter idle. frame ID 2. t. macrotick static slot action point action point offset. static slot action point action point offset static slot. slot counter 1. static slot 2. ਤ 2 ੩తηάϝϯτ಺ͷλΠϛϯάɽ. 2.3 ϑϨʔϜϑΥʔϚοτ FlexRay ϑϨʔϜ͸ૹ৴ͷͨΊͷೖΕ΋ͷͰ͋Γɼࡾͭ. 2.

(3) Vol.2013-SLDM-160 No.13 Vol.2013-EMB-28 No.13 2013/3/13. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ͷηάϝϯτ͔Βߏ੒͞ΕΔɽ͢ͳΘͪɼϔομηάϝϯ τɼϖΠϩʔυηάϝϯτɼ‫ͼٴ‬τϨʔϥηάϝϯτͰ͋ Δɽਤ 3 ʹ FlexRay ϑϨʔϜͷϑΥʔϚοτΛࣔ͢ɽ ϊʔυ͸ϔομηάϝϯτɼϖΠϩʔυηάϝϯτɼ‫ٴ‬ ͼτϨʔϥηάϝϯτͷॱͰϑϨʔϜΛૹ৴͢Δɽਤ 3 ʹ ͓͍ͯɼ‫ݸ‬ʑͷηάϝϯτʹ͓͍ͯɼϊʔυ͸ࠨ͔Βӈͷ ॱংͰσʔλΛૹ৴͢Δɽ. Reserved bit Payload preamble indicator Numm frame indicator Sync frame indcator Start up indicator Frame Payload Header Cycle Data 0 Data 1 Data 2 ID length CRC count 11 bits. 7 bits 11 bits 6 bits. Header Segment. Data n CRC CRC CRC. 0 ... 254 bytes. 24 bits. Payload Segment. Trailer Segment. 111111. ਤ3. ϑϨʔϜͷϑΥʔϚοτɽ. 2.4 ϑϨʔϜͷූ߸Խ FlexRay ϑϨʔϜ͸ 5 ͭͷϏοτྻͰූ߸Խ͞ΕΔɽ͢ ͳΘͪɼૹ৴։࢝ྻ (TSS: transmission start sequence)ɼϑ ϨʔϜ։࢝ྻ (FSS: frame start sequence)ɼόΠτ։࢝ྻ (BSS: byte start sequence)ɼϑϨʔϜऴྃྻ (FES: frame end sequence)ɼ‫ͼٴͼٴ‬ಈతϑϨʔϜࢦࣔྻ (DTS: dynamic trailing sequence) Ͱ͋ΔɽTSS ‫ ͼٴ‬FSS ͸ϑϨʔϜͷ։࢝ ࣌ʹૠೖ͞ΕΔɽϑϨʔϜͷશͯͷόΠτʹ͸ͦͷઌ಄ ʹ BSS ͕ૠೖ͞ΕΔɽFES ͸ϑϨʔϜͷ‫ʹޙ‬ૠೖ͞ΕΔɽ DTS ͸ಈతηάϝϯτʹ͓͍ͯϑϨʔϜͷ FES ͷ௚‫ʹޙ‬ ૠೖ͞ΕΔɽ ਤ 4 ʹɼ੩తηάϝϯτͷූ߸Խ͞ΕͨϑϨʔϜΛࣔ ͢ɽTSS ͸ωοτϫʔΫΛհͯ͠ద੾ͳ઀ଓ४උΛ։࢝͢ ΔͨΊʹ༻͍ΒΕΔɽૹ৴ϊʔυ͸ɼFlexRay ͷύϥϝʔ λͰ‫ن‬ఆ͞ΕΔҰఆ‫ؒظ‬࿈ଓ͢Δ LOW ৴߸͔Βߏ੒͞Ε Δ TSS Λੜ੒͢ΔɽFSS ͕ TSS ͷ‫ʹޙ‬ଓ͘ɽFSS ͸ TSS ͷ‫ޙ‬ͷ࠷ॳͷ BSS ʹ͓͍ͯ͋ΓಘΔྔࢠԽ‫ࠩޡ‬Λิ͏ͨ Ίʹ༻͍ΒΕΔɽFSS ͸ 1 Ϗοτ࣌ؒͷ HIGH ৴߸ʹΑͬ ͯߏ੒͞ΕΔɽϊʔυ͸ૹ৴͞ΕΔϑϨʔϜͷ TSS ͷ௚‫ޙ‬ ͷϏοτετϦʔϜʹ FSS Λ௥Ճ͢ΔɽBSS ͸ड৴σό ΠεʹϏοτετϦʔϜͷλΠϛϯά৘ใΛ༩͑ΔͨΊʹ ༻͍ΒΕΔɽBSS ͸ 1 Ϗοτ࣌ؒͷ HIGH ৴߸ͱ 1 Ϗοτ ࣌ؒͷ LOW ৴߸͔Βߏ੒͞ΕΔɽϑϨʔϜσʔλͷ֤ό Πτ͸ɼҰͭͷ BSS ͱ 8 Ϗοτͷσʔλྻ͔Βߏ੒͞ΕΔ ֦ுόΠτྻͱͯ͠ɼ௨৴࿏Ͱૹ৴͞ΕΔɽFES ͸ϑϨʔ Ϝͷ࠷‫ޙ‬ͷόΠτྻͷऴྃΛࣔͨ͢Ίʹ༻͍ΒΕΔɽFES ͸ 1 Ϗοτ࣌ؒͷ LOW ৴߸ͱ 1 Ϗοτ࣌ؒͷ HIGH ৴߸ Ͱߏ੒͞ΕΔɽϊʔυ͸ϑϨʔϜͷ࠷‫ޙ‬ͷ֦ுόΠτྻͷ ௚‫ޙ‬ͷϏοτετϦʔϜʹ FES Λ෇Ճ͢Δɽ. FSS TxD. 1st byte sequence. last byte sequence. HIgh Low TSS. BSS. BSS. BSS. ਤ 4 ϑϨʔϜͷූ߸Խɽ. FES. 3. εϩοτϚϧνϓϨΫγϯά࠷దԽ໰୊ ௨৴όεͷಈ࡞प೾਺Λ࡟‫͢ݮ‬Δ͜ͱʹΑͬͯɼγες Ϝߏஙʹ༻͍ΔϫΠϠϋʔωεͷௐୡίετΛ཈੍͢Δ͜ ͱ͕Ͱ͖Δɽຊߘ͸ɼϋʔυϦΞϧλΠϜ੍໿ͷԼͰɼε ϩοτϚϧνϓϨΫγϯά‫ͼٴ‬ϑϨʔϜͷϖΠϩʔυ௕Λ ࠷దԽ͠ɼόεͷಈ࡞प೾਺Λ࠷খԽ͢Δઃ‫ํܭ‬๏࿦Λఏ Ҋ͢ΔɽຊઅͰ͸ɼର৅ͱ͢Δઃ‫ܭ‬໰୊ΛఆࣜԽ͠ɼઃ‫ܭ‬ ໰୊ͷղ๏ͱͯ͠ম͖ͳ·͠๏ΛԠ༻͢Δɽ. 3.1 ఆࣜԽ ຊߘͰ͸ɼ௨৴ϊʔυ͕σουϥΠϯ·Ͱʹ‫ݻ‬ఆ௕ͷ σʔλΛૹΔཁ‫ٻ‬Λप‫ظ‬తʹɼ͋Δ͍͸ɼඇप‫ظ‬తʹൃ͢ ΔৼΔ෣͍Λ௨৴৴߸ͱఆٛ͢Δɽ·ͨɼͦΕͧΕͷૹ৴ ཁ‫ૹ͍͓ͯʹٻ‬৴ର৅ͱͳΔ‫ݻ‬ఆ௕σʔλΛ௨৴ϝοηʔ δͱ‫Ϳݺ‬ɽ࣮૷ͷ‫͔఺؍‬Β͸ɼ௨৴ϝοηʔδ͸Ұ‫ݸ‬Ҏ্ ͷϑϨʔϜʹ֨ೲ͞Εɼૹ৴‫ݩ‬ϊʔυ͔Βૹ৴ઌϊʔυʹ ૹΒΕΔ͜ͱͱͳΔɽ໰୊ͷ؆୯ԽͷͨΊʹɼຊߘͰ͸प ‫ظ‬తͳ௨৴৴߸͔Βߏ੒͞ΕΔωοτϫʔΫγεςϜΛԾ ఆ͢Δɽ௨৴ϝοηʔδ͕ඇप‫ظ‬తʹૹΒΕΔωοτϫʔ ΫγεςϜ͸ɼҰൠੑΛࣦΘͣʹप‫ظ‬తͳγεςϜʹม‫׵‬ ͢Δ͜ͱ͕Ͱ͖Δɽ௨৴ϝοηʔδͷ࠷খִؒΛ௨৴৴߸ ͷप‫͢ͱظ‬Δ͜ͱͰɼඇप‫ظ‬త৴߸Λप‫ظ‬త৴߸ͱΈͳ͢ ͜ͱ͕Ͱ͖Δɽ௨৴৴߸͸࢛ͭ૊ (N, C, D, S ) Ͱද͞ΕΔɽ ͜͜ͰɼN ͸ωοτϫʔΫϊʔυΛɼC ͸प‫ظ‬ΛɼD ͸૬ ରσουϥΠϯ࣌ࠁΛɼS ͸௨৴ϝοηʔδͷϏοτ਺Λ ࣔ͢ɽωοτϫʔΫϊʔυ N ͸ C ୯Ґ࣌ؒຖʹ S Ϗοτ ͷ௨৴ϝοηʔδΛૹ৴͢Δཁ‫ٻ‬Λൃ͠ɼͦΕͧΕͷ௨৴ ϝοηʔδΛɼૹ৴ཁ‫ͤൃ͕ٻ‬ΒΕ͔ͯΒ D ୯Ґ࣌ؒҎ಺ ʹૹΓऴΘΔඞཁ͕͋ΔͱԾఆ͢Δɽ Nsig ‫ݸ‬ͷ௨৴৴߸ S = {s1 , s2 , · · · , sNsig } ͕ɼq ‫ݸ‬ͷ੩తε ϩοτ͔Βߏ੒͞ΕΔ੩తηάϝϯτʹΑͬͯૹ৴͞Ε ΔωοτϫʔΫγεςϜΛߟ͑Α͏ɽຊߘͰ͸ɼ੩తε ϩοτͷ਺ q Λม਺ͱͯ͠औΓѻ͏ɽ௨৴৴߸ si ͸࢛ͭ૊ (Ni , Ci , Di , S i ) Ͱఆٛ͞ΕΔɽҰͭͷ௨৴৴߸ʹରͯ͠ɼҰ ͭͷ௨৴αΠΫϧʹ͓͍ͯ͸ߴʑҰͭͷ੩తεϩοτׂ͕ Γ౰ͯΒΕΔͱԾఆ͢ΔɽωοτϫʔΫγεςϜͷಈ࡞प ೾਺͸ w Ͱ͋ΓɼϘʔϨʔτ͸ w bps Ͱ͋Δͱ͢ΔɽΑΓ ௿͍ಈ࡞प೾਺Λ࣮‫͢ݱ‬Δ͜ͱʹΑͬͯΑΓ҆ՁͳϫΠϠ ϋʔωεΛબ୒Ͱ͖Δͱͷલఏʹཱͪɼ໨తؔ਺Λ௨৴ό εͷಈ࡞प೾਺ w ͷ࠷খԽͱ͢Δɽ Ұͭͷ௨৴ϝοηʔδ͸Ұ‫ݸ‬Ҏ্ͷϑϨʔϜͷ‫ૹͰܗ‬Β ΕΔɽਤ 3 ʹࣔ͢Α͏ʹɼҰͭͷϑϨʔϜ͸ϔομηά ϝϯτɼϖΠϩʔυηάϝϯτɼ‫ͼٴ‬τϨʔϥηάϝϯτ ͔Βߏ੒͞ΕΔɽຊߘͰ͸ɼϔομηάϝϯτͷେ͖͞‫ٴ‬ ͼτϨʔϥηάϝϯτͷϏοτྔΛͦΕͧΕ Bhd ‫ ͼٴ‬Btl ͱ͢ΔɽϖΠϩʔυηάϝϯτͷେ͖͞͸ɼઃ‫͕ऀܭ‬ఆ ΊΒΕΔ΋ͷͰ͋Δ͕ɼ೚ҙͷ੩తηάϝϯτʹ͓͍ͯ ಉҰͰ͋Δඞཁ͕͋ΔɽҰͭͷϖΠϩʔυηάϝϯτ͸ p (0 ≤ p ≤ 127) ‫ݸ‬ͷ 16 Ϗοτϫʔυ͔Βߏ੒͞ΕΔͱ͢Δɽ ͳ͓ɼFlexRay ͷඪ४ʹ͓͍ͯ͸ɼϖΠϩʔυηάϝϯτͷ େ͖͞͸‫਺ۮ‬όΠτͰ͋Δͱ͞Εɼͦͷൣғ͸ 0 Ҏ্ 254 ҎԼͰ͋Δ͜ͱ͕‫ن‬ఆ͞Ε͍ͯΔɽϑϨʔϜͷϏοτ௕ f ͸ҎԼͷΑ͏ʹࣔ͞ΕΔɽ f = Bhd + Btl + 16p.. (1). ූ߸Խ͞ΕͨϑϨʔϜͷେ͖͞ fenc ͸ҎԼͷΑ͏ʹද͞ ΕΔɽ ⓒ 2013 Information Processing Society of Japan. 3.

(4) Vol.2013-SLDM-160 No.13 Vol.2013-EMB-28 No.13 2013/3/13. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. f fenc = f + BTSS + BFSS + · BBSS + BFES + BDLM + BIDL 8 BBSS = 1+ f + BTSS + BFSS + BFES + BDLM + BIDL 8 (2) = (16 + 2BBSS ) p + O, BBSS (Bhd + Btl ) O= 1+ 8 + BTSS + BFSS + BFES + BDLM + BIDL . (3) ͜͜Ͱɼ BTSS , BFSS , BBSS , BFES , BDLM , and BIDL ͸ͦΕͧΕ TSSɼFSSɼBSSɼFESɼνϟωϧΞΠυϧσϦϛλɼ‫ͼٴ‬ νϟωϧΞΠυϧ࣌ؒΛද͢ɽ આ໌ͷ؆୯ԽͷͨΊʹɼϋʔυσουϥΠϯ੍໿Λ࣋ͭ ௨৴৴߸͚͕ͩ༩͑ΒΕΔͱ͠ɼҰͭͷ௨৴αΠΫϧ͸Ұ ͭͷ੩తηάϝϯτ͚ͩͰߏ੒͞ΕΔͱ͢ΔɽຊઅͰఆٛ ͞ΕΔ໰୊͸ɼಈతηάϝϯτɼγϯϘϧ΢Οϯυ΢ɼ‫ٴ‬ ͼωοτϫʔΫΞΠυϧλΠϜ͕‫ݻ‬ఆ௕Ͱ͋Δ‫ݶ‬Γɼ੩త ηάϝϯτɼಈతηάϝϯτɼγϯϘϧ΢Οϯυ΢ɼ‫ͼٴ‬ ωοτϫʔΫΞΠυϧλΠϜΛ࣋ͭγεςϜʹ֦ுͰ͖ ΔɽԾఆ͔Βɼ1 ͭͷ௨৴αΠΫϧͷ࣌ؒ tcc ͸ q ‫ݸ‬ͷ੩త ηάϝϯτͷ࣌ؒͱ౳͘͠ɼҎԼͷΑ͏ʹࣔ͞ΕΔɽ. tcc =. q · fenc w. = {(16 + 2BBSS ) p + O}. q . w. (4). ͜͜Ͱɼq ͸Ұͭͷ௨৴αΠΫϧΛߏ੒͢Δ੩తεϩοτ ਺Λද͢੔਺ม਺Ͱ͋Γɼw ͸ FlexRay όεͷಈ࡞प೾਺ Λද࣮͢਺ม਺Ͱ͋Δɽ FlexRay ͷඪ४Ͱ͸ɼεϩοτϚϧνϓϨΫγϯάɼ͢ ͳΘͪɼෳ਺ͷ௨৴αΠΫϧʹ࿱Γɼෳ਺ͷ௨৴৴߸Λಉ Ұͷ੩తεϩοτʹׂΓ౰͍ͯΔٕ๏ɼΛ‫ڐ‬༰͍ͯ͠Δɽ ۩ମతʹ͸ɼ64 ‫ݸ‬ͷ௨৴αΠΫϧʹ࿱Γɼ࠷େ 64 ‫Ͱ·ݸ‬ ͷ௨৴৴߸ΛಉҰͷ੩తεϩοτʹׂΓ౰ͯΔ͜ͱΛ‫ڐ‬༰ ͍ͯ͠Δɽ64 ‫ݸ‬ͷ௨৴αΠΫϧ͸‫܁‬Γฦ͠ग़‫͢ݱ‬Δ͜ͱͱ ͳΔɽεϩοτϚϧνϓϨΫγϯάΛ༻͍Δ͜ͱͰɼ࣮ߦ ଳҬ෯ͷ࢖༻ޮ཰͕޲্͢Δ͕ɼઃ‫͕ۭؒܭ‬େ͖͘ͳΔͨ Ίʹɼඅ΍͢΂͖ઃ‫ܭ‬ΤϑΥʔτ͸૿Ճ͢Δɽ໰୊ͷ؆୯ ԽͷͨΊʹɼ੔਺ม਺ ai (0 ≤ ai ≤ 6) Λಋೖ͠ɼҰͭͷ௨ ৴৴߸͸ 64 ‫ݸ‬ͷ௨৴αΠΫϧͰɼ2ai ‫ݸ‬ͷ੩తεϩοτΛ ফඅ͠ɼ26−ai ‫ݸ‬ͷ௨৴αΠΫϧຖʹҰͭͷ੩తεϩοτΛ ফඅ͢ΔͱԾఆ͢Δɽ·ͨɼ੔਺ม਺ bi (0 ≤ bi ≤ 6) Λಋ ೖ͠ɼҰͭͷ௨৴ϝοηʔδΛૹΔͨΊʹ 2bi ‫ݸ‬ͷϑϨʔ Ϝʢ੩తεϩοτʣΛ༻͍ΔͱԾఆ͢Δɽ γάφϧ i ͷ௨৴ϝοηʔδͷେ͖͞ S i ͸ɼׂΓ౰ͯ ΒΕͨ੩తηάϝϯτͰૹΔ͜ͱ͕Ͱ͖ΔϑϨʔϜͷϖΠ ϩʔυηάϝϯτͷ૯‫ܭ‬Λ௒͑ͯ͸ͳΒͳ͍ɽΑͬͯɼҎ ԼͷΑ͏ͳ੍໿͕ಋೖ͞ΕΔɽ. 2bi +4 p ≥ S i , ∀i.. (5). ௨৴৴߸ͷసૹཁ‫ٻ‬Λຬͨ͢సૹೳྗΛ࣮‫͢ݱ‬Δඞཁ ͕͋Δɽ͢ͳΘͪɼҰͭͷ௨৴ϝοηʔδΛૹ৴͢ΔͨΊ ʹཁ͢Δ࣌ؒ͸ɼ௨৴৴߸ͷप‫ظ‬ҎԼͰ͋Δඞཁ͕͋Δɽ ΑͬͯɼҎԼͷ੍໿͕ಋೖ͞ΕΔɽ. 2−ai +bi +6 tcc ≤ Ci , ∀i.. (6). ্‫ه‬ͷ੍໿͸ɼࣜ (4) Λ༻͍ͯɼҎԼͷΑ͏ʹม‫͖Ͱܗ‬Δɽ ⓒ 2013 Information Processing Society of Japan. {(16 + 2BBSS ) p + O}. 2−ai +bi +6 q ≤ Ci , ∀i. w. (7). ௨৴৴߸͕प‫ظ‬తʹ 64 αΠΫϧͷ͏ͪ 2ai ‫ݸ‬ͷ௨৴α ΠΫϧΛ࢖༻͢Δ‫ܗ‬ଶ͸ɼҐ૬͕ 26−ai ௨Γଘࡏ͢ΔͨΊ ʹɼ26−ai ௨Γଘࡏ͢Δɽ௨৴৴߸ͷҐ૬Λࣔ͢੔਺ม਺ ci (1 ≤ ci ≤ 64) Λಋೖ͢Δɽ ௨৴৴߸ͷҐ૬͕ܾ·Ε͹ɼ௨৴৴߸ʹׂΓ౰ͯΒΕΔ ௨৴αΠΫϧ͕શͯఆ·Δɽ௨৴৴߸͕࢖༻͢Δ௨৴αΠ ΫϧΛࣔͨ͢ΊʹɼҎԼͷΑ͏ͳೋ஋ม਺ di, j Λಋೖ͢Δɽ ⎧ −ai +6 ⎪ ⎪ · m (0 ≤ m ≤ 2ai − 1) ͷ৔߹ɽ ⎪ ⎨ 1 j = ci + 2 di, j = ⎪ ⎪ ⎪ ⎩ 0 ͦΕҎ֎ɽ. (8) Ұͭͷ௨৴αΠΫϧʹ‫·ؚ‬ΕΔ੩తεϩοτͷ਺ q ͸ɼ Ұͭͷ௨৴αΠΫϧʹׂΓ౰ͯΒΕΔ௨৴৴߸ͷ࠷େ਺ ʹΑܾͬͯఆ͞ΕΔɽҰͭͷ௨৴αΠΫϧ͋ͨΓͷ੩తε ϩοτͷ਺ q ͸ҎԼͷΑ͏ʹද͞ΕΔɽ. q = max di, j . (9) j. i. Ұͭͷ௨৴ϝοηʔδ͸ҰͭҎ্ͷϑϨʔϜͷ‫ૹͰܗ‬৴ ͞ΕΔɽਤ 5 ʹɼҰͭͷ௨৴ϝοηʔδ͕ҰͭҎ্ͷϑ ϨʔϜͷ‫ૹͰܗ‬ΒΕΔ༷ࢠΛࣔ͢ɽҰ൪໨ͷϑϨʔϜ͕੩ తεϩοτʹΑͬͯૹΒΕΔલʹ଴͕ͪ࣌ؒੜ͡Δɽ௨৴ ৴߸͕௨৴αΠΫϧதͷ੩తεϩοτͷԿΕ͔ʹׂΓ౰ͯ ΒΕΔͱԾఆ͢ΔɽҎԼʹࣔ͢Α͏ʹɼ࠷େ଴ͪ࣌ؒ͸ɼ ׂΓ౰ͯΒΕͨ੩తεϩοτͷִؒͱ౳͍͠ͱ͢Δɽ. 2−ai +6 tcc .. (10). ଴ͪ࣌ؒͷ‫ʹޙ‬ɼϑϨʔϜΛૹΔ͕࣌ؒଓ͘ɽҰͭͷ௨৴ ϝοηʔδΛૹΔ͕࣌ؒɼҎԼʹࣔ͢ɼׂΓ౰ͯΒΕͨ௨ ৴αΠΫϧͷ૯‫ʹܭ‬౳͍͠ͱ͢Δɽ. 2−ai +bi +6 tcc . ௨৴৴߸ i ͷ௨৴ϝοηʔδΛૹ৴͢ΔͨΊͷ࠷ѱϨΠς ϯγ ti ͸࠷ѱ଴ͪ࣌ؒͱҰͭͷ௨৴ϝοηʔδΛૹΔ࣌ؒ ͷ࿨Ͱ͋ΓɼҎԼͷΑ͏ʹද͞ΕΔɽ

(5). ti = 2−ai +6 + 2−ai +bi +6 tcc . (11) ϋʔυσουϥΠϯ੍໿Λຬͨͨ͢Ίʹɼ௨৴৴߸ i ͷ௨ ৴ϝοηʔδΛɼ૬ରσουϥΠϯ Di Λ௒͑ͳ͍Α͏ʹɼ ૹΔඞཁ͕͋Δɽࣜ (11) ΑΓɼҎԼͷ੍໿͕ಋ͔ΕΔɽ.

(6) 2−ai +6 + 2−ai +bi +6 tcc ≤ Di , ∀i. ্‫ه‬ͷ੍໿͸ɼࣜ (4) Λ༻͍ͯɼҎԼͷΑ͏ʹม‫͖Ͱܗ‬Δɽ.

(7) q ≤ Di . (12) {(16 + 2BBSS ) p + O} 2−ai +6 + 2−ai +bi +6 w ਺ཧϞσϧ͸ҎԼͷΑ͏ʹ༩͑ΒΕΔɽ Minimize the cost function w subject to ( 1 ) 2bi +4 p ≥ S i , ∀i. 2−ai +bi +6 q ≤ Ci , ∀i. ( 2 ) {(16 + 2BBSS ) p + O}. w ( 3 ) q = max di, j . j i.

(8) q ≤ Di , ∀i. ( 4 ) {(16 + 2BBSS ) p + O} 2−ai +6 + 2−ai +bi +6 w. 4.

(9) Vol.2013-SLDM-160 No.13 Vol.2013-EMB-28 No.13 2013/3/13. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. transmit request. transmit request. previous period. current period. next period. overall transmission time worst-case waiting time. assigned static slot ਤ5. unassigned static slot. ௨৴ϝοηʔδͷ఻ૹ࣌ؒɽ. Variables • w is a real variable. • p is an integer variable. • q is an integer variable. • ai is an integer variable. • bi is an integer variable. • ci is an integer variable. • di, j is a binary variable.. 3.2 ম͖ͳ·͠๏Λ༻͍ͨ TDMA εέδϡʔϦϯά ম͖ͳ·͠ (SA: simulated annealing) ๏͸ඇܾఆੑΞϧ ΰϦζϜͷҰͭͰ͋Δ [9]ɽධՁ஋͕վળ͞ΕΔղΛ࠾୒ ͢Δ͜ͱʹՃ͑ͯɼ͋Δ৚݅ͷ΋ͱͰධՁ஋͕ѱԽ͢Δղ ΋࠾୒͢Δ఺͕ SA ๏ͷಛ௃ͱͯ͠‫͛ڍ‬ΒΕΔɽ୳ࡧॲཧ ͷॳ‫ظ‬ஈ֊Ͱ͸ɼධՁ஋͕ѱԽ͢ΔղΛ࠾୒͢Δ֬཰͕େ ͖͘ɼ୳ࡧॲཧ͕ਐΉʹͭΕɼධՁ஋͕ѱԽ͢Δ౓߹͍͕ খ͍͞ղͷΈ͕࠾୒͞Ε΍͘͢ͳΔɽ࠷ऴతʹ͸ɼධՁ஋ Λվળ͢ΔղͷΈ͕࠾୒͞ΕΔɽ SA ๏ͷٖࣅίʔυ [9] Λਤ 6 ʹࣔ͢ɽखଓ͖ SA ʹ͓͍ ͯ͸ɼखଓ͖ Metropolis ͷ‫ͼݺ‬ग़͕͠‫܁‬Γฦ͞ΕΔɽखଓ ͖ Metropolis ͕‫ͼݺ‬ग़͞ΕΔ౓ʹɼԹ౓Λද͢ม਺ T ʹྫྷ ٫཰ α ͕৐͡ΒΕɼT ͸‫ݮ‬গ͢ΔɽҰํɼखଓ͖ Metropolis ͕‫ͼݺ‬ग़͞ΕΔ౓ʹɼ M ʹ β ͕৐͡ΒΕɼ M ͸૿Ճ͢Δɽ M ͸खଓ͖ Metropolis ʹ͓͚Δղͷ୳ࡧճ਺Λܾఆ͢Δ ΋ͷͰ͋Δɽखଓ͖ Metropolis ʹ͓͍ͯ͸ɼ༩͑ΒΕͨղ ͷۙ๣Λ໭͢खଓ͖ Neighbor ʹΑͬͯಘΒΕͨҰ࣌ղΛ ಘΔɽ৽ͨʹಘΒΕͨղͱ‫ࡏݱ‬ղͷධՁ஋ͷࠩ෼ʹ‫ͮج‬ ͍ͯɼॲཧ͕ҟͳΔɽධՁ஋͕࡟‫͞ݮ‬Εͨ৔߹ɼNewS Ͱ BestS Λߋ৽͢Δɽ͞΋ͳ͚Ε͹ɼ֬཰తʹɼධՁ஋ͷ૿ ՃΛ‫͠ڐ‬ɼNewS Ͱ CurS Λߋ৽͢Δɽ ຊ‫͍͓ͯʹڀݚ‬͸ɼSA ๏Λ 3.1 અͰࣔͨ͠໰୊ͷղ๏ͱ ͯ͠༻͍ͨɽղۭؒ͸ɼม਺ ai , bi , ci , w, p ʹΑͬͯߏ੒͞ ΕΔɽۙ๣Λ‫ٻ‬ΊΔखଓ͖ Neighbor ʹ͓͍ͯ͸ɼҰఆͷ ֬཰ʹ‫͍ͯͮج‬ɼղΛߏ੒͢Δม਺ΛҰͭબ୒͠ɼ૿‫͞ݮ‬ ͤΔɽ੔਺ม਺ʹ͍ͭͯɼ1 ͚ͩ૿‫͢ݮ‬Δɽw ʹؔͯ͠͸ɼ ਖ਼‫ن‬෼෍ (μ = 0, σ = 50) ʹ‫ݮ૿͍ͯͮج‬஋Λܾఆͨ͠ɽ. ⓒ 2013 Information Processing Society of Japan. worst-case waiting time. sending time. Pseudo-code for Simulated Annealing Procedure SA(S 0 ,T 0 ,α,β,M,MaxTime) // S 0 ͸ॳ‫ظ‬ղ // T 0 ͸ॳ‫ظ‬Թ౓ // α ͸ྫྷ٫཰ // β ͸ఆ਺ // M ͸࣍ͷύϥϝʔλߋ৽·Ͱͷ࣌ؒ // MaxTime ͸૯ॲཧ࣌ؒ begin T = T0 ; CurS = S 0 ; BestS = CurS; CurCost = Cost(CurS); BestCost = Cost(BestS); Time = 0; repeat Metropolis(CurS,CurCost,BestS,BestCost,T,M); Time = Time + M; T = αT; M = βM; until (Time ≥ MaxTime); end Procedure Metropolis(CurS,CurCost,BestS,BestCost,T,M) begin repeat NewS = Neighbor(CurS); NewCost = Cost(NewS); ΔCost = NewCost − CurCost; if (ΔCost < 0 ) then if NewCost < BestCost then BestS = NewS; endif else if (RANDOM < e−ΔCost/T ) then CurS = NewS; endif endif M = M − 1; until (M = 0) end ਤ 6 SA ๏ͷٖࣅίʔυ. 4. ࣮‫ݧ‬ 4.1 ४උ SAE ϕϯνϚʔΫ͸ࣗಈं޲͚෼ࢄ੍‫ޚ‬γεςϜͷ௨৴ ৴߸ཁ݅ͷҰྫͰ͋ΔɽSAE ϕϯνϚʔΫ͸ 53 छྨͷ௨ ৴৴߸͔Βߏ੒͞ΕΔɽSAE ϕϯνϚʔΫͷৄࡉ͸ Kutlu ΒʹΑͬͯ༩͑ΒΕ͍ͯΔ [6]ɽຊߘͷ࣮‫͍͓ͯʹݧ‬͸ɼେ. 5.

(10) Vol.2013-SLDM-160 No.13 Vol.2013-EMB-28 No.13 2013/3/13. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ͖ͳ௨৴৴߸਺ʹରͯ͠΋ SA ʹ‫͍ͨͮج‬ιϧό͕඼࣭ͷ ߴ͍ղΛ‫ٻ‬ΊΔ͜ͱ͕Ͱ͖Δ͜ͱΛ֬ೝ͢ΔͨΊʹɼSAE ϕϯνϚʔΫΛ༻͍ͯԾ૝తͳ௨৴৴߸ू߹Λ࡞੒ͨ͠ɽ ࣮‫͍ͨ༻ʹݧ‬௨৴৴߸ू߹Λද 1 ʹࣔ͢ɽද 1 ͷதͷϕϯ νϚʔΫ bn ͸ n ‫ݸ‬෼ͷ SAE Λ‫ؚ‬Ή͜ͱΛҙຯ͢Δɽ. Operating frequency [Mbps]. 30. ද 1 ࣮‫͍ͨ༻ʹݧ‬௨৴৴߸ू߹ɽ ϕϯνϚʔΫ໊ ௨৴৴߸਺. b1 ʢSAE ϕϯνϚʔΫʣ b2 b3 b4 b5 b6 b7. 53 106 159 212 265 318 371. ຊߘͰࣔ͢‫ʹݧ࣮ػࢉܭ‬͸ɼද 2 ʹࣔ͢ɼPark ΒʹΑͬ ͯ༩͑ΒΕͨωοτϫʔΫύϥϝʔλू߹ [7] Λ༻͍ͨɽ νϟωϧΞΠυϧσϦϛλͷ௚‫ʹޙ‬͸νϟωϧΞΠυϧλ ΠϜ͕ͳ͍ͱԾఆͨ͠ɽ ද 2 ωοτϫʔΫύϥϝʔλɽ Factor Length Header w/o BSS 5 B/frame Header w BSS 45 bits/frame Trailer w/o BSS 3 B/frame Trailer w BSS 27 bits/frame TSS 9 bits/frame FSS 1 bit/frame FES 2 bits/frame Idle delimiter 11 bits/frame Action point offset 1 MT/frame, 10 bits/frame BSS 2 bits/frame byte. 1. 2. 3. 4. 5. 6. 7. 8. 5. ͓ΘΓʹ ຊߘʹ͓͍ͯ͸ɼεϩοτϚϧνϓϨγϯάɼ‫ͼٴ‬ϑ ϨʔϜͷϖΠϩʔυ௕Λ࠷దԽ͠ɼ௨৴όεͷಈ࡞प೾਺ Λ࠷খԽ͢Δ TDMA ௨৴‫ߏػ‬ͷઃ‫ܭ‬ख๏ΛఏҊͨ͠ɽSA ๏Λ࠾༻͢Δ͜ͱͰɼେ‫ن‬໛ͳ਺ͷ௨৴৴߸Λ‫ؚ‬Ήγες Ϝʹରͯ͠΋ɼ඼࣭ͷߴ͍ TDMA εέδϡʔϧΛ࣮༻࣌ ؒ಺ʹಘΔ͜ͱ͕ՄೳͱͳͬͨɽεϩοτϚϧνϓϨΫγ ϯάΛ࠾༻͠ͳ͍‫ط‬ଘख๏ [10, 11] ͱൺ΂ɼఏҊख๏͸ಈ ࡞प೾਺Λ 62.3ʙ63.2%࡟‫͖Ͱݮ‬Δ͜ͱΛ࣮‫ݧ‬తʹ֬ೝ͠ ͨɽఏҊख๏ʹΑͬͯɼΑΓ௿଎Ͱ҆ՁͳϫΠϠϋʔωε Λ༻͍Δ͜ͱ͕Ͱ͖Δ͜ͱ͕‫ظ‬଴͞ΕΔɽ ࢀߟจ‫ݙ‬ [1] [2]. [4]. [6]. [7]. ⓒ 2013 Information Processing Society of Japan. 5. ਤ 7 ௨৴৴߸ू߹ͷ‫ن‬໛ͱಈ࡞प೾਺ͷؔ܎ɽ. [5]. 4.2 ࣮‫݁ݧ‬Ռ ఏҊख๏ͷ༗ޮੑΛࣔͨ͢ΊʹɼSA ʹ‫ͮ͘ج‬ιϧόͰ ಘΒΕΔ TDMA εέδϡʔϧΛɼ‫ط‬ଘ‫ڀݚ‬ͷख๏ [10, 11] Λ༻͍ͯಘΒΕΔ΋ͷͱൺֱͨ͠ɽఏҊख๏͸εϩοτϚ ϧνϓϨΫγϯάΛ࠾༻͢Δ΋ͷͰ͋ΓɼҰํɼ‫ط‬ଘख๏ ͸εϩοτϚϧνϓϨΫγϯάΛ࠾༻͠ͳ͍΋ͷͰ͋Δɽ ਤ 7 ʹ࣮‫݁ݧ‬ՌΛࣔ͢ɽಘΒΕͨόεͷಈ࡞प೾਺͸ɼ௨ ৴৴߸ू߹ͷ‫ن‬໛ʹൺྫͯ͠૿Ճ͢Δ͜ͱ͕Ӑ͑Δɽ‫ط‬ଘ ͷख๏ͱൺ΂ͯɼఏҊख๏͸ 62.3ʙ63.2%ͷಈ࡞प೾਺Λ ࡟‫͢ݮ‬Δ݁ՌͱͳΓɼεϩοτϚϧνϓϨΫγϯάͷޮՌ Λ࣮‫ݧ‬తʹ֬ೝͰ͖ͨɽ·ͨɼ௨৴৴߸਺͕ 159 ‫ݸ‬Λ௒͑ Δ‫ن‬໛ͷϕϯνϚʔΫʹରͯ͠͸ɼ‫ط‬ଘख๏Ͱ͸ɼFlexRay ͷ‫͞ڐ্֨ن‬ΕΔ 10Mbps Λ௒͑Δ݁ՌͱͳΓɼFlexRay ʹ४‫ͨ͠ڌ‬γεςϜΛߏங͢Δ͜ͱ͕Ͱ͖ͳ͍͜ͱ͕ཧղ ͞ΕΔɽ. 10. # of SAE copies. ද 3 SA ͷύϥϝʔλɽ. SM ΛߦΘͳ͍৔߹ͷ࠷దղ [10, 11] 100 0.9, 0.99, 0.999, 0.9999, 0.99999 1.00001, 1.0001, 1.001, 1.01 10, 20, 30, 40, 50, 60, 70, 80, 90, 100. 15. 0. [3]. S0 T0 α β M ͷॳ‫ظ‬஋. 20. 0. 3.1 અʹࣔͨ͠໰୊ͷղΛ༩͑ΔɼSA ๏ʹ‫͍ͨͮج‬ιϧ όΛ C++‫ʹޠݴ‬Αͬͯ։ൃͨ͠ɽSA ͷύϥϝʔλͱͯ͠ɼ ද 3 ʹࣔ͢΋ͷΛ༻͍ͨɽ200 ௨Γͷύϥϝʔλͷ૊߹ͤ ʹରͯ͠ɼSA ๏ʹ‫ͮ͘ج‬ιϧόΛ࣮ߦ͠ɼղΛ‫ٻ‬Ίͨɽ ύϥϝʔλ. w slot multiplexing w/o slot multilexing. 25. [8]. [9] [10]. [11]. [12]. J. Bisschop, AIMMS –optimization modeling–, Apr. 2011. Bosch, “Control area network,” http://www.can.bosch.com/, Jan. 2013. G. Cena and A. Valenzano, “Achieving round-robin access in controller area networks,” IEEE Trans. Ind. Electron., Vol. 49, No. 6, pp.1202–1213, Dec. 2002. FlexRay Consortium, FlexRay communications system protocol specification version 3.0.1, Oct. 2010. ‫ؠ‬Ӭ໌ਓ, ਿ‫ݪ‬ਅ, “৴པੑཁ‫͍ͨͮجʹٻ‬ର‫ނ‬োੑΛ࣮‫ݱ‬ ͢Δ TDMA εέδϡʔϦϯάख๏,” ৘ใॲཧֶձ૊ࠐΈ γεςϜγϯϙδ΢Ϝ, pp. 39–47, 2012 ೥ 10 ݄. A. Kutlu, H. Ekiz, and E. T. Powner, “Performance analysis of MAC protocols for wireless control area network,” Proc. International Symposium on Parallel Architectures, Algorithms, and Networks, pp. 494–499, Jun. 1996. I. Park and M. Sunwoo, “FlexRay network parameter optimization method for automotive applications,” IEEE Trans. on Industrial Electronics, Vol. 58, No. 4, pp. 1449– 1459, Apr. 2011. K. Schmidt and E. G. Schmidt, “Message scheduling for the FlexRay protocol: the static segment,” IEEE Trans. Vehicular Technology, Vol. 58, No. 5, pp. 2170–2179, Jun. 2009. നੴ༸Ұ༁ Sadiq M. Sait Βஶ, ૊߹ͤ࠷దԽΞϧΰϦζ Ϝͷ࠷৽ख๏, ‫ؙ‬ળ‫ࣜג‬ձࣾ, 2002 ೥ 3 ݄. ਿ‫ݪ‬ਅ, ‫ؠ‬Ӭ໌ਔ, “ϋʔυϦΞϧλΠϜੑΛߟྀͨ͠ FlexRay ͷόεଳҬ෯ͷ࠷খԽٕज़,” ৘ใॲཧֶձ‫ڀݚ‬ ใࠂ, Vol. 2012-EMB-24, No. 19, pp. 1–6, 2012 ೥ 3 ݄. M. Sugihara and A. Iwanaga, “Minimization of FlexRay bus bandwidth for hard real-time applications,” Journal of Infor˙ mation Processing, Vol. 21, No. 1, pp.46-52, Jan. 2013. H. Zeng et al., “Schedule optimization of time-triggered systems communicating over the FlexRay static segment,” IEEE Trans. Industrial Informatics, Vol. 7, No. 1, pp. 1–17, Feb. 2011.. 6.

(11)