With the rapid development of wireless network, the integration of cellular and multi-hop networks is the trend for Next Generation Mobile Networks (NGMN). And vertical handoff is really an open and challenge issue in this area. Consequently, in this paper, a Multi-step Vertical HandOff Mechanism (MVHOM) is proposed for a Cellular Multi-hop Network (CMN). The mechanism comprises three steps, getting location information based on arrival time in conjunction with Radio Signal Strength (RSS), then dealing with access network selection by weight of QoS factors calculated by an integrated Analytic Hierarchy Process (AHP) and Grey Relational Analysis (GRA) algorithm, and finally triggering a forced vertical handoff to sustain service continuity. Simulations reveal that the proposed MVHOM can effectively improve the quality of service and performance in CMN.